DSA Tutorial: From Zero to Interview Ready (Complete Guide)

Almost every technical interview at Google, Meta, Amazon, or any top tech company starts with a data structures and algorithms (DSA) question. Trees alone show up in about 20-25% of interview questions at top companies. If you want to pass coding interviews, DSA is not optional.

This guide takes you from the basics of Big O notation to the patterns that solve most interview problems. All examples use Python for clarity — the ideas apply the same way in Kotlin, Go, Java, or any language you already know. Where a language-specific detail actually changes the code (like integer overflow), we call it out in prose instead of repeating every example three times.

What you need: basic programming knowledge in any language — variables, loops, functions, and classes. No computer science degree required.

Part 1: Complexity and Foundations

Big O Notation

Big O describes how an algorithm’s time or space grows as input size n grows. It is the upper bound — the worst case. We ignore constants and lower-order terms: O(2n) is O(n), O(n + 100) is O(n), O(3n² + 5n) is O(n²). We care about growth rate, not exact operation counts.

For n = 1,000,000: O(1) is 1 operation, O(log n) is ~20, O(n) is 1,000,000, O(n log n) is ~20,000,000, O(n²) is 1,000,000,000,000 (too slow), O(2ⁿ) is impossible to finish.

Rules for calculating Big O from code: a single loop over n elements is O(n). Nested loops multiply: a loop inside a loop is O(n²). Sequential blocks add, then keep the dominant term: O(n) + O(n²) = O(n²). Halving the input each step is O(log n) — binary search is the textbook example. For recursive functions, count how many calls happen and how much work each does: two recursive calls per level (naive Fibonacci) is O(2ⁿ); one call per level (factorial) is O(n).

Space complexity works the same way, but only counts extra memory, not the input itself: a few variables is O(1), a new array of size n is O(n), a recursive call stack of depth n is O(n).

Amortized analysis matters for one common case: appending to a dynamic array (Python list, Kotlin ArrayList, Go slice). Most appends are O(1), but when the array is full it must resize — copy everything to a bigger array, an O(n) operation. Because resizing is rare, the average cost per append is still O(1). This is called amortized O(1).

Big O reference for every structure in this guide:

* Only if you already have a reference to the node — otherwise O(n) to find it. ** Peek only. m = string length, N = number of words, M = average word length.

Two mistakes catch people constantly: the in operator on a Python list is O(n), not O(1) — use a set for O(1) membership. And string concatenation in a loop is O(n²) in Python and Kotlin because strings are immutable and each += builds a new string — use "".join() instead.

Choosing the Right Data Structure

The first interview question is always: what data structure fits this problem? Ask three questions:

What do you need to do most often? Access by index → array. Look up by key → hash map. Insert/delete at ends → stack or queue. Always get min/max → heap. Search by prefix → trie. Check connectivity → union-find or graph + BFS/DFS. Maintain sorted order → BST.

Am I storing relationships or just values? Just values → array, set, heap. Key-value pairs → hash map. Hierarchical data → tree. Connections between items → graph. Groups of items → union-find.

Do I need worst-case guarantees, or is average-case fine? A hash map is O(1) average but O(n) worst case with a bad hash. A balanced BST is O(log n) guaranteed. If an interviewer pushes on worst case, that difference is the answer.

Quick decision path: need O(1) lookup by key → hash map. Need min/max repeatedly → heap. Need sorted order → BST. Strings with prefixes → trie. Track connected groups over time → union-find. Graph or grid needing shortest path → BFS; otherwise DFS. Need LIFO → stack. Need FIFO → queue. Otherwise → array.

In practice, arrays beat linked lists almost every time — even when a textbook says linked lists give O(1) insert. Dynamic arrays are contiguous in memory, so the CPU cache loads many elements at once; linked list nodes are scattered, so every .next is a cache miss. Only reach for a linked list when you need O(1) insert/delete at a position you already have a pointer to, and don’t want to shift elements.

Part 2: Linear Data Structures

Arrays and Strings

An array stores elements in contiguous memory, each reachable by index in O(1). A dynamic array (Python list) grows automatically; inserting at the end is O(1) amortized, inserting at an arbitrary index is O(n) because everything after it must shift.

Strings are immutable in Python, Kotlin, and Go — you cannot change a character in place, you build a new string. That’s why repeated concatenation in a loop is O(n²): each += allocates a fresh string.

Two pointers is the single most useful array technique: two indices that move through the array based on a condition, instead of nested loops.

def two_sum_sorted(numbers, target):
    left, right = 0, len(numbers) - 1
    while left < right:
        total = numbers[left] + numbers[right]
        if total == target:
            return [left, right]
        elif total < target:
            left += 1   # need a bigger sum
        else:
            right -= 1  # need a smaller sum
    return []

This runs in O(n) time, O(1) space — no nested loop needed because the array is sorted, so moving a pointer inward always moves the sum in a predictable direction.

Valid Anagram (LeetCode #242) is the canonical frequency-counting problem: two strings are anagrams if they have the same character counts.

def is_anagram(s, t):
    if len(s) != len(t):
        return False
    count = [0] * 26
    for a, b in zip(s, t):
        count[ord(a) - ord('a')] += 1
        count[ord(b) - ord('a')] -= 1
    return all(c == 0 for c in count)

O(n) time, O(1) space — the count array is always size 26 regardless of string length.

Interviewers like array/string questions because they test index handling (off-by-one is the most common bug), whether you notice an O(n) improvement over an O(n²) brute force, and whether you handle edge cases: empty input, single element, duplicates.

Linked Lists

A linked list is a chain of nodes, each holding a value and a pointer to the next node. Unlike arrays, nodes live anywhere in memory — you can only reach one by walking from the head.

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

Inserting at the head is O(1) — just point the new node at the old head. Inserting at the tail is O(n) — you must walk to the end first, unless you keep a tail pointer. This asymmetry is why arrays usually win: appending to a dynamic array is O(1) amortized, but linked lists are only fast for insert/delete when you already hold the node.

Reversing a linked list is the single most common linked-list interview question. Track three pointers — previous, current, next — and flip each link as you walk:

def reverse_list(head):
    prev = None
    current = head
    while current is not None:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    return prev

O(n) time, O(1) space.

Fast and slow pointers (Floyd’s algorithm) is the second most important pattern. The slow pointer moves one step, the fast pointer moves two. If there’s a cycle, fast eventually laps slow and they meet; if not, fast reaches the end first.

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

The same technique finds the middle node: when fast reaches the end, slow is at the midpoint, because it moved half as far.

Merging two sorted lists introduces the dummy node trick — instead of special-casing “what is the head,” create a placeholder node and build the result after it, then return dummy.next:

def merge_two_lists(l1, l2):
    dummy = ListNode(0)
    current = dummy
    while l1 and l2:
        if l1.value <= l2.value:
            current.next, l1 = l1, l1.next
        else:
            current.next, l2 = l2, l2.next
        current = current.next
    current.next = l1 or l2
    return dummy.next

A doubly linked list adds a prev pointer, trading extra memory for O(1) deletion when you already hold the node (no need to walk from the head to find its predecessor). A circular linked list has the tail point back to the head instead of None — useful for round-robin scheduling.

Stacks and Queues

A stack is LIFO (last in, first out) — push and pop from the same end, both O(1). A queue is FIFO (first in, first out) — enqueue at the back, dequeue from the front, both O(1) with the right structure (Python’s collections.deque, not a plain list, since popping from the front of a list is O(n)).

Valid Parentheses (LeetCode #20) is the classic stack problem: push opening brackets, and when you see a closing bracket, it must match whatever is on top of the stack.

def is_valid(s):
    stack = []
    pairs = {')': '(', '}': '{', ']': '['}
    for char in s:
        if char in '({[':
            stack.append(char)
        elif not stack or stack.pop() != pairs[char]:
            return False
    return not stack

Implementing a queue with two stacks is a popular question: push onto one stack; when you need to pop, if the “pop stack” is empty, dump everything from the “push stack” into it (which reverses the order), then pop from there. Each element moves between stacks at most once, so it’s amortized O(1) per operation even though a single dump looks like O(n).

A monotonic stack keeps elements in increasing or decreasing order and powers “next greater element” style problems:

def next_greater_element(nums):
    result = [-1] * len(nums)
    stack = []  # indices, values decreasing
    for i, num in enumerate(nums):
        while stack and nums[stack[-1]] < num:
            result[stack.pop()] = num
        stack.append(i)
    return result

For [2, 1, 4, 3] this returns [4, 4, -1, -1]. Each index is pushed and popped at most once, so it’s O(n) despite the nested-looking while.

Hash Maps and Sets

Hashing converts a key into an array index via a hash function, giving O(1) average lookup, insert, and delete. A hash map stores key-value pairs; a hash set stores unique keys only. If you can only master one data structure beyond arrays, make it hash maps — many problems that look O(n²) become O(n) once you add one.

Two Sum (LeetCode #1) is the canonical example. For each number, check whether its complement (target minus the number) has already been seen:

def two_sum(nums, target):
    seen = {}  # value -> index
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

O(n) time, O(n) space — one pass instead of the O(n²) brute force of checking every pair.

Group Anagrams (LeetCode #49) sorts each word’s characters to build a shared key:

def group_anagrams(strs):
    groups = {}
    for s in strs:
        key = "".join(sorted(s))
        groups.setdefault(key, []).append(s)
    return list(groups.values())

O(n·k log k) where k is the max word length — the sort dominates.

Collisions happen when two keys hash to the same slot. Most implementations use chaining (each slot holds a small list) or open addressing (probe for the next free slot). You rarely implement this yourself, but it explains why the worst case is O(n): if every key collides, the hash map degrades to a linked list. This is rare with a decent hash function, but worth mentioning in an interview to show you understand the trade-off.

Part 3: Trees, Heaps, Graphs, Tries, and Union-Find

Trees

A tree is nodes connected by edges, with one root and no cycles. A binary tree node has at most two children:

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

Four traversals matter. Inorder (left, root, right) visits a BST in sorted order. Preorder (root, left, right) is used to copy or serialize a tree. Postorder (left, right, root) is used to delete a tree bottom-up. Level-order (BFS with a queue) visits level by level:

from collections import deque

def level_order(root):
    if root is None:
        return []
    result, queue = [], deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.value)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)
    return result

A binary search tree (BST) adds one rule: every left subtree is smaller, every right subtree is larger. This lets search, insert, and delete run in O(log n) on a balanced tree — but O(n) on a skewed one that degenerates into a linked list. Self-balancing trees (AVL, Red-Black) maintain balance automatically; Kotlin/Java’s TreeMap uses one internally. Python’s standard library has no built-in sorted map — use the third-party sortedcontainers, or bisect on a list for simple cases.

Validating a BST has a classic trap: checking only that a node’s immediate children are smaller/larger is not enough — every node in the left subtree must be smaller than the root, not just the direct child. The fix is to pass down a valid (min, max) range and narrow it at each step:

def is_valid_bst(root):
    def validate(node, low, high):
        if node is None:
            return True
        if node.value <= low or node.value >= high:
            return False
        return (validate(node.left, low, node.value) and
                validate(node.right, node.value, high))
    return validate(root, float('-inf'), float('inf'))

Heaps and Priority Queues

A heap is a complete binary tree satisfying the heap property: in a min-heap, every parent is ≤ its children, so the root is always the smallest. Because it’s a complete tree, it can be stored in a plain array with index math instead of pointers: parent of i is (i-1)//2, children are 2i+1 and 2i+2.

Insert appends to the end then bubbles up (swap with parent while smaller) — O(log n). Extracting the min swaps the root with the last element, removes it, then bubbles down (swap with the smaller child while larger) — O(log n). Peek is O(1). Building a heap from an unsorted array via heapify is O(n) — faster than inserting elements one at a time (O(n log n)), because most nodes near the bottom need little or no bubbling.

You rarely hand-roll a heap in an interview — use Python’s heapq (min-heap by default; negate values for a max-heap):

import heapq

def find_kth_largest(nums, k):
    min_heap = nums[:k]
    heapq.heapify(min_heap)
    for num in nums[k:]:
        if num > min_heap[0]:
            heapq.heapreplace(min_heap, num)
    return min_heap[0]

The trick behind Kth Largest Element (LeetCode #215) and Top K Frequent Elements (#347): keep a min-heap of size k. Anything smaller than the heap’s root can’t be in the top k, so it never needs to enter. This is O(n log k) instead of sorting the whole array at O(n log n).

Graphs

A graph is vertices connected by edges, which — unlike trees — can form cycles and connect any node to any other. The two representations: an adjacency list (each vertex maps to its neighbors, O(V+E) space) and an adjacency matrix (O(V²) space, O(1) edge lookup). Interviews almost always use adjacency lists because real graphs are sparse.

BFS explores level by level with a queue and finds the shortest path in an unweighted graph:

from collections import deque

def bfs(graph, start):
    visited, queue, order = {start}, deque([start]), []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return order

DFS explores as deep as possible before backtracking, using recursion or an explicit stack — it does not guarantee the shortest path, but it’s the natural fit for exploring all paths, detecting cycles, or flood-filling a region.

Number of Islands (LeetCode #200) is the canonical grid-as-graph problem: scan the grid, and every time you find unvisited land, run DFS to sink the whole connected island:

def num_islands(grid):
    rows, cols = len(grid), len(grid[0])
    count = 0

    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == '0':
            return
        grid[r][c] = '0'  # mark visited
        dfs(r + 1, c); dfs(r - 1, c); dfs(r, c + 1); dfs(r, c - 1)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                dfs(r, c)
    return count

Topological sort orders a directed acyclic graph so every edge points forward — think “finish prerequisites before the course.” Kahn’s algorithm does it with BFS: repeatedly remove nodes with no remaining incoming edges.

from collections import deque

def topological_sort(num_nodes, edges):
    graph = {i: [] for i in range(num_nodes)}
    in_degree = {i: 0 for i in range(num_nodes)}
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1

    queue = deque(n for n in in_degree if in_degree[n] == 0)
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    return order if len(order) == num_nodes else []  # empty = cycle detected

If the result has fewer nodes than the graph, there’s a cycle — no valid ordering exists. This is exactly LeetCode #207, Course Schedule.

Tries

A trie (prefix tree) stores strings one character per node, so shared prefixes share memory. It’s the data structure behind autocomplete and spell-check.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word:
            node = node.children.setdefault(char, TrieNode())
        node.is_end = True

    def search(self, word):
        node = self._find(word)
        return node is not None and node.is_end

    def starts_with(self, prefix):
        return self._find(prefix) is not None

    def _find(self, text):
        node = self.root
        for char in text:
            if char not in node.children:
                return None
            node = node.children[char]
        return node

Every operation is O(m), where m is the word or prefix length — independent of how many words the trie holds. That’s the key trade-off versus a hash set: a hash set matches exact strings in O(m) average too, but cannot answer “does anything start with this prefix” without scanning every key. A trie answers that in O(m) by construction, at the cost of more memory (one node per character instead of one entry per word).

Union-Find

Union-Find (Disjoint Set Union) answers one question fast: are these two elements in the same group? It supports find(x) (which group’s root does x belong to) and union(x, y) (merge two groups).

The naive version — each element points to a parent, walk up to find the root — can degrade to a linked list (O(n) per find). Two optimizations fix this. Path compression makes every node on a find path point directly to the root, flattening future lookups. Union by rank attaches the shorter tree under the taller one, keeping trees balanced.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.count = n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # path compression
        return self.parent[x]

    def union(self, x, y):
        root_x, root_y = self.find(x), self.find(y)
        if root_x == root_y:
            return False
        if self.rank[root_x] < self.rank[root_y]:
            root_x, root_y = root_y, root_x
        self.parent[root_y] = root_x
        if self.rank[root_x] == self.rank[root_y]:
            self.rank[root_x] += 1
        self.count -= 1
        return True

With both optimizations, the amortized time per operation is O(α(n)) — the inverse Ackermann function, which grows so slowly it’s effectively O(1) for any n you’ll ever see. Number of Connected Components (LeetCode #323) is just union on every edge, then read count. Redundant Connection (#684) processes edges in order and returns the first one where union returns False — that edge connects two nodes already in the same group, which means it creates a cycle.

Rule of thumb: use Union-Find when edges arrive one at a time and you need connectivity answers as you go. Use BFS/DFS when you need shortest paths or a one-time traversal of a static graph.

Part 4: Core Algorithm Techniques

Sorting

Sorting unlocks other techniques — binary search needs sorted input, and duplicate detection becomes a simple neighbor-comparison on sorted data.

Merge sort divides, sorts each half, merges — guaranteed O(n log n), stable, but O(n) extra space:

def merge_sort(nums):
    if len(nums) <= 1:
        return nums
    mid = len(nums) // 2
    left, right = merge_sort(nums[:mid]), merge_sort(nums[mid:])
    result, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    return result + left[i:] + right[j:]

Quick sort partitions around a pivot and sorts in place — usually faster in practice due to cache locality, but O(n²) worst case if the pivot is consistently bad (e.g. always picking the first element on already-sorted input). Randomizing the pivot avoids that.

Counting sort beats comparison sorts entirely when values are integers in a small known range [0, k]: tally counts, then rebuild the array — O(n + k), no comparisons at all.

Default advice for interviews: use your language’s built-in sort (Python’s Timsort — a merge/insertion hybrid, stable, O(n log n)) unless the question specifically asks you to implement one.

Binary Search

Binary search cuts the search space in half every step: O(log n) instead of O(n).

def binary_search(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2  # avoid overflow
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

left + (right - left) // 2 instead of (left + right) // 2 avoids integer overflow in languages with fixed-size integers (Kotlin, Go, Java, C++). Python integers are arbitrary precision, so it isn’t strictly necessary there — but it’s a good habit that costs nothing.

Two templates prevent off-by-one bugs. Template 1 (while left <= right) finds an exact match. Template 2 (while left < right) finds a boundary — the first element satisfying some condition:

def lower_bound(nums, target):
    left, right = 0, len(nums)
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid
    return left

Mixing the two templates is the most common cause of infinite loops or off-by-one errors.

Binary search on the answer is the technique that surprises people the first time they see it: instead of searching an array, search a range of possible answers, checking feasibility at each midpoint. Koko Eating Bananas (LeetCode #875) — find the minimum eating speed to finish all piles within h hours:

import math

def min_eating_speed(piles, h):
    left, right = 1, max(piles)
    while left < right:
        mid = left + (right - left) // 2
        hours_needed = sum(math.ceil(pile / mid) for pile in piles)
        if hours_needed <= h:
            right = mid       # mid works, try slower
        else:
            left = mid + 1    # mid too slow, need faster
    return left

Recognize this pattern whenever a problem asks for the “minimum of maximum” or “maximum of minimum,” or when a monotonic property holds (if speed k works, every speed faster than k also works).

Rotated sorted array search relies on the insight that at least one half is always properly sorted, so you can tell which half to discard by comparing nums[left] to nums[mid].

Two Pointers and Sliding Window

Two pointers turn many O(n²) brute-force scans into O(n).

Converging pointers start at both ends and move inward — used above for two-sum-on-sorted-array. Container With Most Water (LeetCode #11) uses the same shape: always move the pointer at the shorter line, since keeping it can never produce a better answer.

Same-direction pointers (slow/fast) remove duplicates from a sorted array in place:

def remove_duplicates(nums):
    if not nums:
        return 0
    slow = 0
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
    return slow + 1

Sliding window (fixed size) maintains a running calculation as a window of size k slides across an array — add the entering element, remove the leaving one, no need to recompute the whole window.

Sliding window (variable size) expands the right edge and shrinks the left edge whenever a constraint is violated. Longest Substring Without Repeating Characters (LeetCode #3):

def length_of_longest_substring(s):
    seen = set()
    left = result = 0
    for right in range(len(s)):
        while s[right] in seen:
            seen.remove(s[left])
            left += 1
        seen.add(s[right])
        result = max(result, right - left + 1)
    return result

O(n) time — each character enters and leaves the window at most once, even though there’s a nested while.

Recursion and Backtracking

Every recursive function needs a base case (stops recursion) and a recursive case (calls itself on a smaller problem). Each call adds a frame to the call stack — n calls means O(n) space, and too many means a stack overflow.

Backtracking is recursion with undo: try a choice, recurse, and if it doesn’t pan out, undo it and try the next option. Three steps: choose, explore, undo.

def subsets(nums):
    result = []

    def backtrack(start, path):
        result.append(path[:])  # every path is a valid subset
        for i in range(start, len(nums)):
            path.append(nums[i])   # choose
            backtrack(i + 1, path) # explore
            path.pop()             # undo

    backtrack(0, [])
    return result

O(n · 2ⁿ) — there are 2ⁿ subsets, and copying each costs O(n). Permutations follow the same shape but track a used array instead of a start index, since order matters and every element must appear exactly once (O(n · n!)). N-Queens adds validity checks (no shared column or diagonal) before choosing each position.

Pruning skips branches that can’t possibly lead to a valid answer — sorting candidates first, for instance, lets you break out of a loop the moment a candidate is too large, instead of checking every remaining one.

Two mistakes are almost universal here: forgetting the base case (infinite recursion), and saving a reference to the path instead of a copy (result.append(path) instead of result.append(path[:])) — the path keeps mutating after you thought you saved it.

Dynamic Programming

DP is recursion with memory. It applies when two conditions hold: overlapping subproblems (the same subproblem is solved repeatedly) and optimal substructure (the best overall solution is built from the best solutions to subproblems).

Four steps solve any DP problem: 1) write the brute-force recursive solution first — don’t skip this. 2) Add a cache (memoization) — this is top-down DP. 3) Convert to filling a table iteratively from the smallest subproblem up — this is bottom-up DP. 4) Optimize space if each state only depends on a few previous states.

# Climbing Stairs — 1 or 2 steps at a time, how many ways to the top?
def climb_stairs(n):
    if n <= 2:
        return n
    prev2, prev1 = 1, 2
    for _ in range(3, n + 1):
        prev2, prev1 = prev1, prev1 + prev2
    return prev1

State: dp[i] = ways to reach stair i. Recurrence: dp[i] = dp[i-1] + dp[i-2]. Space-optimized from O(n) to O(1) because each step only needs the previous two values.

House Robber: dp[i] = max(dp[i-1], dp[i-2] + nums[i]) — either skip house i, or rob it and add to the best result two houses back (since adjacent houses can’t both be robbed).

Coin Change — fewest coins to make an amount — is the unbounded-knapsack shape:

def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], dp[i - coin] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

Longest Common Subsequence, a 2D string DP, compares two strings character by character:

def lcs(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i - 1] == text2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

DP is hard because defining the state isn’t obvious and the recurrence needs real insight — that’s exactly why step 1 (brute force first) matters: you can’t optimize a recurrence you haven’t written down.

Greedy Algorithms

A greedy algorithm makes the locally best choice at each step and never reconsiders it. It’s simpler and faster than DP, but only correct when the greedy choice is provably optimal.

Where greedy fails: making change with coins [1, 3, 4] for target 6 — greedy takes 4+1+1 (3 coins), but the optimal is 3+3 (2 coins). This is exactly why general coin change needs DP, not greedy — the local best choice (take the biggest coin) doesn’t always lead to the global best.

Interval scheduling — maximum non-overlapping intervals — is the classic case where greedy does work: always pick the interval that ends earliest, since that leaves the most room for what comes after.

def max_non_overlapping(intervals):
    intervals.sort(key=lambda x: x[1])  # sort by end time
    count, last_end = 0, float('-inf')
    for start, end in intervals:
        if start >= last_end:
            count += 1
            last_end = end
    return count

Jump Game — can you reach the last index, where each element is the max jump length from that position — tracks the farthest reachable position and fails fast if the current index ever exceeds it:

def can_jump(nums):
    farthest = 0
    for i, num in enumerate(nums):
        if i > farthest:
            return False
        farthest = max(farthest, i + num)
    return True

To convince yourself (and an interviewer) that a greedy approach is correct, use an exchange argument — show that swapping the greedy choice for any other choice never improves the result — or just try to construct a counterexample; if you can’t find one, it probably works. When in doubt, test the greedy approach against brute force on a small input before committing to it.

BFS/DFS Deep Dive

Beyond basic traversal, two patterns come up constantly. Dijkstra’s algorithm finds shortest paths in a weighted graph with non-negative edges, using a min-heap instead of a plain queue:

import heapq

def dijkstra(graph, start):  # graph: {node: [(neighbor, weight), ...]}
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    heap = [(0, start)]
    while heap:
        dist, node = heapq.heappop(heap)
        if dist > distances[node]:
            continue  # a shorter path was already found
        for neighbor, weight in graph[node]:
            new_dist = dist + weight
            if new_dist < distances[neighbor]:
                distances[neighbor] = new_dist
                heapq.heappush(heap, (new_dist, neighbor))
    return distances

O((V+E) log V) with a binary heap. Dijkstra does not work with negative edge weights — use Bellman-Ford for that case.

Multi-source BFS starts from several nodes at once instead of one — enqueue all sources before the loop begins. Rotting Oranges (LeetCode #994) enqueues every already-rotten orange, then spreads outward level by level, tracking elapsed time.

Cycle detection in a directed graph uses three-color DFS: unvisited, in-progress (currently on the recursion stack), and done. Seeing an in-progress node again means you’ve found a back edge — a cycle.

def has_cycle_directed(graph, n):
    color = [0] * n  # 0=unvisited, 1=in-progress, 2=done

    def dfs(node):
        color[node] = 1
        for neighbor in graph[node]:
            if color[neighbor] == 1:
                return True
            if color[neighbor] == 0 and dfs(neighbor):
                return True
        color[node] = 2
        return False

    return any(color[i] == 0 and dfs(i) for i in range(n))

Part 5: Problem Patterns

Once you know the individual data structures and algorithms, the real interview skill is recognizing which pattern a new problem matches. Analyses of real interview question sets consistently find that a large majority — often cited as 70-90% — map to about 10 core patterns.

The Ten Core Patterns

Recognition flowchart: sorted (or sortable) input → two pointers or binary search. Contiguous subarray/substring → sliding window. Grid/tree/graph → BFS (shortest path) or DFS (explore everything). Min/max/count with overlapping subproblems → DP. All combinations → backtracking. K largest/smallest → heap. Intervals → sort + merge. “Next greater/smaller” → monotonic stack. Grouping or connectivity → Union-Find.

The habit that matters most: spend the first two or three minutes of any interview problem identifying the pattern before writing code. Memorizing “Two Sum uses a hash map” only solves Two Sum. Learning “hash map trades space for O(1) lookup to cut O(n²) to O(n)” solves dozens of problems.

String-Specific Patterns

Strings combine several patterns above. Two pointers check palindromes and reverse in place. Sliding window solves “find all anagrams” — maintain a running character count and compare it to the target’s count as the window slides. Hash map frequency counting groups anagrams, as shown in Part 2. For pattern matching inside a string, the KMP algorithm finds a substring in O(n + m) by precomputing a “failure function” that avoids re-scanning characters on a mismatch — you rarely implement KMP from scratch in an interview, but knowing what it does (and that Python/Kotlin/Go’s built-in string search does something at least this efficient) signals depth.

Tree and Graph-Specific Patterns

Beyond basic traversal, five shapes recur constantly:

Diameter (longest path between any two nodes) computes height bottom-up while tracking the best left + right seen so far, not just the final height:

def diameter_of_binary_tree(root):
    diameter = 0
    def height(node):
        nonlocal diameter
        if not node:
            return 0
        left, right = height(node.left), height(node.right)
        diameter = max(diameter, left + right)
        return 1 + max(left, right)
    height(root)
    return diameter

Lowest common ancestor (LCA) has a fast path for a BST — walk down, go left if both targets are smaller, right if both are larger, and stop at the first split. For a general binary tree, use plain recursion: a node is the LCA if it is one of the targets, or if the targets are found on both its left and right subtrees.

Path Sum III (count paths summing to a target, not required to start at the root) reuses the prefix-sum technique from arrays, applied along a tree path — track running sums in a hash map as you descend, and undo the increment when backtracking out of a subtree, exactly like the choose/explore/undo shape from backtracking.

Topological sort was covered fully in Part 3 — it’s also the answer to “course ordering” and “build order” problems whenever they appear disguised as tree/graph questions.

Union-Find for dynamic connectivity — also covered in Part 3 — is the right call whenever edges arrive one at a time (as in Redundant Connection) rather than being given as a complete, static graph.

DP Patterns

DP problems fall into six recurring shapes, and naming the shape usually reveals the recurrence:

Knapsack — 0/1 (each item used once) or unbounded (each item reusable, like coins). Iterate the capacity loop backward for 0/1 knapsack to avoid reusing an item twice in the same pass; iterate forward for unbounded, since reuse is the point.

String DP compares two strings character by character in a 2D table. Edit Distance is the sharpest example — dp[i][j] is the minimum operations to convert the first i characters of one string into the first j characters of another:

def min_distance(word1, word2):
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i-1] == word2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
    return dp[m][n]

Grid DP moves through a 2D grid, each cell depending on its top/left neighbors (Unique Paths, Minimum Path Sum). Interval DP computes the best result over a range [i, j] by trying every split point k between them (Burst Balloons) — O(n³), since there are O(n²) ranges and O(n) split points each.

State machine DP tracks multiple parallel states per position — “holding a stock” vs. “not holding,” with a cooldown state in between:

def max_profit_with_cooldown(prices):
    if len(prices) < 2:
        return 0
    hold, sold, rest = -prices[0], 0, 0
    for price in prices[1:]:
        hold, sold, rest = max(hold, rest - price), hold + price, max(rest, sold)
    return max(sold, rest)

The pattern-recognition question for DP specifically: single array depending on previous elements → linear DP. Choosing items under a capacity → knapsack. Two strings compared character by character → string DP. Grid with directional movement → grid DP. A range with a split point → interval DP. Multiple parallel states at each position → state machine DP.

Gotchas That Catch Everyone Once

Off-by-one errors in binary search. Mixing the left <= right template (exact match) with the left < right template (boundary finding) is the single most common source of infinite loops and wrong answers. Pick a template per problem and stick to it.

Modifying a list while iterating it. Removing an element from a Python list mid-for loop skips the next element, because indices shift underneath the iterator. Either iterate a copy, iterate backward, or build a new list.

Recursion without a base case, or with a wrong one. No base case means infinite recursion until a stack overflow. A wrong base case (off-by-one) silently corrupts the entire DP table or recursion result, since everything downstream builds on it.

Forgetting to mark nodes visited in a graph with cycles. Without a visited set, BFS/DFS loops forever the moment there’s a cycle. This is the most common bug in graph problems that otherwise look correct.

Greedy where DP is required. If you can’t construct a proof (or at least fail to find a counterexample after trying), don’t trust a greedy approach — test it against brute force on a small input first. The [1, 3, 4] coin example above is the textbook counterexample.

Saving a reference instead of a copy in backtracking. result.append(path) in Python appends a reference to the same mutable list, which keeps changing as backtracking continues. Use result.append(path[:]) (or path.toList() in Kotlin) to snapshot the current state.

Integer overflow in binary search’s midpoint. (left + right) // 2 can overflow in fixed-width-integer languages like Kotlin, Go, or Java on very large inputs. left + (right - left) // 2 is the safe form. Python’s arbitrary-precision integers don’t have this problem, but the habit costs nothing and transfers to every other language.

Where to Go From Here

You now have the full toolkit: complexity analysis, every core data structure, the major algorithm techniques, and the patterns that tie them together. Two things turn this knowledge into interview performance: spaced, deliberate practice rather than random grinding, and knowing where DSA stops mattering — some interview loops weight system design far more heavily once you’re past a certain level.

• How to Practice DSA Effectively — a study plan, not just a problem list
• Complete DSA Cheat Sheet — every data structure, algorithm, and template on one page for quick review before an interview
• System Design vs DSA — how to split your prep time by seniority level
• Python Tutorial: From Zero to a Real Project — if the Python syntax here was new to you