Data Structures & Algorithms — Complete Course

Unit 1: Unit 1 — Arrays, Strings & Hashing

Arrays are the foundation. Master the classic window/pointer patterns: sliding window for contiguous subarray problems, two pointers for sorted/paired problems, and prefix sums to turn range-sum queries into O(1). Hash maps give O(1) lookup — they trade space for time, so always say the space cost. Strings are arrays of characters; many string problems are really two-pointer or hashing problems in disguise.

Teach: Hash-maps turn lookups into O(1)

When a problem says find a pair, duplicate or element whose complement exists, reach for a hash map (dict) or hash set. The critical insight: you trade O(n) memory to make each lookup O(1) instead of O(n). Always state both time AND space complexity. Worked example — Two Sum: Input [2,7,11,15], target 9. Step 1: element 2. Complement 9-2=7 not seen yet. Store seen[2]=0. Step 2: element 7. Complement 9-7=2 IS in seen (index 0). Answer indices [0,1]. Complexity: O(n) time, O(n) space. Order matters: only one pass is needed.

Teach: Sliding window for contiguous subarrays

For 'maximum sum/ length of a subarray/substring that satisfies a constraint', the sliding window is usually O(n): grow the window by extending the right edge; shrink from the left while the constraint is violated; track the best answer at each valid state. Fixed window (length k): slide and recompute the sum by adding right and removing left — O(n) total, no nested loop. Variable window (any valid length): expand right until constraint breaks, then move left until valid again — each element enters and leaves once, so O(n).

Teach: Prefix sums for O(1) range queries

Build prefix[i] = sum of arr[0..i-1], then range sum(arr[l..r]) = prefix[r+1] - prefix[l] in O(1). Space cost O(n). This is a pure open-sesame trick: any problem asking many range sums is flirting with prefix sums. Same idea with prefix products for range products (watch out for zeros).

Teach: Two pointers on sorted arrays

Sorted array + pair/duplicate/container problem ⇒ two pointers. Place one at 0 and one at n-1; move the pointer that gets you closer to the target. Because the array is sorted, each move provably keeps all better candidates reachable — that is what makes the O(n) bound safe. Container With Most Water: area = distance × min height; move the shorter side.

Exercises

• Two Sum — Given an array of integers and a target, return the indices of the two numbers that add up to target. You may not use the same element twice.
• Best Time to Buy and Sell Stock — Given daily prices, choose one day to buy and a later day to sell for maximum profit. Return 0 if no profit possible.
• Contains Duplicate — Return true if any value appears at least twice in the array.
• Maximum Subarray (Kadane) — Find the contiguous subarray with the largest sum and return that sum (array may contain negatives).
• Longest Substring Without Repeating Characters — Return the length of the longest substring without repeating characters.
• Product of Array Except Self — Return an array where output[i] is the product of all elements except nums[i], WITHOUT using division, in O(n).

Practice problems

• Two Sum
• Best Time to Buy and Sell Stock
• Contains Duplicate
• Product of Array Except Self
• Maximum Subarray (Kadane)
• Longest Substring Without Repeating Characters
• Valid Anagram
• Container With Most Water
• 3Sum
• Group Anagrams

Unit 2: Unit 2 — Linked Lists

Linked lists test pointer manipulation and edge-case discipline (head/tail, empty, one node). The three must-have techniques: (1) the two-pointer runner for finding the middle or Nth-from-end, (2) reversing a list iteratively with prev/curr/next, and (3) a dummy head node to avoid special-casing head removal. Many 'merge' problems are just pointer walks.

Teach: Iterative reversal in one pass

Reversal is the #1 linked-list warm-up and shows pointer hygiene. Task: reverse 1 → 2 → 3 → None. State: prev=None, curr=head(1), next=None. Iteration 1: save next=2; curr.next=prev(None); prev=curr(1); curr=next(2). Iteration 2: next=3; curr.next=prev(1); prev=2; curr=3. Iteration 3: next=None; curr.next=prev(2); prev=3; curr=None. Done. Return prev (3) as the new head. O(n) time, O(1) space. Edge cases: empty list, single node.

Teach: Dummy head removes edge-case branching

Many 'remove/insert' problems force special handling at the head. A dummy node before head makes every node a 'middle' node with a uniform prev.next update. Remove Nth node from end: compute len, walk to node (len - n - 1) in ONE pass with a dummy; dummy.next -> dummy.next.next. O(n) time, O(1) space. Always ask: must I handle head-removal specially?

Exercises

• Reverse Linked List — Reverse a singly linked list iteratively and return the new head.
• Linked List Cycle — Return true if the linked list has a cycle (Floyd's tortoise-and-hare).
• Merge Two Sorted Lists — Merge two sorted linked lists into one sorted list.
• Middle of the Linked List — Return the middle node. If two middles, return the second one.
• Remove Nth Node From End of List — Remove the n-th node from the end and return the head. One pass.
• Intersection of Two Linked Lists — Return the node where two singly linked lists intersect, or None.

Practice problems

• Reverse Linked List
• Linked List Cycle
• Merge Two Sorted Lists
• Middle of the Linked List
• Remove Nth Node From End of List
• Intersection of Two Linked Lists
• Palindrome Linked List

Unit 3: Unit 3 — Trees & Binary Search Trees

Trees are the single most common interview topic. Master recursive traversal (pre/in/post) and level-order (BFS via queue). On a BST, in-order gives a sorted sequence, and search/insert/delete are O(h). The height of a balanced tree is ~log n — that's why BSTs are fast. 'Validate BST', 'lowest common ancestor', and 'max depth' are the warm-ups; path-sum and diameter problems test whether you can thread a global answer through recursion.

Teach: Recursive traversal is a template

Every traversal is the same skeleton with a different visit position. def walk(node): if not node: return visit(node) # pre-order walk(node.left) walk(node.right) Move visit(node) after the left call for in-order (=> sorted on a BST); after both calls for post-order. O(n) time, O(h) stack space. Level-order (BFS): queue, pop front, enqueue children.

Teach: BST in-order is sorted — use the invariant

A BST keeps left < node < right everywhere. So: - In-order DFS yields sorted output — the check for 'is this a BST' must carry a (lo, hi) bound because children constrain their ancestor direction, not just the immediate parent. - Search/insert/delete are O(h) ~ O(log n) balanced, O(n) skewed. validate(node, lo=-inf, hi=+inf): node.val must be in (lo, hi); recurse left with hi=node.val, right with lo=node.val.

Exercises

• Maximum Depth of Binary Tree — Return the number of nodes along the longest root-to-leaf path.
• Invert Binary Tree — Swap every left and right child, return the root.
• Validate Binary Search Tree — Return true if the tree is a valid BST (left < node <= right? use strict for <).
• Binary Tree Level Order Traversal — Return level-order values grouped by level.
• Lowest Common Ancestor of a Binary Tree — Given roots p and q (each present), return their lowest common ancestor.
• Diameter of Binary Tree — Return the length (in edges) of the longest path between any two nodes.
• Binary Tree Maximum Path Sum — Return the maximum path sum — a path can start and end at any nodes.

Practice problems

• Maximum Depth of Binary Tree
• Same Tree / Invert Binary Tree
• Validate Binary Search Tree
• Binary Tree Level Order Traversal
• Lowest Common Ancestor of a BST
• Binary Tree Maximum Path Sum
• Diameter of Binary Tree

Unit 4: Unit 4 — Graphs: BFS, DFS, Topological Sort, Shortest Path

Graphs appear constantly at the Staff bar. BFS gives shortest path in unweighted graphs and is the natural tool for 'number of islands', word-ladder, and level-order grid problems. DFS works for connectivity and backtracking. Topological sort (Kahn's algorithm) handles dependency ordering — very relevant to build systems and task scheduling. Dijkstra (with a min-heap) is the weighted shortest path; union-find is the fast way to handle dynamic connectivity / number-of-connected-components.

Teach: BFS vs DFS — pick by what you need

BFS (queue) finds the SHORTEST path in unweighted graphs and processes level-by-level (islands, word ladder, grid distances). Mark visited when ENQUEUING to avoid duplicate work. DFS (stack/recursion) explores one branch fully — good for connectivity, backtracking, topological DFS. Mark visited when visiting. Grid problems: the 4-neighbor (or 8-neighbor) moves are just offset tuples; keep bounds checks inside the traversal.

Teach: Topological sort — Kahn's algorithm

For dependency ordering (courses, build systems): count in-degrees, seed the queue with 0-in-degree nodes, pop and decrement neighbours, append to order. If order length < node count → a cycle exists (no valid ordering). O(V+E). 'Course Schedule' asks canFinish (detect cycle); 'Course Schedule II' wants the actual order.

Exercises

• Number of Islands — Count connected groups of '1' in a 2D grid (4-directional).
• Course Schedule — Return true if all courses can be finished given prerequisite pairs.
• Course Schedule II — Return a valid course ordering, or [] if impossible.
• Word Ladder — Shortest transformation length from beginWord to endWord, one letter changed per step, each word in wordList.
• Network Delay Time (Dijkstra) — Return the time for all nodes to receive a signal, or -1 if unreachable.
• Number of Connected Components in an Undirected Graph — Return the number of connected components given n nodes and edges.

Practice problems

• Number of Islands
• Clone Graph
• Course Schedule (topological sort)
• Course Schedule II
• Pacific Atlantic Water Flow
• Word Ladder
• Network Delay Time (Dijkstra)
• Number of Connected Components in an Undirected Graph

Unit 5: Unit 5 — Heaps / Priority Queues

A heap gives you the min/max element in O(log n) — that's the tool for 'top K' and 'Kth largest' problems. The classic trick is a min-heap of size K for top-K-largest (keep the K largest, eject the smallest). Priority queues are also the engine of Dijkstra and greedy scheduling. Always state: 'I use a heap so each push/pop is O(log k), and the answer is the root, O(1) to read.'

Teach: Min-heap of size K = top-K-largest

To keep the K LARGEST values with O(log k) per push and O(1) to read the answer, maintain a MIN-heap of size K: push each value; if size > K, pop the smallest. The root is the K-th largest (your answer). Why min-heap and not max? The min-heap lets you eject the smallest, keeping the largest K. 'Top K Frequent Elements' = heap keyed by frequency.

Teach: Two heaps for streaming median

Split data into a max-heap (lower half) and a min-heap (upper half). Insert to the appropriate side, rebalance so sizes differ by <= 1. Median = lower.max if sizes differ else (lower.max + upper.min)/2. O(log n) per insertion. 'Find Median from Data Stream' is the classic.

Exercises

• Kth Largest Element in an Array — Return the k-th largest element in an unsorted array.
• Top K Frequent Elements — Return the k most frequent elements.
• Merge K Sorted Lists — Merge k sorted linked lists into one sorted list.
• Find Median from Data Stream — Design a class that supports addNum and findMedian in O(log n) each.
• Task Scheduler — Return the least number of units of time to finish all tasks with a cooldown of n between same tasks.
• K Closest Points to Origin — Return the k closest points to the origin by Euclidean distance.

Practice problems

• Kth Largest Element in an Array
• Top K Frequent Elements
• Merge K Sorted Lists
• Find Median from Data Stream
• Task Scheduler
• K Closest Points to Origin

Unit 6: Unit 6 — Dynamic Programming

DP is the highest-yield hard topic. The process: (1) define the state f(i) — what you're computing; (2) write the recurrence — how f(i) depends on earlier states; (3) set the base cases; (4) fill bottom-up (or memoize top-down). The most common patterns: 1-D (climbing stairs, house robber, LIS), 2-D grid (unique paths), subsequence (LCS), and knapsack (choose/subset with capacity). Always give the time complexity as states × work-per-state.

Teach: The DP recipe (state → recurrence → base → order)

1. STATE: define f(i) precisely — what you are computing at step i. 2. RECURRENCE: how f(i) depends on earlier states (include/exclude, min over predecessors...). 3. BASE: seed the simplest cases. 4. ORDER: fill bottom-up (loop) or top-down (memoized recursion). 5. COMPLEXITY: states × work-per-state. Always state it. Climbing stairs: f(i) = f(i-1) + f(i-2), f(0)=1, f(1)=1 -> O(n) time, O(1) space rolling.

Teach: Knapsack = include-or-exclude with capacity

'Can we pick a subset summing to target?' (Partition Equal Subset Sum, Coin Change II): dp[j] = whether value j is reachable. For each item, iterate capacities DESCENDING to use items once: dp[j] |= dp[j - item]. Classic 0/1 knapsack: dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight_i] + value_i).

Exercises

• Climbing Stairs — Ways to climb n stairs taking 1 or 2 steps at a time.
• House Robber — Max loot without robbing adjacent houses.
• Longest Increasing Subsequence — Length of the longest strictly increasing subsequence.
• Longest Common Subsequence — Length of longest common subsequence of two strings.
• Coin Change — Fewest coins to make amount, or -1.
• Partition Equal Subset Sum — Can you split the array into two subsets of equal sum?
• Best Time to Buy and Sell Stock with Cooldown — Max profit with a 1-day cooldown after selling.

Practice problems

• Climbing Stairs
• House Robber
• Longest Increasing Subsequence
• Longest Common Subsequence
• Unique Paths
• Coin Change
• Partition Equal Subset Sum (knapsack)
• Word Break
• Best Time to Buy and Sell Stock with Cooldown

Unit 7: Unit 7 — Binary Search & Sorting

Binary search isn't just 'find in sorted array' — it's 'search over an answer space that is monotonic'. Master the off-by-one (low/high/mid invariants) and the rotated-array variants. Quickselect (partition) finds the Kth element in O(n) average. Know merge sort and quicksort well enough to describe stability and complexity, and use counting sort when the range is small.

Teach: Binary search = search over a monotonic predicate

Beyond arrays, binary search works on any monotonic predicate P(k): if P(k) is true at some k, it stays true for all larger k. Then you can binary search the smallest k where P(k) holds — 'capacity', 'time', 'speed'. Invariant recipe: lo = first feasible index, hi = first infeasible; while lo < hi: mid = (lo+hi)//2; if P(mid): hi = mid else lo = mid+1. Watch off-by-one; always test empty / single / not-found cases.

Teach: Rotated sorted array — find the pivot implicitly

In a rotated sorted array, one half is always sorted. Compare nums[mid] to nums[lo]: if sorted on the left, check membership in that range; else search the right. This gives O(log n) 'Search in Rotated Sorted Array'.

Exercises

• Binary Search — Return index of target in a sorted array or -1.
• First and Last Position of Element in Sorted Array — Return [first, last] index of target.
• Search in Rotated Sorted Array — Search target in a rotated sorted array of distinct values, O(log n).
• Find Minimum in Rotated Sorted Array — Return the minimum of a rotated sorted array of distinct values.
• Search a 2D Matrix — Search in a row- and column-sorted matrix.
• Koko Eating Bananas (binary search on answer) — Smallest eating speed k so Koko eats all bananas within h hours.

Practice problems

• Binary Search
• First and Last Position of Element in Sorted Array
• Search in Rotated Sorted Array
• Find Minimum in Rotated Sorted Array
• Kth Largest Element (quickselect)
• Search a 2D Matrix

Unit 8: Unit 8 — Recursion & Backtracking

Backtracking is 'try, then undo'. The skeleton: a recursive helper that builds a candidate, explores, then removes the last choice (pruning). Combination/permutation/subset problems are the canonical set. The complexity is usually O(branching^depth), so pruning matters. State it honestly and show you can cut branches.

Teach: The backtracking skeleton (try → recurse → undo)

def bt(path, options): if goal(path): record(path); return for choice in options: path.append(choice) # try bt(path, options - {choice}) # recurse path.pop() # undo Subsets: include/exclude each element. Combinations: choose with a start index. Permutations: full option set each level, skip used. Prune when the partial candidate cannot lead to a solution (N-Queens).

Exercises

• Subsets — Return all subsets of a distinct-integer array.
• Combinations — All combinations of k numbers out of 1..n.
• Permutations — All orderings of array (distinct).
• Generate Parentheses — All well-formed parentheses of n pairs.
• N-Queens — All ways to place n queens so none attack.
• Letter Combinations of a Phone Number — All letter combos for a digits string (e.g. '23').

Practice problems

• Subsets
• Combinations
• Permutations
• Combination Sum
• Generate Parentheses
• Letter Combinations of a Phone Number
• N-Queens

Unit 9: Unit 9 — Greedy Algorithms

Greedy = make the locally optimal choice at each step and prove it's globally optimal (usually via exchange argument or interval scheduling). The tell: 'sort then scan', interval scheduling, and activity selection. Greedy only works when the local choice can't hurt — if a counterexample exists, it's DP instead. Say why greedy is safe for THIS problem.

Teach: Local optimal → prove global safe

Greedy picks the locally best choice and relies on an exchange argument to prove global optimality. Classic tells: sort-then-scan, interval scheduling (sort by END time), merge intervals, jump reachability. Interval scheduling: sort by end, keep the earliest-finishing non-conflicting interval — because the earliest finisher leaves the most room. If a counterexample exists, it is DP, not greedy.

Exercises

• Non-overlapping Intervals — Min intervals to remove so the rest are non-overlapping.
• Merge Intervals — Merge all overlapping intervals.
• Jump Game — Can you reach the last index given max jump at each index?
• Jump Game II — Minimum jumps to reach the last index.
• Gas Station — Return the starting station index for a complete circuit, or -1.

Practice problems

• Non-overlapping Intervals
• Merge Intervals
• Jump Game
• Jump Game II
• Gas Station
• Minimum Number of Arrows to Burst Balloons

Unit 10: Unit 10 — Two Pointers & Sliding Window

Two pointers turn O(n^2) scans into O(n): one pointer from each end (sorted-array pair problems) or a fast/slow pair (cycle detection, in-place partition). Sliding window is the 'contiguous subarray' tool — grow the right edge, shrink the left edge to restore the invariant, and the window is always a valid contiguous slice. The tell: 'longest/shortest subarray/substring with a condition' → sliding window; 'pair/triplet with a target' on sorted input → two pointers. Trapping Rain Water and Container With Most Water are the classic two-pointer hard problems.

Teach: Two pointers — shrink the search space from both ends

On sorted input, a pair-sum target can be found in O(n): start one pointer at each end; if the sum is too small, move the left pointer right; too large, move the right pointer left. Each step eliminates one candidate. The same idea powers Trapping Rain Water (track running left/right maxima) and Container With Most Water (shrink the shorter side). Fast/slow pointers detect cycles and find the middle of a list in one pass.

Teach: Sliding window — every contiguous subarray in O(n)

For 'longest/shortest contiguous subarray/substring satisfying a condition', grow the right edge to include a new element, then shrink the left edge until the invariant holds again. The window is always a valid slice, so the answer is the best window seen. Keep a frequency map for 'no repeats' or 'at most k distinct' conditions. Fixed-size windows are simpler: slide by one, add right, remove left.

Exercises

• Valid Palindrome — Check if a string is a palindrome ignoring non-alphanumerics and case.
• Two Sum II — Input Array Is Sorted — Return 1-indexed pair whose values sum to target in a sorted array.
• Trapping Rain Water — Compute total water trapped between elevation bars.
• Longest Substring Without Repeating Characters — Return length of the longest substring with all distinct characters.
• Minimum Window Substring — Return the smallest substring of s containing all chars of t (with counts).

Practice problems

• Valid Palindrome
• Two Sum II — Input Array Is Sorted
• 3Sum
• Container With Most Water
• Trapping Rain Water
• Longest Substring Without Repeating Characters
• Minimum Window Substring
• Longest Repeating Character Replacement

Unit 11: Unit 11 — Final Review & Mock Sprint

By now you've seen every core pattern. The final unit is about recall under pressure. Build a one-page cheat sheet of pattern → data structure → complexity. Then do timed mocks: 1 problem in 30–45 minutes, talking aloud, stating the brute force, then optimizing, then the complexity. Review your weak units and re-solve the problems you missed after 48h.

Teach: How to run the final mock sprint

1. Build a one-page cheat sheet: pattern → data structure → complexity. 2. Timeboxed talk-aloud mocks (30-45 min): state brute force, then optimize, then complexity. 3. After 48h, re-solve the problems you missed (spaced repetition). 4. Use DOJO practice with focus=coding at staff difficulty to simulate the real bar.

Exercises

• Recite 10 core patterns from memory — List the 10 highest-yield patterns and their canonical data structure + complexity, from memory.
• Run one timed 45-min mock — Use DOJO practice (focus=coding, difficulty=staff): solve one problem talk-aloud, then self-score on correctness/trade-offs/complexity.

Practice problems

• Re-solve 3 problems from your weakest unit, timed
• One full 45-min mock on a mixed problem set
• Recite the 10 core patterns from memory
• Run a staff-level coding mock interview in DOJO (focus = Coding)