Big Tech DSA Patterns

Problem: find the length of the longest slice of a string that has no repeated character. The brute-force way checks every possible slice (slow, O(n²)). The sliding-window trick does it in one pass by remembering where each character was last seen.

1. seen = {} is a dictionary mapping each character to the last index where we saw it. left is the start of the current window; best is the longest length found so far.
2. for right, ch in enumerate(s) walks right across the string one character at a time. enumerate hands you both the position right and the character ch.
3. if ch in seen and seen[ch] >= left asks "have we seen this char inside the current window?" If yes, we jump left to just past that old copy — the window instantly becomes duplicate-free again, without a slow inner loop.
4. seen[ch] = right records this character's new position, and best = max(best, right - left + 1) updates the answer with the current window's width (right - left + 1 is how many characters are inside).

What the output means: Prints 3 — the longest repeat-free substring of "abcabcbb" is "abc", which is 3 characters long.

Try this: Trace "abba" by hand. When the second a arrives, left must jump past the first a — this is exactly why the check is seen[ch] >= left and not just ch in seen.

Two more sliding-window classics. (a) the fixed-size window (the width never changes), and (b) the variable window that must cover a required set of characters. Same expand/shrink idea, two flavors.

1. (a) max_sum_k: to find the biggest sum of any k neighbours, don't re-add k numbers each step. Compute the first window once, then window += nums[i] - nums[i-k] — add the new number entering on the right and subtract the old one leaving on the left. Each step is O(1).
2. (b) min_window: find the shortest slice of s containing every character of t. need = Counter(t) counts how many of each character we still need; missing is how many we're short overall.
3. As hi expands the window, each needed character drops missing. When missing == 0 the window is valid, so the inner while shrinks lo from the left past any surplus characters to make the window as tight as possible.
4. Whenever a valid window is smaller than the best so far, we record it with start, end = lo, hi. At the end s[start:end] is the shortest covering slice.

What the output means: Prints 9 BANC: the best sum of 3 neighbours in [2,1,5,1,3,2] is 5+1+3=9, and the smallest window of "ADOBECODEBANC" covering "ABC" is "BANC".

Try this: For (a), print window each loop and watch it slide. For (b), the key insight is that need counts can go negative — that's the signal you have a surplus character you're allowed to drop while shrinking.

Problem: find all unique triplets in nums that sum to zero. The pattern: sort, then for each anchor run a two-pointer sweep. The only fiddly part is not reporting the same triplet twice.

1. nums.sort() sorts in place — cheap (O(n log n)) and it unlocks everything else. res collects the answer triplets.
2. for i in range(len(nums) - 2) picks each anchor. The if i > 0 and nums[i] == nums[i-1]: continue line skips duplicate anchors so we don't emit the same triplet again.
3. lo, hi = i + 1, len(nums) - 1 sets the two pointers on either end of the rest. The while lo < hi loop converges them: sum too small → lo += 1, too big → hi -= 1, exactly right → record it.
4. After recording a hit, the inner while ... nums[lo] == nums[lo-1]: lo += 1 skips over repeated values so duplicate triplets aren't produced.

What the output means: Returns a list of triplets that each sum to 0, e.g. [[-1,-1,2],[-1,0,1]], with no duplicates.

Try this: Remove the two duplicate-skipping lines and run on [-1,-1,2,0,1] — you'll get the same triplet twice. Those continue/skip lines are what interviewers check for.

Three short two-pointer classics that show the range of the pattern: (a) converging pointers on an array, (b) the pointer-flip that reverses a linked list, and (c) the fast/slow pointer pair on a linked list.

1. (a) max_area: two walls form a water container; area = width × the shorter wall. Start pointers at both ends and always move the shorter wall inward — moving the taller one could never help, so this greedy choice is safe and gives O(n).
2. (b) reverse_list: head.next, prev, head = prev, head, head.next flips one arrow and advances, all in a single line. Python evaluates the right side first, so this safely reverses the link and steps forward at once.
3. (c) middle: slow moves one node, fast moves two. When fast reaches the end, slow is exactly halfway — the fast/slow ("tortoise and hare") trick, no length count needed.

What the output means: Prints 49 — the most water the container in [1,8,6,2,5,4,8,3,7] can hold.

Try this: For (c): if fast moves twice as fast as slow, slow covers exactly half the distance by the time fast finishes. That same idea (different speeds) detects a cycle in a list — the hare laps the tortoise.

Problem: return the k most frequent numbers in a list. Count how often each appears, then keep only the top k by frequency using a heap.

1. Counter(nums) builds a dictionary of value → how many times it appears in one O(n) pass.
2. heapq.nlargest(k, counts.items(), key=lambda kv: kv[1]) asks the heap for the k items with the biggest value of kv[1] — and kv[1] is the frequency (each item is a (value, frequency) pair, so index [1] is the count).
3. The list comprehension [v for v, _ in ...] then throws away the counts and keeps just the values. The _ is Python's "I don't need this" placeholder.

What the output means: Prints [1, 2] — in [1,1,1,2,2,3], 1 appears 3 times and 2 appears twice, so those are the two most frequent.

Try this: nlargest hides the size-K heap for you. Change k to 1 and you'll get just [1], the single most common value.

Three heap patterns that go beyond simple top-K: (a) K-closest points, (b) merging K sorted lists, and (c) the elegant two-heaps trick for a running median.

1. (a) k_closest: distance to the origin is x² + y² (no square root needed — comparing squares gives the same order). heapq.nsmallest keeps the k closest in O(n log k).
2. (b) merge_k: seed the heap with the first value of each list. Each pop gives the smallest value across all lists at once; then push the next value from the list that value came from. This merges everything in sorted order.
3. (c) MedianFinder: keep two heaps — lo is a max-heap of the smaller half (stored as negatives, since Python only has min-heaps) and hi is a min-heap of the larger half.
4. add pushes into one heap and rebalances so the halves stay equal-ish. The median is then either the top of the bigger half, or the average of the two tops — an O(1) lookup.

What the output means: Prints [[-2,2],[1,3]] — the two points nearest the origin among [[1,3],[-2,2],[5,8]].

Try this: For the median: add 1,2,3 one at a time and print median() after each. The two heaps always keep the middle value(s) sitting right at their roots.

Problem: Koko eats bananas and must finish all piles within h hours; find her slowest workable speed. The answer isn't in the input array — it's a speed value we search for.

1. hours_at(speed) is the feasibility check: at a given speed, how many hours does eating every pile take? math.ceil(p / speed) rounds up because a partial pile still costs a whole hour.
2. lo, hi = 1, max(piles) bounds the search: the slowest sensible speed is 1, the fastest ever useful is the biggest pile (eating it in one hour).
3. if hours_at(mid) <= h means this speed works — so we try to go slower by setting hi = mid (keep mid as a candidate). Otherwise it's too slow to finish in time, so lo = mid + 1 forces a faster speed.
4. The loop narrows [lo, hi] until they meet on the smallest speed that still finishes in time — the answer.

What the output means: Returns the minimum integer eating speed at which all piles are finished within h hours.

Try this: Notice we never search the piles array — we search the speeds 1..max(piles). Spotting that the answer lives in a searchable, monotonic range is the whole skill here.

Problem: given a list of [start, end] ranges, merge every overlapping pair into one. The trick is entirely in the sorting: once sorted by start, a single sweep does it.

1. intervals.sort(key=lambda iv: iv[0]) sorts by the start value. After this, any interval that overlaps another must be adjacent in the list — that's the guarantee sorting buys us.
2. out = [intervals[0][:]] seeds the result with a copy of the first interval (the [:] copies so we don't mutate the input).
3. if start <= out[-1][1] checks if the current interval overlaps the previous kept one (its start is at or before the previous end). If so, extend that previous interval's end with max(...).
4. Otherwise there's a gap, so we out.append([start, end]) to begin a fresh interval.

What the output means: Prints [[1,6],[8,10]] — [1,3] and [2,6] merge into [1,6]; [8,10] stands alone.

Try this: Add [5,7] to the input. Because it overlaps [1,6] (5 ≤ 6), the answer becomes [[1,7],[8,10]] — the merge chains through automatically.

Problem: count the islands (connected groups of "1") in a grid. The approach: walk every cell, and each time you find new land, sink (flood-fill) the whole island so it's not counted again.

1. rows, cols = len(grid), len(grid[0]) grabs the grid dimensions so the helper can check boundaries.
2. sink(r, c) is a recursive flood fill. The guard 0 <= r < rows and 0 <= c < cols and grid[r][c] == "1" stops it from running off the edge or onto water/visited cells.
3. Once on land, grid[r][c] = "0" marks it visited (by turning it to water), then it recurses into all four neighbours — spreading across the whole connected island.
4. The double for loop scans every cell; each fresh "1" means one new island, so count += 1 and we sink it flat before moving on.

What the output means: Returns the number of separate islands — e.g. 3 for the grid drawn in the diagram above.

Try this: This uses DFS (recursion). The very same problem can be solved with BFS and a queue — try rewriting sink to push neighbours onto a deque instead of recursing.

Two grid-graph variations: (a) multi-source BFS (many starting points spreading at once) and (b) topological sort to detect a cycle in a dependency graph.

1. (a) oranges_rotting: rot spreads to neighbours each minute. Instead of one start, we seed all rotten oranges into the queue at once (multi-source BFS) and count fresh oranges.
2. Each queued item carries (row, col, time). Popping a cell and pushing its fresh neighbours with t+1 spreads the rot outward level by level; minutes tracks the last time stamp. If any fresh orange survives, we return -1.
3. (b) can_finish: courses with prerequisites form a directed graph. indeg[a] counts how many prerequisites course a still has; we start with everything that has zero prerequisites.
4. Each time we "take" a course we decrement its dependents' indeg; any that hit 0 join the queue. If we manage to schedule all n courses, there was no cycle — return done == n.

What the output means: Prints True False: [[1,0]] is schedulable (take 0 then 1), but [[1,0],[0,1]] is a deadlock — each needs the other.

Try this: Multi-source BFS is the "fire spreads from many points" pattern. Topological sort is the "do tasks in dependency order" pattern — and if you can't finish, you've found a cycle.

Problem: find the lowest common ancestor of nodes p and q in a binary tree. This tiny function is a masterclass in "recurse and let answers bubble up."

1. The base case if root is None or root is p or root is q: return root stops the recursion when we found a target (p or q) or ran off the bottom (None). It reports back whatever it hit.
2. left = ...(root.left, ...) and right = ...(root.right, ...) ask each subtree "did you find either target?" This is the recursion doing the work for us.
3. if left and right: return root is the key line: if both sides found something, the current node is where p and q split — so it's the LCA.
4. return left or right handles the other case: if only one side found a target, pass that result upward so an ancestor can decide.

What the output means: Returns the LCA node — for targets 5 and 1 in the diagram's tree, it returns node 3.

Try this: This one function quietly covers three outcomes: both targets on the left, both on the right, or split. Trace each case on paper to see how left or right forwards the answer up.

Problem: generate all subsets of a list. This is the canonical backtracking template — learn its shape and permutations, combinations, and N-queens all follow the same skeleton.

1. res holds all subsets found; path is the subset we're currently building as we descend the tree.
2. res.append(path[:]) records the current subset — and note every node is a valid subset, not just the leaves, so we save on entry. The [:] stores a snapshot copy (otherwise later edits would corrupt it).
3. The loop for i in range(start, len(nums)) tries each remaining element. path.append(nums[i]) is choose; backtrack(i + 1) is explore (starting after i so elements aren't reused); path.pop() is un-choose.
4. The start index is what prevents duplicate subsets like [1,2] and [2,1] — we only ever move forward.

What the output means: Prints all 8 subsets of [1,2,3]: [], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3].

Try this: Comment out path.pop() and watch the output break — without the "un-choose" step the shared path never rewinds, so every branch corrupts the next.

Two bottom-up DP classics. (a) Coin change (fewest coins to reach an amount) builds a 1-D table; (b) longest common subsequence (LCS) builds a 2-D table. Both fill small answers first, then combine them.

1. (a) coin_change: dp[x] is the fewest coins to make amount x. Start with dp[0]=0 and everything else inf (unreachable).
2. For each amount x and each coin c, dp[x] = min(dp[x], dp[x-c] + 1) asks "is using this coin (1 coin plus the best way to make the remainder x-c) better than what I have?" That's the recurrence.
3. (b) lcs: dp[i][j] is the longest subsequence shared by the first i letters of a and first j of b.
4. If the current letters match, extend the diagonal: dp[i-1][j-1] + 1. If not, carry the best of dropping one letter from either string: max(dp[i-1][j], dp[i][j-1]).

What the output means: Prints 3 3: it takes 3 coins (5+5+1) to make 11 from [1,2,5], and the longest common subsequence of "abcde" and "ace" is "ace" (length 3).

Try this: For coin change, print the whole dp array at the end and read off how each amount's answer was built from a smaller one — that's DP made visible.

Four more DP staples that show the space-saving trick: when a cell only needs the last one or two cells, you can drop the whole table and keep a couple of variables.

1. (a) climb: ways to reach step n = ways to reach n-1 + ways to reach n-2 — literally Fibonacci in disguise. Two rolling variables a, b replace the table → O(1) space.
2. (b) rob: at each house choose take-or-skip. take, skip = skip + x, max(skip, take) — if you rob this house you add it to the best that skipped the previous one; otherwise carry the best so far.
3. (c) lis: longest increasing subsequence in O(n log n). tails keeps the smallest possible tail for each length; bisect_left finds where the new value fits, replacing a tail (to keep options open) or extending the list.
4. (d) word_break: dp[i] = "can s[:i] be split into dictionary words?" It's true if some earlier valid point dp[j] is true and s[j:i] is a word.

What the output means: Prints 8 12 4: 8 ways to climb 5 stairs; max robbery of [2,7,9,3,1] is 12 (2+9+1); longest increasing subsequence length is 4.

Try this: For climb, print a, b each iteration — you'll see the Fibonacci sequence appear. Recognizing a problem as "Fibonacci-shaped" instantly gives you the O(1) solution.

Problem: for each day, how many days until a warmer temperature? A brute-force double loop is O(n²); a monotonic stack does it in O(n) by remembering days still "waiting" for a warmer one.

1. res = [0] * len(temps) defaults every answer to 0 (meaning "no warmer day ahead"). stack holds indices of days whose warmer day hasn't been found yet, kept with temperatures decreasing down the stack.
2. For each new day i with temperature t, the while loop pops every day on the stack that is colder than today — because today is their next warmer day.
3. res[j] = i - j records the wait: the gap in days between the colder day j and today i.
4. Then stack.append(i) parks today to wait for its warmer day. Each index is pushed and popped at most once → O(n).

What the output means: Prints [1,1,4,2,1,1,0,0] — e.g. day 0 (73°) waits 1 day for 74°; the last two days have no warmer day, so 0.

Try this: "Monotonic" just means the stack stays sorted (here decreasing). The tell for this pattern is "next greater/smaller element" — daily-temperatures, next-greater-element, and largest-rectangle all use it.

Problem: count how many contiguous subarrays sum to exactly k. The prefix-sum + hashmap trick turns an O(n²) search into a single O(n) pass.

1. A prefix sum is the running total from the start. If two prefix sums differ by k, the numbers between them sum to k — that's the whole insight.
2. seen counts how many times each running total has occurred; seen[0] = 1 seeds the "empty prefix" so subarrays starting at index 0 are counted.
3. Each step adds x to running, then count += seen[running - k] asks "how many earlier prefixes leave exactly k between them and here?" — an O(1) dictionary lookup instead of scanning back.
4. seen[running] += 1 then records the current prefix for future steps to find.

What the output means: Prints 2 — in [1,1,1] with k=2, the subarrays [1,1] at positions 0–1 and 1–2 both sum to 2.

Try this: The magic is running - k: instead of asking "what sums to k?" you ask "have I seen a prefix that, subtracted from now, leaves k?" This complement-in-a-hashmap idea also powers Two Sum.

Three must-know linked-list moves, all in O(1) extra space: (a) reverse, (b) merge two sorted lists using a dummy head, and (c) remove the nth node from the end with an offset two-pointer.

1. ListNode is the node type: a val and a next pointer to the following node.
2. (a) reverse: head.next, prev, head = prev, head, head.next flips one link and advances in a single line (Python computes the whole right side before assigning).
3. (b) merge_two: a dummy head node lets us build behind a dummy tail without special-casing the first node. We repeatedly attach the smaller of the two list heads; at the end tail.next = a or b appends whatever remains, and dummy.next is the real merged head.
4. (c) remove_nth_from_end: move fast n nodes ahead to open a gap, then move fast and slow together. When fast reaches the end, slow sits just before the target, so slow.next = slow.next.next unlinks it — all in one pass.

What the output means: Each returns a rebuilt list head: (a) the reversed list, (b) the two lists merged in sorted order, (c) the list with the nth-from-end node removed.

Try this: The dummy head is the unsung hero — it removes the "what if the list is empty / we remove the first node?" edge cases so your main loop stays clean. Watch for it in almost every linked-list solution.