DSA Workbench
Learn how computers sort things, search for things and find their way. Everything is explained in plain words, with pictures you can play with. No experience needed.
What is DSA?
DSA stands for Data Structures and Algorithms. Those are big words for two simple ideas.
Data structure
A clever way to keep your stuff. A toy box with labelled boxes is a data structure, because you always know where each toy lives.
Algorithm
A recipe. A list of steps that gets a job done, like the steps for making a sandwich or for finding a book in a library.
A computer is very fast but not clever. It does exactly what the steps say and nothing more. Good steps and good organising let the same computer finish in a blink instead of in years.
Meet the containers
These are the eight ways programmers keep their stuff. Each one is good at some jobs and slow at others.
How fast is it?
When a pile of toys grows, some jobs stay quick and some get very slow. Move the slider and watch how many steps each way of working needs. The grown-up name for this is Big-O.
The bars are squeezed so all four fit on the screen. A bar that looks only a little longer can be thousands of times more steps. Times assume a computer doing about 100 million small steps every second.
Words you will meet
- Array
- A row of items with numbers on them.
- Index
- The number of a spot in the row. The first spot is number 0, not 1.
- Loop
- Doing the same thing again and again until the job is done.
- Pointer
- A finger that points at one spot. Many tricks use two fingers.
- Sorted
- Lined up from smallest to biggest.
- Recursion
- Solving a big problem by first solving a smaller copy of it, like nesting dolls.
- Big-O
- A way to say how the number of steps grows when the pile grows.
- Time and space
- Time is how many steps a recipe takes. Space is how much memory it needs.
How to use this page
- Watch it work. Press Play and see bars line themselves up, a number guessing game, and a maze being solved.
- Problems. Press “Pick one for me” and try a puzzle. Tap the circle when you solve it.
- Patterns. Each pattern is a recipe that solves a whole family of puzzles, with a real-life picture to help you remember it.
New here? Start with Warm-ups. Tap the circle to cycle: to do, solved, revisit. Progress is saved in this browser only. Problem links open on LeetCode.
Patterns
A pattern is a recipe that solves a whole family of puzzles. Each card has a real-life picture to help you remember it, a short recipe written like code, and practice problems that link to LeetCode. The circle beside a problem shares its progress with the Problems tab.
O(1) the same few steps however big the pile is. O(log n) the work is cut in half each time, like the guessing game. O(n) one look at every item. O(n log n) a little more than one look at every item, which is how good sorting works. O(n²) every item meets every other item, which gets slow very fast. Here n means how many items there are.
How quick is each container?
| Container | Grab one by position | Find something | Add | Remove |
|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) |
| Linked list | O(n) | O(n) | O(1) at a known node | O(1) at a known node |
| Hash map | n/a | O(1) average | O(1) average | O(1) average |
| Balanced BST | n/a | O(log n) | O(log n) | O(log n) |
| Binary heap | O(1) min or max | O(n) | O(log n) | O(log n) |
| Stack / queue | O(1) top or front | O(n) | O(1) | O(1) |
How big is the pile? Choose the speed to aim for
| Size of the pile (n) | Aim for | In plain words |
|---|---|---|
| 10 | O(n!) | A tiny pile. You can afford to try every possible order. (Backtracking) |
| 20 | O(2^n) | A small pile. You can try every way of picking or skipping each item. (Subsets) |
| 500 | O(n³) | Three loops inside each other still finish in time. |
| 5,000 | O(n²) | Two loops inside each other are fine. (Grids and checking pairs) |
| 100,000 to 1,000,000 | O(n log n) | Sort first, or use a heap or a guessing game (binary search). |
| 10,000,000 and up | O(n) or O(log n) | Look at each item only once, or even less. (Lookup book, two fingers, sliding frame) |
A computer does roughly 100 million small steps every second. A job that needs 10 billion steps would take about 100 seconds, which is usually too slow.