Data Structures & Algorithms#

Every structure here comes with a picture you already have in your head — cinema seats, a treasure hunt, a pile of plates, a ticket queue. Learn the mental model first and the code stops being something to memorise. Press Play on any animation to watch the idea move.

Table of Contents#

1. The Only Maths You Need
2. Arrays
3. Linked Lists
4. Stacks
5. Queues
6. Hash Tables & Sets
7. Trees
8. Graphs
9. Searching
10. Sorting
11. Traversal & Shortest Paths
12. The Four Problem-Solving Philosophies
13. The Whole Thing on One Page

The Only Maths You Need#

Before any structure makes sense you need one idea: Big-O. It does not measure seconds — seconds depend on your laptop. It measures how the work grows as the input grows, which is the only thing that still matters when your ten test rows become ten million production rows.

1. O(1) constant — array index, hash lookup. Input size is irrelevant.
2. O(log n) logarithmic — binary search, balanced trees. You halve the problem each step.
3. O(n) linear — one pass over everything.
4. O(n log n) linearithmic — the good sorts. In practice, close enough to linear.
5. O(n²) quadratic — nested loops comparing every pair. Fine for thousands, painful beyond.
6. O(2ⁿ) / O(n!) — every subset, every permutation. Dies around n = 30 and n = 12 respectively.

Big-O measures space the same way it measures time — and it is the half people forget. What counts is the extra memory an algorithm allocates, not the input itself. Two things catch beginners out: the call stack is memory, so recursing n deep costs O(n) even if you allocate nothing; and slicing copies, so nums[1:] inside a loop quietly turns a linear algorithm quadratic.

Unit 1 — Foundational Linear Structures#

Linear structures store data sequentially: one item after another, in a row or a defined order.

Arrays#

• Access O(1)
• Search O(n)
• Insert / delete in middle O(n)

The most fundamental structure: a collection of items stored in contiguous memory blocks. The computer reserves a run of slots right next to each other, and each slot gets a serial number — an index — starting at 0.

Because the slots are equal-sized and adjacent, the address of item i is pure arithmetic: base + i × size. No searching involved — that single fact is why arrays are the default container in every language.

• Strength — instant accessKnow the index and the computer jumps straight there, whether there are ten items or ten million.
• Weakness — the shifting hassleInsert between seats 3 and 4 and everyone from 4 onward shuffles one place right. On a big array that is real work.

seats = [10, 20, 30, 40, 50]

seats[2]              # 30    O(1)  - straight there
seats.append(60)      # O(1)  - adding at the end is cheap
seats.insert(2, 25)   # O(n)  - everything after index 2 shifts right
seats.pop(0)          # O(n)  - everything shifts left
30 in seats           # O(n)  - it has to look at each item

# Gotcha: build 2-D grids row by row, or every row is the SAME list.
grid  = [[0] * 4 for _ in range(3)]   # correct
wrong = [[0] * 4] * 3                 # 3 references to one row

const seats = [10, 20, 30, 40, 50];

seats[2];                 // 30   O(1)
seats.push(60);           // O(1)
seats.splice(2, 0, 25);   // O(n) - shifts everything after index 2
seats.shift();            // O(n) - re-indexes the whole array
seats.includes(30);       // O(n)

// Same 2-D gotcha as Python.
const grid = Array.from({ length: 3 }, () => new Array(4).fill(0)); // correct
const wrong = new Array(3).fill(new Array(4).fill(0));              // one row

Why appending is cheap#

A fixed block of memory cannot grow, so how is append O(1)? The array quietly reserves spare capacity. When it fills up, the language allocates a block twice the size and copies everything across — an O(n) operation. Because the size doubles, that copy happens exponentially rarely: across n appends the total copying is less than 2n. Spread over all of them that is O(1) each, which is what amortised means — a long run is fast, not that every single call is.

def move_zeroes(nums):
    """O(n) time, O(1) space. Order of the non-zeros is preserved."""
    write = 0                       # next slot a non-zero should land in
    for read in range(len(nums)):   # read scans every element once
        if nums[read] != 0:
            nums[write], nums[read] = nums[read], nums[write]
            write += 1


data = [0, 3, 0, 5, 9, 0, 2]
move_zeroes(data)
print(data)                         # [3, 5, 9, 2, 0, 0, 0]

function moveZeroes(nums) {         // O(n) time, O(1) space
  let write = 0;                    // next slot a non-zero should land in
  for (let read = 0; read < nums.length; read++) {
    if (nums[read] !== 0) {
      [nums[write], nums[read]] = [nums[read], nums[write]];
      write++;
    }
  }
}

const data = [0, 3, 0, 5, 9, 0, 2];
moveZeroes(data);
console.log(data);                  // [3, 5, 9, 2, 0, 0, 0]

Linked Lists#

• Access by index O(n)
• Insert / delete at a known node O(1)

Linked lists fix the array's shifting problem by giving up contiguity. Data is scattered anywhere in memory. Each node holds two things: the value, and a pointer — the address of the next node.

• Strength — cheap insertionTo splice a node in between two others you just rewrite two pointers. Nothing else in memory moves.
• Weakness — no jumpingTo reach the 100th item you start at the first and follow 99 pointers. There is no index arithmetic.

The three flavours#

1. Singly linked — a one-way street; nodes point forward only.
2. Doubly linked — a two-way street; each node points forward and back. Costs an extra pointer, buys backward iteration and O(1) deletion given just the node.
3. Circular — the last node points back to the first, forming a loop. Think repeat mode in a music player, or a round-robin scheduler.

class Node:
    def __init__(self, value, nxt=None):
        self.value = value
        self.next = nxt

# Chain three nodes: 10 -> 20 -> 30 -> None
head = Node(10, Node(20, Node(30)))

def walk(head):
    while head:                 # the treasure hunt, one clue at a time
        print(head.value)
        head = head.next

class Node {
  constructor(value, next = null) {
    this.value = value;
    this.next = next;
  }
}

// 10 -> 20 -> 30 -> null
const head = new Node(10, new Node(20, new Node(30)));

function walk(node) {
  while (node) {                // follow the chain of clues
    console.log(node.value);
    node = node.next;
  }
}

Reversing a list is the single most asked linked-list question. The trick is that you need three pointers at once — you must save next before you overwrite it, or you lose the rest of the chain.

def reverse(head):
    """The classic interview question. O(n) time, O(1) space."""
    prev = None
    while head:
        nxt = head.next         # remember where we were going
        head.next = prev        # flip this link backwards
        prev, head = head, nxt  # step both pointers forward
    return prev                 # the old tail is the new head

function reverse(head) {        // O(n) time, O(1) space
  let prev = null;
  let cur = head;
  while (cur) {
    const next = cur.next;      // remember the rest
    cur.next = prev;            // flip the link
    prev = cur;
    cur = next;
  }
  return prev;                  // old tail becomes the new head
}

Stacks#

• Push / pop / peek O(1)
• Rule LIFO — last in, first out

A stack only lets you add or remove at one end, called the top. Push puts something on; pop takes the top one off.

That restriction sounds limiting until you notice it is the exact shape of nesting: the most recently opened thing must be the first one closed. Brackets, HTML tags, function calls and undo history are all nesting problems — which is why stacks are everywhere.

1. The browser Back button.
2. Undo (Ctrl+Z) in any editor.
3. The computer's own call stack — one frame per active function call.
4. Depth-first search, and checking balanced brackets.

def is_balanced(s):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []

    for ch in s:
        if ch in "([{":
            stack.append(ch)            # remember what must be closed
        elif ch in pairs:
            # It must close the MOST RECENT opener - that is the LIFO rule.
            if not stack or stack.pop() != pairs[ch]:
                return False

    return not stack                    # nothing may be left open

print(is_balanced("{[()]}"))    # True
print(is_balanced("{[(])}"))    # False - right count, wrong nesting

function isBalanced(s) {
  const pairs = { ")": "(", "]": "[", "}": "{" };
  const stack = [];

  for (const ch of s) {
    if (ch === "(" || ch === "[" || ch === "{") {
      stack.push(ch);                   // remember what must close
    } else if (ch in pairs) {
      if (stack.pop() !== pairs[ch]) return false;   // wrong opener
    }
  }
  return stack.length === 0;            // nothing left open
}

console.log(isBalanced("{[()]}"));      // true
console.log(isBalanced("{[(])}"));      // false

Queues#

• Enqueue / dequeue O(1)
• Rule FIFO — first in, first out

A queue is fairness. Data enters at the back (enqueue) and leaves from the front (dequeue).

Both a stack and a queue accept the same items — only the exit rule differs. Watch them diverge from identical contents:

The variants worth knowing#

1. Circular queue — the end wraps around to the start, reusing the empty slots left behind at the front instead of growing forever.
2. Double-ended queue (deque) — add and remove at both ends. It subsumes both stack and queue.
3. Priority queue — items are served by importance, not arrival time. Think an emergency room: the heart-attack patient is seen before the mild headache who arrived an hour earlier. Usually built on a heap (below).

from collections import deque

q = deque()
q.append("a")       # enqueue at the back    O(1)
q.append("b")
q.popleft()         # dequeue from the front O(1)  -> 'a'

q.appendleft("z")   # deque powers: both ends are O(1)
q.pop()

# NEVER use list.pop(0) as a queue - it shifts every element, O(n).

// No built-in deque, and shift() is O(n). A head index fixes it:
class Queue {
  constructor() {
    this.items = [];
    this.head = 0;
  }

  enqueue(x) {
    this.items.push(x);                 // O(1)
  }

  dequeue() {                           // O(1) amortised
    if (this.head >= this.items.length) return undefined;
    return this.items[this.head++];     // move the pointer, not the data
  }

  get size() {
    return this.items.length - this.head;
  }
}

The priority queue, up close#

A heap is the usual implementation. It answers exactly one question fast — what is the smallest item right now? — and deliberately keeps everything else unsorted, which is why it is cheaper than a full tree. It needs no pointers at all: store the tree in a plain array where the children of index i live at 2i+1 and 2i+2.

class QueueFromStacks:
    def __init__(self):
        self.inbox = []             # newest items land here
        self.outbox = []            # reversed, so the oldest is on top

    def enqueue(self, x):
        self.inbox.append(x)        # always O(1)

    def _shift(self):
        # ONLY refill when outbox is empty, or the order breaks.
        if not self.outbox:
            while self.inbox:
                self.outbox.append(self.inbox.pop())   # reverse into outbox

    def dequeue(self):
        self._shift()
        return self.outbox.pop() if self.outbox else None

    def peek(self):
        self._shift()
        return self.outbox[-1] if self.outbox else None


q = QueueFromStacks()
q.enqueue(1); q.enqueue(2); q.enqueue(3)
print(q.dequeue(), q.dequeue(), q.dequeue())    # 1 2 3  - FIFO preserved

class QueueFromStacks {
  constructor() {
    this.inbox = [];                // newest items land here
    this.outbox = [];               // reversed, so the oldest is on top
  }

  enqueue(x) {
    this.inbox.push(x);             // always O(1)
  }

  #shift() {
    // ONLY refill when outbox is empty, or the ordering breaks.
    if (this.outbox.length === 0) {
      while (this.inbox.length) this.outbox.push(this.inbox.pop());
    }
  }

  dequeue() {
    this.#shift();
    return this.outbox.pop();
  }

  peek() {
    this.#shift();
    return this.outbox.at(-1);
  }
}

const q = new QueueFromStacks();
q.enqueue(1); q.enqueue(2); q.enqueue(3);
console.log(q.dequeue(), q.dequeue(), q.dequeue());   // 1 2 3

Unit 2 — High-Speed & Relational Structures#

Past simple lines: structures for near-instant lookup, hierarchies, and networks.

Hash Tables & Sets#

• Insert / lookup / delete O(1) average
• Worst case O(n)
• No ordering

A hash table is an array you index with something other than a number. It stores key-value pairs, and a hash function is the machine that turns a key into a slot number.

Two different keys can land in the same drawer — a collision. The usual fix is chaining: each bucket holds a little list, and lookups compare keys inside it. As long as the table stays mostly empty the chains stay tiny and lookups stay O(1) on average.

A set is the same machinery with the values thrown away — it stores only unique keys and silently swallows duplicates. Think a VIP guest list where a name cannot appear twice.

# Dictionaries and sets
ages = {"ada": 36, "alan": 41}
ages["grace"] = 45          # O(1) insert
ages.get("linus", 0)        # 0 - no KeyError
"ada" in ages               # O(1) membership

seen = {1, 2, 3}            # a set: unique keys only
seen.add(3)                 # still {1, 2, 3}

def two_sum(nums, target):
    """Find two numbers adding to target. O(n) instead of O(n^2)."""
    seen = {}                       # value -> index
    for i, x in enumerate(nums):
        if target - x in seen:      # is my partner already here?
            return seen[target - x], i
        seen[x] = i
    return None

print(two_sum([2, 7, 11, 15], 9))   # (0, 1)

// Map is the right default - any key type, keeps insertion order.
const ages = new Map([["ada", 36], ["alan", 41]]);
ages.set("grace", 45);      // O(1)
ages.get("linus") ?? 0;     // 0
ages.has("ada");            // O(1)

const seen = new Set([1, 2, 3]);
seen.add(3);                // still {1, 2, 3}

function twoSum(nums, target) {     // O(n) instead of O(n^2)
  const index = new Map();          // value -> index
  for (let i = 0; i < nums.length; i++) {
    if (index.has(target - nums[i])) return [index.get(target - nums[i]), i];
    index.set(nums[i], i);
  }
  return null;
}

console.log(twoSum([2, 7, 11, 15], 9));   // [0, 1]

Trees#

• Traversal O(n)
• Balanced operations O(log n)
• Degenerate O(n)

Trees hold hierarchy — data spreading out from a single origin. Computer-science trees grow upside down: they start at a root at the top and branch downward through parents and children to leaves, which are nodes with no children of their own.

Binary search tree — the guessing game#

A BST adds one rule: every value in the left subtree is smaller than its parent, every value on the right is larger. That single invariant turns a walk into a search — at each node you throw away an entire subtree without looking at it.

Balanced trees — AVL and red-black#

These trees notice when they are becoming lopsided and rotate — a constant-time pointer rearrangement that pulls one node up and pushes another down while preserving the ordering. The result is a guaranteed O(log n) height instead of a hopeful one.

Tries — the autocomplete tree#

A trie (prefix tree) stores words along the edges rather than in the nodes. Each node is a single letter, and shared prefixes share one path — "car" and "cat" both travel the same c → a edges before splitting. Lookup time depends on the length of the word, not on how many words are stored.

class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value, self.left, self.right = value, left, right


def max_depth(node):
    """O(n) time, O(h) stack space."""
    if node is None:
        return 0                    # base case: an empty tree has no depth
    # Trust that each side returns its own answer, then combine.
    return 1 + max(max_depth(node.left), max_depth(node.right))


#        3
#       / \
#      9   20
#         /  \
#        15   7
tree = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
print(max_depth(tree))              # 3

class TreeNode {
  constructor(value, left = null, right = null) {
    this.value = value;
    this.left = left;
    this.right = right;
  }
}

function maxDepth(node) {           // O(n) time, O(h) stack space
  if (!node) return 0;              // base case: empty tree has no depth
  // Trust each side to return its own answer, then combine.
  return 1 + Math.max(maxDepth(node.left), maxDepth(node.right));
}

const tree = new TreeNode(3, new TreeNode(9),
                             new TreeNode(20, new TreeNode(15), new TreeNode(7)));
console.log(maxDepth(tree));        // 3

Graphs#

• Adjacency list O(V + E) space
• Traversal O(V + E)

Graphs are the most general structure there is: vertices (the data points) joined by edges (the connections). Any point may connect to any other. Trees, linked lists and grids are all just graphs with extra rules.

1. Undirected — the relationship runs both ways. Facebook friends.
2. Directed — one-way, drawn with arrows. Instagram followers.
3. Weighted — each edge carries a cost or distance. Google Maps, in kilometres or minutes.
4. Unweighted — connections with no value attached. Plain social circles.

You almost always store a graph as an adjacency list — a map from each vertex to its neighbours. It costs O(V + E) and makes "who is next to me?" instant, which is exactly what every traversal asks.

from collections import defaultdict

def build(edges, directed=False):
    graph = defaultdict(list)
    for a, b in edges:
        graph[a].append(b)
        if not directed:
            graph[b].append(a)      # undirected: the road runs both ways
    return graph

friends = build([("ada", "alan"), ("alan", "grace"), ("ada", "grace")])
print(friends["ada"])               # ['alan', 'grace']

# A grid is a graph too: each cell is a vertex with up to four edges.
DIRECTIONS = ((-1, 0), (1, 0), (0, -1), (0, 1))

function build(edges, directed = false) {
  const graph = new Map();
  const add = (a, b) => {
    if (!graph.has(a)) graph.set(a, []);
    graph.get(a).push(b);
  };
  for (const [a, b] of edges) {
    add(a, b);
    if (!directed) add(b, a);       // undirected: both ways
  }
  return graph;
}

const friends = build([["ada", "alan"], ["alan", "grace"], ["ada", "grace"]]);
console.log(friends.get("ada"));    // ['alan', 'grace']

const DIRECTIONS = [[-1, 0], [1, 0], [0, -1], [0, 1]];   // grid neighbours

def count_islands(grid):
    """O(rows * cols) - every cell is visited at most once."""
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    islands = 0

    def sink(r, c):
        """Flood-fill this island so it is never counted again."""
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != "1":
            return                      # off the grid, or water/already sunk
        grid[r][c] = "0"                # mark visited by sinking the land
        sink(r + 1, c); sink(r - 1, c)
        sink(r, c + 1); sink(r, c - 1)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1":       # unvisited land = a brand new island
                islands += 1
                sink(r, c)
    return islands


print(count_islands([["1", "1", "0", "0"],
                     ["1", "1", "0", "0"],
                     ["0", "0", "1", "0"]]))     # 2

function countIslands(grid) {           // O(rows * cols)
  if (!grid.length) return 0;
  const rows = grid.length;
  const cols = grid[0].length;
  let islands = 0;

  const sink = (r, c) => {              // flood-fill one island
    if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] !== "1") return;
    grid[r][c] = "0";                   // mark visited by sinking the land
    sink(r + 1, c); sink(r - 1, c);
    sink(r, c + 1); sink(r, c - 1);
  };

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === "1") {         // unvisited land = a new island
        islands++;
        sink(r, c);
      }
    }
  }
  return islands;
}

console.log(countIslands([["1","1","0","0"],
                          ["1","1","0","0"],
                          ["0","0","1","0"]]));  // 2

Unit 3 — Core Algorithms#

Structures hold the data. Algorithms are the disciplined, step-by-step methods for working with it.

Searching#

1. Linear search O(n) — check every item one by one. Slow, but it is the only option on unsorted data.
2. Binary search O(log n) — requires sorted data. Open in the middle, decide whether the target is left or right, throw the other half away, repeat.

def binary_search(nums, target):
    """Index of target, or -1. Requires a SORTED list."""
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2   # overflow-safe midpoint, good habit
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            lo = mid + 1            # discard mid and everything left of it
        else:
            hi = mid - 1            # discard mid and everything right of it
    return -1

print(binary_search([2, 5, 8, 12, 16, 23, 38, 56, 72, 91], 72))   # 8

function binarySearch(nums, target) {   // needs a SORTED array
  let lo = 0;
  let hi = nums.length - 1;
  while (lo <= hi) {
    const mid = lo + ((hi - lo) >> 1);  // overflow-safe midpoint
    if (nums[mid] === target) return mid;
    if (nums[mid] < target) lo = mid + 1;   // drop the left half
    else hi = mid - 1;                      // drop the right half
  }
  return -1;
}

console.log(binarySearch([2, 5, 8, 12, 16, 23, 38, 56, 72, 91], 72));  // 8

def search_rotated(nums, target):
    """O(log n). One half of any split is always properly sorted."""
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] == target:
            return mid

        if nums[lo] <= nums[mid]:               # LEFT half is sorted
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1                    # target is inside it
            else:
                lo = mid + 1                    # must be in the messy half
        else:                                   # RIGHT half is sorted
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1


print(search_rotated([4, 5, 6, 7, 0, 1, 2], 0))     # 4
print(search_rotated([4, 5, 6, 7, 0, 1, 2], 3))     # -1

function searchRotated(nums, target) {  // O(log n)
  let lo = 0;
  let hi = nums.length - 1;
  while (lo <= hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (nums[mid] === target) return mid;

    if (nums[lo] <= nums[mid]) {        // LEFT half is sorted
      if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
      else lo = mid + 1;                // must be in the messy half
    } else {                            // RIGHT half is sorted
      if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
      else hi = mid - 1;
    }
  }
  return -1;
}

console.log(searchRotated([4, 5, 6, 7, 0, 1, 2], 0));   // 4
console.log(searchRotated([4, 5, 6, 7, 0, 1, 2], 3));   // -1

Sorting#

You will rarely write a sort in production — both languages ship excellent ones. You learn them because they are the clearest demonstration of algorithmic technique: one task, solved six ways, with the trade-offs on display. Switch algorithms in the picker and watch how differently each one attacks identical data.

1. Bubble sort O(n²) — compare neighbours and swap them, so the largest values bubble up to the end. Simple, slow, rarely the right answer.
2. Selection sort O(n²) — scan for the smallest item, put it at the front, repeat on what remains. Makes the fewest writes of any sort.
3. Insertion sort O(n²) — exactly how you arrange playing cards in your hand: take the next card and slide it into place among the ones already sorted. Genuinely fast on nearly-sorted data.
4. Merge sort O(n log n) — divide and conquer. Split until each piece is a single item, then merge pairs back together in order. Guaranteed fast, needs extra space.
5. Quicksort O(n log n) average — pick a pivot, shove everything smaller to its left and everything larger to its right, then repeat on both sides. Fastest in practice.

Two words get used constantly when comparing sorts. A sort is stable if items that compare equal keep their original relative order — that is what lets you sort by surname, then by department, and still have surnames ordered within each department. It is in place if it needs only O(1) extra memory rather than a second array. Merge sort is stable but not in place; quicksort is in place but not stable.

def merge_sort(nums):
    """Divide and conquer. O(n log n) always."""
    if len(nums) <= 1:
        return nums
    mid = len(nums) // 2
    left = merge_sort(nums[:mid])       # solve each half
    right = merge_sort(nums[mid:])

    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):      # then merge them
        if left[i] <= right[j]:
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    return out + left[i:] + right[j:]


print(merge_sort([38, 12, 47, 5, 29]))    # [5, 12, 29, 38, 47]

function mergeSort(nums) {              // O(n log n) always
  if (nums.length <= 1) return nums;
  const mid = nums.length >> 1;
  const left = mergeSort(nums.slice(0, mid));    // solve each half
  const right = mergeSort(nums.slice(mid));

  const out = [];
  let i = 0;
  let j = 0;
  while (i < left.length && j < right.length) {  // then merge
    if (left[i] <= right[j]) out.push(left[i++]);
    else out.push(right[j++]);
  }
  return [...out, ...left.slice(i), ...right.slice(j)];
}

console.log(mergeSort([38, 12, 47, 5, 29]));   // [5, 12, 29, 38, 47]

Quicksort inverts the effort: instead of doing the work while merging, it does it while splitting. The version below allocates new lists to stay readable — real implementations partition in place.

def quicksort(nums):
    """Pick a pivot, split around it, repeat. Average O(n log n)."""
    if len(nums) <= 1:
        return nums
    pivot = nums[len(nums) // 2]
    smaller = [x for x in nums if x < pivot]
    equal = [x for x in nums if x == pivot]
    larger = [x for x in nums if x > pivot]
    return quicksort(smaller) + equal + quicksort(larger)


print(quicksort([38, 12, 47, 5, 29]))     # [5, 12, 29, 38, 47]

function quicksort(nums) {              // average O(n log n)
  if (nums.length <= 1) return nums;
  const pivot = nums[nums.length >> 1];
  const smaller = nums.filter((x) => x < pivot);
  const equal = nums.filter((x) => x === pivot);
  const larger = nums.filter((x) => x > pivot);
  return [...quicksort(smaller), ...equal, ...quicksort(larger)];
}

console.log(quicksort([38, 12, 47, 5, 29]));   // [5, 12, 29, 38, 47]

def sort_colors(nums):
    """O(n) time, O(1) space, single pass. Values must be 0, 1 or 2."""
    low, i, high = 0, 0, len(nums) - 1

    while i <= high:
        if nums[i] == 0:
            nums[low], nums[i] = nums[i], nums[low]
            low += 1
            i += 1              # the swapped-in value was already checked
        elif nums[i] == 2:
            nums[i], nums[high] = nums[high], nums[i]
            high -= 1           # do NOT advance i - that value is unseen
        else:                   # nums[i] == 1, already in the middle band
            i += 1


data = [2, 0, 2, 1, 1, 0]
sort_colors(data)
print(data)                     # [0, 0, 1, 1, 2, 2]

function sortColors(nums) {     // O(n) time, O(1) space, single pass
  let low = 0;
  let i = 0;
  let high = nums.length - 1;

  while (i <= high) {
    if (nums[i] === 0) {
      [nums[low], nums[i]] = [nums[i], nums[low]];
      low++;
      i++;                      // swapped-in value was already checked
    } else if (nums[i] === 2) {
      [nums[i], nums[high]] = [nums[high], nums[i]];
      high--;                   // do NOT advance i - that value is unseen
    } else {
      i++;                      // a 1 is already in the middle band
    }
  }
}

const data = [2, 0, 2, 1, 1, 0];
sortColors(data);
console.log(data);              // [0, 0, 1, 1, 2, 2]

Traversal & Shortest Paths#

Once data sits in a tree or graph you need a systematic way to visit it. There are two, and they differ by a single detail: which item you take out of the waiting list next.

• Depth-first search (DFS)Dive as deep as possible down one branch, then back up and try the next. Uses a stack, or plain recursion. Good for "does a path exist?", cycle detection and connected components.
• Breadth-first search (BFS)Visit every immediate neighbour first, then everything two steps away, and so on. Uses a queue. Good for "fewest moves" and shortest paths on unweighted graphs.

On a binary tree the same two ideas produce four standard orders. The three depth-first ones differ only in when the node itself is visited relative to its children — a one-line change with completely different uses. In-order on a BST comes out perfectly sorted.

from collections import deque

def bfs(graph, start):
    """Queue -> oldest first -> explores level by level. O(V + E)."""
    visited = {start}
    q = deque([start])
    order = []

    while q:
        node = q.popleft()              # OLDEST first
        order.append(node)
        for neighbour in graph[node]:
            if neighbour not in visited:
                visited.add(neighbour)  # mark on ENQUEUE, or it enters twice
                q.append(neighbour)
    return order

function bfs(graph, start) {            // queue -> level by level
  const visited = new Set([start]);
  const queue = [start];
  const order = [];
  let head = 0;                         // index, not shift() - keeps it O(1)

  while (head < queue.length) {
    const node = queue[head++];         // OLDEST first
    order.push(node);
    for (const neighbour of graph.get(node) ?? []) {
      if (visited.has(neighbour)) continue;
      visited.add(neighbour);           // mark on ENQUEUE
      queue.push(neighbour);
    }
  }
  return order;
}

Now change one word. Swap the queue for a stack — take the newest item instead of the oldest — and the same loop dives down a single branch instead of spreading in rings. Nothing else differs.

def dfs(graph, start):
    """Stack -> newest first -> dives down one branch. O(V + E)."""
    visited = set()
    stack = [start]
    order = []

    while stack:
        node = stack.pop()              # NEWEST first
        if node in visited:
            continue
        visited.add(node)
        order.append(node)
        stack.extend(graph[node])
    return order

function dfs(graph, start) {            // stack -> dive deep
  const visited = new Set();
  const stack = [start];
  const order = [];

  while (stack.length) {
    const node = stack.pop();           // NEWEST first
    if (visited.has(node)) continue;
    visited.add(node);
    order.push(node);
    stack.push(...(graph.get(node) ?? []));
  }
  return order;
}

Dijkstra's algorithm — shortest path with costs#

BFS finds the fewest hops. When edges have costs — kilometres, minutes, money — you need Dijkstra. It keeps a min-heap (priority queue) of the cheapest place to go next, and relaxes edges as it goes: whenever a shortcut is found, the recorded cost is lowered. This is what powers Google Maps.

The Four Problem-Solving Philosophies#

Almost every algorithm is built on one of four mindsets. Recognising which one a problem wants is most of the battle.

1. Greedy#

Philosophy: take the best option available right now and never look back.

2. Divide & Conquer#

Philosophy: break an intimidating problem into small independent sub-problems, solve those, and combine the results.

Merge sort and quicksort are the canonical examples: split ten million items down to single items, where the problem is trivial, then reassemble. The sub-problems being independent is what separates this from dynamic programming.

All of it runs on recursion — a function that calls itself on a smaller input. You write it as if the smaller case is already solved, which is the mental leap, and handle only the smallest case by hand. Every recursive function needs exactly three things:

1. A base case that returns without recursing — in merge sort, a list of one item is already sorted.
2. A recursive case that calls itself on a strictly smaller input.
3. Progress — every path must move toward the base case.

3. Dynamic Programming#

Philosophy: those who do not remember the past are condemned to recompute it.

Fibonacci is the standard demonstration. Naive recursion recomputes the same values an exponential number of times; caching them makes it linear. Step through the animation and watch the cache start intercepting calls:

def fib_slow(n):
    """O(2^n) - recomputes the same subproblems over and over."""
    if n <= 1:
        return n
    return fib_slow(n - 1) + fib_slow(n - 2)

function fibSlow(n) {                   // O(2^n)
  if (n <= 1) return n;
  return fibSlow(n - 1) + fibSlow(n - 2);
}

Now add the diary. The logic is untouched — the only change is that finished answers get written down, and that alone collapses O(2ⁿ) to O(n).

from functools import lru_cache

@lru_cache(maxsize=None)
def fib_fast(n):
    """O(n). The decorator IS the diary."""
    if n <= 1:
        return n
    return fib_fast(n - 1) + fib_fast(n - 2)


print(fib_fast(300))        # instant

const memo = new Map();
function fibFast(n) {                   // O(n) - the Map is the diary
  if (n <= 1) return n;
  if (memo.has(n)) return memo.get(n);
  const value = fibFast(n - 1) + fibFast(n - 2);
  memo.set(n, value);
  return value;
}

console.log(fibFast(90));               // use BigInt past 2^53 - 1

Once you see that each answer depends only on the two before it, you can drop the recursion entirely and sweep forward with two variables — same result, no stack frames, constant memory.

def fib_iterative(n):
    """O(n) time, O(1) space - no recursion at all."""
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a


print(fib_iterative(90))    # 2880067194370816120

function fibIterative(n) {              // O(n) time, O(1) space
  let [a, b] = [0, 1];
  for (let i = 0; i < n; i++) [a, b] = [b, a + b];
  return a;
}

console.log(fibIterative(90));          // use BigInt past 2^53 - 1

4. Backtracking#

Philosophy: try a path; on hitting a dead end, step back to the last junction and try a different one.

The code is always the same three lines — choose, explore, un-choose:

def subsets(nums):
    """All 2^n subsets. At each index: take it, or skip it."""
    out, path = [], []

    def go(i):
        if i == len(nums):
            out.append(path[:])     # copy - path keeps mutating
            return
        go(i + 1)                   # skip nums[i]
        path.append(nums[i])        # 1. choose
        go(i + 1)                   # 2. explore
        path.pop()                  # 3. un-choose

    go(0)
    return out

print(subsets([1, 2, 3]))
# [[], [3], [2], [2,3], [1], [1,3], [1,2], [1,2,3]]

function subsets(nums) {                // all 2^n subsets
  const out = [];
  const path = [];

  const go = (i) => {
    if (i === nums.length) {
      out.push([...path]);              // copy - path keeps mutating
      return;
    }
    go(i + 1);                          // skip
    path.push(nums[i]);                 // 1. choose
    go(i + 1);                          // 2. explore
    path.pop();                         // 3. un-choose
  };

  go(0);
  return out;
}

console.log(subsets([1, 2, 3]).length); // 8

The Whole Thing on One Page#

Pick a structure#

Pick an approach#

• "Sorted array" + find a pairTwo pointers, one at each end. O(n).
• "Have I seen this before?"Hash set. Turns O(n²) into O(n).
• "Top k" or "k-th largest"A heap of size k.
• "Fewest moves / steps"BFS.
• "Does a path exist?"DFS.
• "Cheapest route" with costsDijkstra.
• "How many ways" / "min or max cost"Dynamic programming.
• "All combinations / permutations"Backtracking with pruning.
• "Prefix" or "autocomplete"Trie.
• "Dependencies / prerequisites"Topological sort on a DAG.

How to attack any problem#

1. Restate it in your own words. Confirm the edge cases: empty input, one element, duplicates, negatives, maximum size.
2. Write the brute force, even just out loud. It gives you a correct baseline and a complexity to beat.
3. Find the waste. What is being recomputed? What gets thrown away between iterations?
4. Match the pattern from the list above.
5. Say the complexity out loud — time and space — before you call it done.

Where to go next#

1. 📘 The DSA Detailed Course — the same ground in 38 sections, plus prefix sums, union-find, topological sort, MSTs, segment trees, string matching and a full practice roadmap.
2. 📖 VisuAlgo — interactive visualisations of every structure here.
3. 🧠 LeetCode — for the repetitions. Time-box to 25 minutes, then read the solution and re-solve it from scratch the next day.

"Bad programmers worry about the code. Good programmers worry about data structures and their relationships." — Linus Torvalds