🏠 Your DSA Lab

A living notebook — 22 topics, each with plain-English concepts, key terms, real code, and an interactive animation you can drive.

The learning path

Seven phases, ordered by difficulty — each one builds on the last. Click any topic to jump there.

📚 Stack

LIFO — Last In, First Out. Think of a stack of plates.

Key terms

push

Add an element to the top of the stack.

pop

Remove and return the top element.

peek / top

Look at the top element without removing it.

LIFO

Last In, First Out — the ordering guarantee.

overflow / underflow

Pushing to a full stack / popping from an empty one.

Sample code

# A Python list already works as a stack
stack = []
stack.append(1)   # push
stack.append(2)
stack.append(3)
top = stack[-1]      # peek -> 3
x = stack.pop()      # pop  -> 3
print(stack)        # [1, 2]

const stack = [];
stack.push(1);        // push
stack.push(2);
stack.push(3);
const top = stack[stack.length - 1]; // peek -> 3
const x = stack.pop();  // pop  -> 3
console.log(stack); // [1, 2]

🎟️ Queue

FIFO — First In, First Out. Think of a line at a ticket counter.

Key terms

enqueue

Add an element to the back of the queue.

dequeue

Remove and return the front element.

front / rear

The two ends: you read from the front, write to the rear.

FIFO

First In, First Out — the ordering guarantee.

Sample code

from collections import deque

q = deque()
q.append("a")     # enqueue (add to rear)
q.append("b")
first = q.popleft() # dequeue -> "a"  (remove from front)
# deque gives O(1) at BOTH ends — always use it, not a list

// A simple queue with an array (fine for learning)
const q = [];
q.push("a");         // enqueue
q.push("b");
const first = q.shift(); // dequeue -> "a"

⏱️ Complexity Analysis

How we measure how fast (time) and how memory-hungry (space) an algorithm is — as the input grows.

The common classes (fastest → slowest)

Key terms

Big-O

Upper bound — the worst-case growth rate. The one you'll quote most.

Big-Θ (theta)

Tight bound — growth that's both an upper and lower bound.

Big-Ω (omega)

Lower bound — the best case.

time vs space

Time = operations performed. Space = extra memory used. You often trade one for the other.

amortized

Average cost per op over a sequence. A dynamic array's push is O(1) amortized even though occasional resizes cost O(n).

best / avg / worst

The same algorithm can behave differently on lucky vs unlucky inputs (e.g. quicksort).

🔢 Arrays & Strings

Contiguous, index-addressed memory — the most fundamental structure. Strings are just arrays of characters.

Key terms

index

The position of an element, starting at 0. a[0] is the first.

contiguous

Stored in one unbroken block of memory — what makes O(1) access possible.

dynamic array

Auto-resizing array (Python list, JS Array). push is O(1) amortized.

in-place

Modifying the array without allocating a copy — O(1) extra space.

two pointers

A common technique: walk two indices toward each other (or at different speeds) to solve problems in one pass.

Sample code

a = [10, 20, 30, 40]
a[2]            # O(1) access -> 30
a.append(50)     # O(1) amortized push
a.insert(0, 5)   # O(n) — shifts everything right
20 in a         # O(n) search (unsorted)

# two-pointer: reverse in place
i, j = 0, len(a) - 1
while i < j:
    a[i], a[j] = a[j], a[i]
    i += 1; j -= 1

const a = [10, 20, 30, 40];
a[2];             // O(1) -> 30
a.push(50);       // O(1) amortized
a.unshift(5);     // O(n) — shifts everything
a.includes(20);   // O(n) search

Complexity

🔗 Linked Lists

Nodes scattered in memory, each pointing to the next. No indices — you follow the chain.

Key terms

node

One link in the chain — holds a value plus a pointer.

pointer / next

Reference from one node to the following node.

head / tail

The first node / the last node (whose next is null).

null

Marks the end of the list — the last node points to nothing.

singly vs doubly

Singly = points forward only. Doubly = each node also points back, so you can walk both ways.

Sample code

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

# build 1 -> 2 -> 3
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)

# traverse — O(n)
node = head
while node:
    print(node.val)
    node = node.next

# insert at head — O(1)
new = Node(0)
new.next = head
head = new

class Node {
  constructor(val) { this.val = val; this.next = null; }
}
let head = new Node(1);
head.next = new Node(2);

// traverse — O(n)
let node = head;
while (node) { console.log(node.val); node = node.next; }

Complexity

🗂️ Hash Tables & Sets

Near-instant lookup by key. A hash function turns a key into a bucket index.

Key terms

hash function

Turns any key into a bucket index, fast and deterministically.

bucket

One slot in the backing array where entries land.

collision

Two keys hashing to the same bucket. Handled by chaining (a list per bucket).

load factor

entries ÷ buckets. When it gets high, the table resizes to keep lookups fast.

set vs map

A set stores keys only (membership). A map/dict stores key→value pairs.

Sample code

# dict = hash map, set = hash set
prices = {"apple": 3, "pear": 5}
prices["apple"]        # O(1) avg lookup -> 3
prices["kiwi"] = 2      # O(1) insert
"pear" in prices        # O(1) membership

seen = set()
seen.add("cat")          # O(1)
"cat" in seen           # O(1)

const prices = new Map([["apple", 3]]);
prices.get("apple");   // O(1) -> 3
prices.set("kiwi", 2);
prices.has("apple");   // O(1)

const seen = new Set();
seen.add("cat");
seen.has("cat");        // O(1)

Complexity

🌳 Trees

Hierarchical data — a root branching into children, with no cycles.

Key terms

root / leaf

Top node with no parent / bottom node with no children.

parent / child

Direct up/down relationships between connected nodes.

depth / height

Depth = distance from root. Height = longest path down to a leaf.

binary tree

Each node has at most two children (left, right).

BST

Binary search tree: left < node < right, giving O(log n) search when balanced.

balanced

Height stays ~log n. Unbalanced, a BST degrades into a linked list (O(n)).

Sample code

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

def inorder(node):
    if not node: return
    inorder(node.left)    # go left
    print(node.val)       # visit
    inorder(node.right)   # go right
# On a BST, in-order prints values sorted.

class TreeNode {
  constructor(val) { this.val = val; this.left = this.right = null; }
}
function inorder(node) {
  if (!node) return;
  inorder(node.left);      // go left
  console.log(node.val);  // visit
  inorder(node.right);     // go right
}

Complexity (balanced BST)

🌲 Tries (Prefix Trees)

A tree of characters for storing strings — built for lightning-fast prefix search (autocomplete).

Key terms

prefix tree

Another name for a trie — the path from root spells out a prefix.

node per character

Each edge is one character; each node has a map of child characters.

end-of-word marker

A flag on a node saying "a complete word ends here" (● in the demo).

prefix search

The trie's superpower: check if any word starts with a prefix in O(L).

Sample code

class Trie:
    def __init__(self):
        self.root = {}          # nested dicts of chars

    def insert(self, word):     # O(L)
        node = self.root
        for ch in word:
            node = node.setdefault(ch, {})
        node["$"] = True     # end-of-word

    def starts_with(self, prefix):  # O(L)
        node = self.root
        for ch in prefix:
            if ch not in node: return False
            node = node[ch]
        return True

class Trie {
  constructor() { this.root = {}; }
  insert(word) {                // O(L)
    let node = this.root;
    for (const ch of word)
      node = node[ch] ??= {};
    node["$"] = true;           // end-of-word
  }
  startsWith(prefix) {           // O(L)
    let node = this.root;
    for (const ch of prefix) {
      if (!(ch in node)) return false;
      node = node[ch];
    }
    return true;
  }
}

Complexity

🕸️ Graphs

Nodes connected by edges — the most general structure. Trees and linked lists are special cases.

Key terms

vertex / edge

A node / a connection between two nodes.

directed vs undirected

Edges one-way (A→B) vs mutual (A—B).

weighted

Edges carry a number (distance, cost). Dijkstra handles these.

adjacency list

Map of node → list of neighbors. Compact for sparse graphs.

adjacency matrix

A V×V grid; edge lookup is O(1) but space is O(V²).

degree

How many edges touch a node.

path / cycle

A route through edges / a path that returns to its start.

Sample code

# adjacency list (undirected)
graph = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "D"],
    "D": ["B", "C"],
}
graph["A"]          # neighbors of A -> ["B", "C"]

# weighted: store (neighbor, weight) pairs
wgraph = {"A": [("B", 5), ("C", 2)]}

// adjacency list (undirected)
const graph = {
  A: ["B", "C"],
  B: ["A", "D"],
  C: ["A", "D"],
  D: ["B", "C"],
};
graph.A;            // -> ["B", "C"]

Complexity

⛰️ Heaps & Priority Queues

A tree that always keeps the smallest (or largest) item at the top — O(log n) to add or remove it.

Key terms

heap property

Every parent ≤ its children (min-heap) — so the min is always the root.

min-heap / max-heap

Smallest on top / largest on top.

sift-up / sift-down

Restore the heap property after an insert (bubble up) or removal (bubble down).

complete binary tree

Every level full except possibly the last, filled left-to-right — lets us use a flat array.

priority queue

The abstract "always give me the highest-priority item" idea; a heap is how it's built.

Sample code

import heapq

h = []
heapq.heappush(h, 5)   # O(log n)
heapq.heappush(h, 2)
heapq.heappush(h, 8)
heapq.heappush(h, 1)
h[0]                   # peek min -> 1  (O(1))
heapq.heappop(h)       # remove min -> 1 (O(log n))
# max-heap trick: push negated values (-v)

// JS has no built-in heap — hand-roll or use a library.
// Concept: array where parent(i) = (i-1)>>1,
// children of i = 2i+1 and 2i+2.
class MinHeap {
  constructor() { this.a = []; }
  push(v) { this.a.push(v); this._up(this.a.length - 1); }
  peek() { return this.a[0]; }   // O(1)
  // _up sifts up; pop() swaps root & last, then sifts down
}

Complexity

📐 Mathematical Foundations

The handful of math ideas that show up in almost every algorithm.

Key terms

Big-O

Upper bound on growth as n → ∞. The vocabulary for comparing algorithms.

logarithm

Inverse of exponentiation. log₂(n) = number of halvings to reach 1.

modulo (%)

Remainder after division. Wraps values into a fixed range [0, m).

GCD

Greatest common divisor of two integers, via Euclid's algorithm.

factorial / nCr

Counting arrangements (n!) and combinations (n choose r) — the basis of combinatorics.

Sample code

def gcd(a, b):        # Euclid's algorithm — O(log(min(a,b)))
    while b:
        a, b = b, a % b   # replace with (b, remainder)
    return a

print(gcd(48, 36))    # 12

# log intuition: how many halvings to reach 1?
n, steps = 1000, 0
while n > 1:
    n //= 2; steps += 1
print(steps)           # 10  (≈ log2(1000))

🔟 Bit Manipulation

Working directly with the binary bits of a number — fast and memory-cheap.

Key terms

bit / mask

A single 0/1; a mask is a number used to isolate or set specific bits.

set / clear / toggle

Turn a bit on (x | 1<<i), off (x & ~(1<<i)), or flip it (x ^ 1<<i).

x & (x-1)

Clears the lowest set bit — the classic trick for counting 1-bits.

XOR trick

a ^ a = 0, so XOR-ing everything cancels pairs and leaves the unique value.

Sample code

x = 0b1010            # 10
is_set = (x >> 1) & 1   # check bit 1 -> 1
x |= (1 << 2)         # set bit 2   -> 1110 (14)
x &= ~(1 << 1)       # clear bit 1 -> 1100 (12)

# find the element that appears once (all others twice)
def unique(nums):
    r = 0
    for v in nums: r ^= v   # pairs cancel to 0
    return r
print(unique([4,1,4,6,1]))  # 6

🔍 Searching Algorithms

Finding an element — from a brute-force scan to O(log n) binary search.

Key terms

linear search

Scan front-to-back. O(n). No ordering required.

binary search

Repeatedly halve a sorted range. O(log n).

lo / mid / hi

The three pointers bounding the current search window.

invariant

"If the target exists, it's within [lo, hi]" — stays true every iteration.

Sample code

def binary_search(a, target):   # a must be SORTED
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == target: return mid
        elif a[mid] < target: lo = mid + 1  # target is right half
        else:                 hi = mid - 1  # target is left half
    return -1                            # not found

print(binary_search([1,3,5,7,9], 7))  # 3

Complexity

🗃️ Sorting Algorithms

Putting things in order — the workhorse behind search, dedup, grouping, and more.

Key terms

comparison sort

Orders by comparing pairs. Lower bound is O(n log n).

stable

Equal elements keep their original relative order (merge sort is; quicksort isn't).

in-place

Sorts using O(1) extra memory (quicksort ~is; merge sort isn't).

pivot / partition

Quicksort's split point and the rearrange step around it.

Sample code

def merge_sort(a):
    if len(a) <= 1: return a           # base case
    mid = len(a) // 2
    left  = merge_sort(a[:mid])          # divide + conquer
    right = merge_sort(a[mid:])
    return merge(left, right)             # combine

def merge(l, r):
    out, i, j = [], 0, 0
    while i < len(l) and j < len(r):
        if l[i] <= r[j]: out.append(l[i]); i += 1
        else:            out.append(r[j]); j += 1
    return out + l[i:] + r[j:]           # leftovers

print(merge_sort([5,2,9,1,6]))    # [1, 2, 5, 6, 9]

🔁 Recursion & Divide-and-Conquer

A function that calls itself — and the strategy of splitting a problem into smaller copies of itself.

Key terms

base case

The stopping condition — solved directly, no further recursion.

recursive case

Where the function calls itself on smaller input.

call stack

The stack (!) of paused function calls waiting to finish. Deep recursion can overflow it.

divide & conquer

Divide → recurse → combine.

Sample code

def factorial(n):
    if n <= 1:            # base case
        return 1
    return n * factorial(n - 1)   # recursive case — shrinks toward base

print(factorial(5))     # 120  (5*4*3*2*1)

# the call stack, top to bottom:
# factorial(5) -> 5 * factorial(4) -> 5*4 * factorial(3) -> ...

🌴 Backtracking

Try a choice, recurse, and undo it if it leads to a dead end.

Key terms

choice

One decision at the current step (place a queen, add an item).

constraint

A rule a valid solution must satisfy.

prune

Abandon a branch early once it can't possibly work.

un-choose

Undo the last choice before trying the next — restores state.

Sample code

# all subsets of [1,2,3] via choose / explore / un-choose
def subsets(nums):
    out, path = [], []
    def dfs(i):
        if i == len(nums):
            out.append(path[:])      # a complete choice
            return
        path.append(nums[i])         # CHOOSE to include
        dfs(i + 1)                  # EXPLORE
        path.pop()                   # UN-CHOOSE
        dfs(i + 1)                  # explore excluding it
    dfs(0)
    return out

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

🪙 Greedy Algorithms

Take the best-looking option right now, and never look back.

Key terms

greedy choice

The locally-best option taken at each step, never revisited.

optimal substructure

Optimal solutions are built from optimal sub-solutions.

exchange argument

The usual proof: show any optimal solution can be swapped toward the greedy one without getting worse.

Sample code

# interval scheduling: most non-overlapping meetings
def max_meetings(intervals):
    intervals.sort(key=lambda x: x[1])  # greedy: earliest FINISH first
    count, end = 0, float('-inf')
    for s, e in intervals:
        if s >= end:          # doesn't overlap the last pick
            count += 1; end = e
    return count

print(max_meetings([(1,3),(2,5),(4,6)]))  # 2

🧩 Dynamic Programming

Break a problem into overlapping subproblems, solve each once, and remember the answer.

Key terms

subproblem / state

A smaller instance, identified by the inputs that matter (the "state").

overlapping subproblems

The same subproblem is needed many times — the signal for DP.

memoization

Top-down: cache results of the recursion.

tabulation

Bottom-up: fill a table from base cases upward.

Sample code

from functools import lru_cache

# naive fib recomputes the same values -> O(2^n)
# memoized: each n computed once -> O(n)
@lru_cache(None)
def fib(n):
    if n < 2: return n      # base cases
    return fib(n-1) + fib(n-2)  # cached after first call

print(fib(50))   # instant: 12586269025

Complexity

🧠 Common Problem-Solving Patterns

The reusable "shapes" that crack the majority of coding problems.

✅ Algorithm Correctness & Proofs

How you know an algorithm works — not just that it passed a few tests.

Key terms

loop invariant

A property true at the top of every iteration; the backbone of loop proofs.

induction

Prove a base case, then that each case implies the next.

termination

Argue the algorithm always halts (e.g., a value strictly decreases toward a bound).

pre/postcondition

What must hold before running / what's guaranteed after.

counterexample

A single input where the algorithm fails — disproves correctness instantly.

Sample: an invariant in action

def max_of(a):
    best = a[0]
    # INVARIANT: `best` == the maximum of a[0..i-1]
    for i in range(1, len(a)):
        if a[i] > best:
            best = a[i]
        # invariant restored: best == max of a[0..i]
    return best   # at exit i==len(a): best == max of whole array