DSA in Python — The Patterns That Recur¶

What this lesson gives you

Seven algorithmic patterns, Python’s batteries, and the complexity vocabulary every tier-1 interviewer expects you to speak fluently.

Estimated time: 45 min read · Part: Cracking the Tier-1 Interview

Tier-1 technical interviews are not trivia contests. They are pattern-recognition tests with a communication component layered on top. The recruiter screener asks whether you know Python. The first-round engineer asks whether you can recognize a sliding-window problem in disguise. The hiring committee debrief asks whether your reasoning would make sense to a client VP under time pressure. This lesson arms you with recognition vocabulary: seven patterns that account for roughly 85% of every problem you will encounter, plus the Big-O language to discuss them without hesitation.

The candidate who prepared 300 problems

Maya spent six weeks grinding 300 LeetCode problems, solving each one in isolation. In her Google loop she was given a novel problem she had never seen. She froze — not because she lacked skill, but because she had never built the mental model to ask “which pattern does this fit?” Her colleague Soo-Min prepared 60 problems, explicitly naming the pattern before touching the keyboard. Soo-Min recognized the two-pointer fingerprint within thirty seconds of reading the same novel problem and breezed through it. Pattern literacy is the meta-skill; volume is secondary.

Big-O: The Five Numbers You Will Speak Every Interview¶

Big-O notation describes how an algorithm’s resource use scales with input size n. Interviewers do not just want the answer — they want to hear you reason about it aloud before writing a single line of code.

Complexity	Name	Typical source	n = 10⁶ → rough ops
O(1)	Constant	Hash table lookup, array index	1
O(log n)	Logarithmic	Binary search, balanced BST op	~20
O(n)	Linear	Single-pass scan, hash map build	10⁶
O(n log n)	Linearithmic	Efficient sort, heap sort	~20 × 10⁶
O(n²)	Quadratic	Nested loops, naive string match	10¹² — too slow
O(n · m)	Product	DP on two sequences of length n, m	depends on both
O(2ⁿ)	Exponential	Subsets enumeration, naive recursion	astronomical

The constraint tells you the target complexity

When n ≤ 10, O(2ⁿ) is fine. When n ≤ 10³, O(n²) is acceptable. When n ≤ 10⁵, you need O(n log n) or better. When n ≤ 10⁶, you need O(n) or O(n log n). Interviewers deliberately reveal constraints in the problem statement — read them as a complexity budget, not as input bounds.

Amortized Analysis: Why `list.append` Is O(1)¶

Python lists are backed by dynamic arrays. When the underlying buffer fills, Python allocates a new buffer roughly 1.125× larger and copies all elements — an O(n) operation. Yet we call append O(1) amortized. Each element was “responsible” for its proportional share of that eventual copy cost, spreading the one-time expense across all n insertions. The same logic applies to Python’s dict rehashing and set resizing. When an interviewer probes “is that really O(1)?” for append, the correct answer is: “O(1) amortized; individual calls can be O(n) during a resize, but that cost is distributed.”

The highway service analogy

You commute 250 days a year. Once a year you spend a full weekend on a major car service. Averaged across 250 trips, that two-day cost adds only minutes per commute. The daily travel cost is effectively constant even though there is one expensive weekend. Dynamic array resizing works identically — one expensive resize, amortized over the many cheap appends that preceded it.

Space Complexity: In-Place vs Auxiliary¶

Space complexity measures the extra memory your algorithm consumes beyond the input. An in-place algorithm uses O(1) auxiliary space — it modifies the input array or uses a fixed number of pointer variables. Algorithms that build result arrays, hash maps, or deep recursion call stacks use auxiliary space proportional to their depth or output size. Always volunteer both time and space complexity; interviewers will ask, and the trade-off framing (“I can achieve O(n) time by spending O(n) space on a hash map, versus O(n²) time with O(1) space — which matters more in your context?”) signals engineering maturity.

Pattern 1 — Hash Map: O(1) Lookup as a Superpower¶

The hash map pattern converts an O(n) linear search into an O(1) lookup by pre-indexing values as keys. It is the single most frequent pattern at every interview level. Signal phrases: “find a pair that sums to X,” “detect duplicates,” “count frequencies,” “group elements by property.”

hash_map_patterns.py

# ── two_sum: O(n) time, O(n) space ───────────────────────────────────────
def two_sum(nums: list[int], target: int) -> list[int]:
    seen: dict[int, int] = {}          # value -> index
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

# ── group_anagrams: canonical-key grouping ────────────────────────────────
from collections import defaultdict

def group_anagrams(strs: list[str]) -> list[list[str]]:
    groups: dict[tuple, list[str]] = defaultdict(list)
    for s in strs:
        key = tuple(sorted(s))         # "eat" and "tea" both map to ('a','e','t')
        groups[key].append(s)
    return list(groups.values())

# ── anagram detection: fixed-alphabet frequency array (O(1) space) ────────
def is_anagram(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    freq = [0] * 26
    for c in s:
        freq[ord(c) - ord('a')] += 1
    for c in t:
        freq[ord(c) - ord('a')] -= 1
    return all(f == 0 for f in freq)

Pattern 2 — Two Pointers: Linear Time on Sorted or Symmetric Structures¶

Two pointers placed at opposite ends (or at different speeds in the same direction) eliminate the inner loop from O(n²) to O(n). Signal phrases: “sorted array,” “palindrome,” “remove duplicates in-place,” “container with most water.”

two_pointers.py

# ── container with most water: O(n) ──────────────────────────────────────
def max_water(heights: list[int]) -> int:
    left, right = 0, len(heights) - 1
    best = 0
    while left < right:
        area = min(heights[left], heights[right]) * (right - left)
        best = max(best, area)
        # always advance the shorter wall — moving the taller cannot increase area
        if heights[left] < heights[right]:
            left += 1
        else:
            right -= 1
    return best

# ── valid palindrome (skip non-alphanumeric): O(n) ───────────────────────
def is_palindrome(s: str) -> bool:
    left, right = 0, len(s) - 1
    while left < right:
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1
        if s[left].lower() != s[right].lower():
            return False
        left += 1
        right -= 1
    return True

# ── three-sum: fix one element, two-pointer for the rest ─────────────────
def three_sum(nums: list[int]) -> list[list[int]]:
    nums.sort()
    result: list[list[int]] = []
    for i, val in enumerate(nums):
        if i > 0 and nums[i] == nums[i - 1]:
            continue                   # skip duplicates for the fixed element
        lo, hi = i + 1, len(nums) - 1
        while lo < hi:
            s = val + nums[lo] + nums[hi]
            if s == 0:
                result.append([val, nums[lo], nums[hi]])
                while lo < hi and nums[lo] == nums[lo + 1]:
                    lo += 1
                while lo < hi and nums[hi] == nums[hi - 1]:
                    hi -= 1
                lo += 1; hi -= 1
            elif s < 0:
                lo += 1
            else:
                hi -= 1
    return result

Pattern 3 — Sliding Window: O(n) Over Subarray / Substring Problems¶

The sliding window maintains a contiguous range [left, right] and expands the right boundary unconditionally while contracting the left boundary only when a constraint is violated. Signal phrases: “contiguous subarray,” “substring,” “maximum / minimum length,” “at most K distinct.”

sliding_window.py

from collections import defaultdict

# ── longest substring without repeating characters ────────────────────────
def length_of_longest_substring(s: str) -> int:
    char_idx: dict[str, int] = {}
    best = 0
    left = 0
    for right, ch in enumerate(s):
        if ch in char_idx and char_idx[ch] >= left:
            left = char_idx[ch] + 1    # jump left past the duplicate
        char_idx[ch] = right
        best = max(best, right - left + 1)
    return best

# ── minimum window substring: O(n) ───────────────────────────────────────
def min_window(s: str, t: str) -> str:
    need: dict[str, int] = defaultdict(int)
    for c in t:
        need[c] += 1
    missing = len(t)
    best_start, best_len = 0, float('inf')
    left = 0
    for right, ch in enumerate(s):
        if need[ch] > 0:
            missing -= 1
        need[ch] -= 1
        if missing == 0:                      # valid window: try to shrink
            while need[s[left]] < 0:
                need[s[left]] += 1
                left += 1
            if right - left + 1 < best_len:
                best_len = right - left + 1
                best_start = left
            need[s[left]] += 1               # break window to continue scan
            missing += 1
            left += 1
    return s[best_start:best_start + best_len] if best_len != float('inf') else ""

# ── longest substring with at most K distinct characters ─────────────────
def longest_k_distinct(s: str, k: int) -> int:
    freq: dict[str, int] = defaultdict(int)
    best = 0
    left = 0
    for right, ch in enumerate(s):
        freq[ch] += 1
        while len(freq) > k:
            lc = s[left]
            freq[lc] -= 1
            if freq[lc] == 0:
                del freq[lc]
            left += 1
        best = max(best, right - left + 1)
    return best

Pattern 4 — BFS / DFS: Traversal and Shortest Paths¶

BFS (queue, level-by-level) finds the shortest path in unweighted graphs. DFS (stack or recursion, depth-first) explores fully before backtracking — the right tool for cycle detection, connected-component counting, topological sort, and all-paths enumeration. Grid problems are implicit graphs where each cell is a node and edges connect its four neighbors.

bfs_dfs.py

from collections import deque

# ── BFS: shortest path in unweighted graph ────────────────────────────────
def bfs_shortest(graph: dict[int, list[int]], src: int, dst: int) -> int:
    if src == dst:
        return 0
    visited = {src}
    queue: deque[tuple[int, int]] = deque([(src, 0)])
    while queue:
        node, dist = queue.popleft()
        for nb in graph.get(node, []):
            if nb == dst:
                return dist + 1
            if nb not in visited:
                visited.add(nb)
                queue.append((nb, dist + 1))
    return -1

# ── DFS: number of islands (in-place mutation to avoid a visited set) ─────
def num_islands(grid: list[list[str]]) -> int:
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    count = 0

    def sink(r: int, c: int) -> None:
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != '1':
            return
        grid[r][c] = '0'              # mark as water so we never revisit
        sink(r + 1, c); sink(r - 1, c)
        sink(r, c + 1); sink(r, c - 1)

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

# ── Topological sort via DFS: course schedule (cycle detection) ───────────
def can_finish(num_courses: int, prereqs: list[list[int]]) -> bool:
    graph: dict[int, list[int]] = {i: [] for i in range(num_courses)}
    for a, b in prereqs:
        graph[b].append(a)
    state = [0] * num_courses    # 0=unvisited 1=in-progress 2=done

    def has_cycle(node: int) -> bool:
        if state[node] == 1: return True     # back-edge detected
        if state[node] == 2: return False    # already fully explored
        state[node] = 1
        if any(has_cycle(nb) for nb in graph[node]):
            return True
        state[node] = 2
        return False

    return not any(has_cycle(i) for i in range(num_courses))

Pattern 5 — Binary Search: O(log n) on Any Monotone Search Space¶

Binary search is not just “find element in sorted array.” The advanced form is binary search on the answer space: if the answer is a value in a range and you can write is_feasible(x) -> bool that is monotonically True/False over that range, binary search finds the boundary in O(log range) × O(cost of is_feasible).

binary_search.py

import bisect, math

# ── classic binary search template ───────────────────────────────────────
def binary_search(nums: list[int], target: int) -> int:
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2    # avoids overflow (critical in other langs)
        if nums[mid] == target:   return mid
        elif nums[mid] < target:  lo = mid + 1
        else:                     hi = mid - 1
    return -1

# ── search in rotated sorted array ───────────────────────────────────────
def search_rotated(nums: list[int], target: int) -> int:
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] <= nums[mid]:           # left half is sorted
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:                               # right half is sorted
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

# ── binary search on answer space ────────────────────────────────────────
# Minimum eating speed (Koko) — feasibility check makes this O(n log max(piles))
def min_eating_speed(piles: list[int], h: int) -> int:
    def can_finish(speed: int) -> bool:
        return sum(math.ceil(p / speed) for p in piles) <= h

    lo, hi = 1, max(piles)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if can_finish(mid):
            hi = mid          # mid works; try slower
        else:
            lo = mid + 1      # mid too slow; need faster
    return lo

# ── bisect: Python standard library binary search ─────────────────────────
arr = [1, 3, 5, 7, 9]
pos = bisect.bisect_left(arr, 6)    # 3  (insertion point keeping sort)
bisect.insort(arr, 6)               # arr is now [1, 3, 5, 6, 7, 9]

Pattern 6 — Heap: O(log n) Access to Extremes¶

Python’s heapq is a min-heap. Negate values to simulate a max-heap. Heaps solve “top-K,” “K-th largest/smallest,” and “merge K sorted streams” problems in O(n log K) rather than O(n log n) sort.

heap_patterns.py

import heapq
from collections import Counter

# ── top-K frequent elements: O(n log k) ──────────────────────────────────
def top_k_frequent(nums: list[int], k: int) -> list[int]:
    freq = Counter(nums)
    heap: list[tuple[int, int]] = []
    for val, count in freq.items():
        heapq.heappush(heap, (count, val))
        if len(heap) > k:
            heapq.heappop(heap)        # evict the least frequent
    return [val for _, val in heap]

# ── kth largest element: O(n log k) ──────────────────────────────────────
def find_kth_largest(nums: list[int], k: int) -> int:
    heap: list[int] = []
    for num in nums:
        heapq.heappush(heap, num)
        if len(heap) > k:
            heapq.heappop(heap)
    return heap[0]                     # smallest item in the heap of k largest

# ── merge K sorted lists: O(n log k) using (value, list_idx, node) ───────
class ListNode:
    def __init__(self, val: int = 0, next: 'ListNode | None' = None):
        self.val = val; self.next = next

def merge_k_lists(lists: list[ListNode | None]) -> ListNode | None:
    heap: list[tuple[int, int, ListNode]] = []
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))
    dummy = ListNode()
    cur = dummy
    while heap:
        _, i, node = heapq.heappop(heap)
        cur.next = node; cur = cur.next
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    return dummy.next

# ── max-heap via negation; heappushpop is one atomic O(log n) ────────────
max_heap: list[int] = []
for v in [3, 1, 4, 1, 5, 9, 2, 6]:
    heapq.heappush(max_heap, -v)
largest = -heapq.heappop(max_heap)       # 9
# heappushpop: push then pop in one sift — faster than two calls
result = -heapq.heappushpop(max_heap, -7)  # pushes 7, pops and returns new max

Pattern 7 — Dynamic Programming: Optimal Substructure + Overlapping Subproblems¶

DP works when a problem can be decomposed into subproblems that recur (overlapping) and whose optimal solutions compose into the global optimum (optimal substructure). There are two implementation styles: top-down (memoized recursion) and bottom-up (tabulation). Both yield identical answers; bottom-up avoids Python’s recursion limit and runs faster in practice due to lower per-call overhead.

dynamic_programming.py

from functools import lru_cache

# ── coin change: memoization (top-down) ──────────────────────────────────
def coin_change_memo(coins: list[int], amount: int) -> int:
    @lru_cache(maxsize=None)
    def dp(rem: int) -> float:
        if rem == 0: return 0
        if rem < 0:  return float('inf')
        return 1 + min(dp(rem - c) for c in coins)

    ans = dp(amount)
    return int(ans) if ans != float('inf') else -1

# ── coin change: tabulation (bottom-up) — avoids recursion limit ──────────
def coin_change_tab(coins: list[int], amount: int) -> int:
    INF = float('inf')
    dp = [INF] * (amount + 1)
    dp[0] = 0
    for amt in range(1, amount + 1):
        for coin in coins:
            if coin <= amt:
                dp[amt] = min(dp[amt], dp[amt - coin] + 1)
    return int(dp[amount]) if dp[amount] != INF else -1

# ── climbing stairs: space-optimised 1D DP ───────────────────────────────
def climb_stairs(n: int) -> int:
    if n <= 2: return n
    a, b = 1, 2
    for _ in range(3, n + 1):
        a, b = b, a + b
    return b

# ── longest common subsequence: classic 2D DP ─────────────────────────────
def lcs_length(text1: str, text2: str) -> int:
    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]

Graph Representations and Union-Find¶

Choose your representation based on density. Adjacency lists (dict of lists) are O(V + E) space and work for most interview problems. Adjacency matrices are O(V²) space but give O(1) edge-existence checks — use them only when the graph is dense or the problem explicitly asks for it. Union-Find handles connected-component and cycle-detection problems in near-O(1) per query after O(n) build, making it faster than DFS when only connectivity matters.

union_find.py

# ── Union-Find with path compression + union by rank ─────────────────────
class UnionFind:
    def __init__(self, n: int) -> None:
        self.parent = list(range(n))
        self.rank   = [0] * n
        self.components = n

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

    def union(self, x: int, y: int) -> bool:
        """Returns False if x and y were already connected (i.e., cycle)."""
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        self.components -= 1
        return True

# ── usage: number of provinces ────────────────────────────────────────────
def find_circle_num(is_connected: list[list[int]]) -> int:
    n = len(is_connected)
    uf = UnionFind(n)
    for i in range(n):
        for j in range(i + 1, n):
            if is_connected[i][j]:
                uf.union(i, j)
    return uf.components

# ── usage: detect cycle in undirected graph ───────────────────────────────
def has_cycle(n: int, edges: list[list[int]]) -> bool:
    uf = UnionFind(n)
    for u, v in edges:
        if not uf.union(u, v):    # already same component = cycle
            return True
    return False

Python Batteries for Interviews¶

python_batteries.py

from collections import Counter, deque, defaultdict
from functools import lru_cache
import bisect, heapq

# ── Counter: frequency map in one call ───────────────────────────────────
words = ["apple", "banana", "apple", "cherry", "banana", "apple"]
freq  = Counter(words)               # Counter({'apple': 3, 'banana': 2, ...})
top2  = freq.most_common(2)          # [('apple', 3), ('banana', 2)]
freq.subtract(Counter(["apple"]))    # decrements counts in-place

# ── deque: O(1) push/pop from both ends ───────────────────────────────────
dq = deque([1, 2, 3], maxlen=5)      # bounded deque for sliding-window maximums
dq.appendleft(0)                     # deque([0, 1, 2, 3])
dq.popleft()                         # 0  — O(1), unlike list.pop(0) which is O(n)

# ── defaultdict: no KeyError on first access ──────────────────────────────
adj: dict[str, list[str]] = defaultdict(list)
adj['a'].append('b')                 # no need to check if 'a' key exists

# ── lru_cache: transparent memoization for pure functions ─────────────────
@lru_cache(maxsize=None)
def fib(n: int) -> int:
    return n if n <= 1 else fib(n - 1) + fib(n - 2)

fib.cache_clear()   # call before the next test to avoid stale state

# ── bisect: O(log n) operations on sorted lists ───────────────────────────
sorted_arr = [1, 3, 5, 7, 9]
pos  = bisect.bisect_left(sorted_arr, 6)    # 3 — where 6 would be inserted
posr = bisect.bisect_right(sorted_arr, 5)   # 3 — after existing 5
bisect.insort(sorted_arr, 6)                # inserts 6, keeps list sorted

# ── heapq: nlargest / nsmallest as single-call shortcuts ─────────────────
data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]
top3    = heapq.nlargest(3, data)    # [9, 6, 5]
bottom3 = heapq.nsmallest(3, data)  # [1, 1, 2]

Python’s recursion depth trap

Python’s default recursion limit is 1 000. A DFS on a 300×300 grid can exceed it. In interviews either call sys.setrecursionlimit(300 * 300) explicitly (and say so out loud), or convert to iterative DFS with an explicit stack. Interviewers at top-tier companies probe for this specifically — it shows you understand Python’s runtime, not just its syntax.

flowchart TD
    A[Read the problem] --> B{Sorted inputor need extremes?}
    B -->|Sorted array| C{Search or pairs?}
    B -->|Need min/max K times| H[Heap]
    C -->|Search target| D[Binary Search]
    C -->|Pairs / palindrome| E[Two Pointers]
    A --> F{Contiguous subarrayor substring?}
    F -->|Fixed or variable window| G[Sliding Window]
    A --> I{Graph or grid?}
    I -->|Shortest path| J[BFS]
    I -->|All paths / cycle / components| K[DFS / Union-Find]
    A --> L{Count, group,or find complement?}
    L --> M[Hash Map]
    A --> N{Optimal answerbuilt from sub-answers?}
    N --> O[Dynamic Programming]

Tiebreaker in heap tuples

When you push tuples into heapq, Python compares them lexicographically. If two tuples share the same first element (e.g., same frequency), Python compares the second element. If the second element is a custom object that doesn’t support <, you get a TypeError. Always add a monotonically increasing counter as a tiebreaker: (priority, counter, item).

Pattern	Time	Space	Signal phrase	Python weapon	Common gotcha
Hash Map	O(n)	O(n)	“find pair,” “group by,” “count”	dict, Counter, defaultdict	Same-index collision in two_sum (use seen[num] = i, not a set)
Two Pointers	O(n)	O(1)	“sorted,” “palindrome,” “in-place”	lo / hi indices	Off-by-one: use `lo < hi` not `lo <= hi` when they can’t overlap
Sliding Window	O(n)	O(k)	“contiguous subarray,” “at most K”	deque, defaultdict	Forgetting to shrink window when constraint violated
BFS	O(V+E)	O(V)	“shortest path,” “level order”	collections.deque	Mark visited before enqueuing, not after dequeuing
DFS	O(V+E)	O(V)	“all paths,” “connected,” “cycle”	recursion / explicit stack	Python recursion depth; use iterative DFS for deep trees/grids
Binary Search	O(log n)	O(1)	“minimum feasible,” “sorted range”	bisect, lo/hi template	`lo < hi` vs `lo <= hi`: depends on whether mid can be the answer
Heap	O(n log k)	O(k)	“top-K,” “kth largest,” “merge streams”	heapq (negate for max)	Tuple comparison breaks on non-comparable second elements — add a counter
DP	varies	O(n) or O(n²)	“maximum/minimum,” “number of ways”	lru_cache, 2-D array	Confusing index with value in dp array; forgetting the base case

Consulting lens: pattern vocabulary as client communication

In technical solutions consulting you will often explain algorithm choices to non-technical stakeholders: “We process your ten-million-event daily stream in linear time by maintaining a hash map of active sessions — one O(1) lookup per event. The trade-off is O(n) memory, which at 200 bytes per session means roughly 2 GB for your peak concurrency. That is far cheaper than the quadratic database scan your current query performs.” The same pattern vocabulary that wins interviews is the vocabulary you use to justify architectural choices in client deliverables.

Key takeaways

Read the constraint first; it gives you a complexity budget before you choose any algorithm.
Name the pattern out loud before writing a single line — this alone distinguishes prepared candidates.
Hash map converts O(n) search to O(1) lookup; it is the most-reached lever in tier-1 interviews.
BFS finds shortest paths; DFS handles existence, connectivity, and topological order.
Binary search applies to any monotone feasibility function, not just sorted arrays.
DP = memoized recursion or tabulation; tabulation avoids Python’s stack depth limit.
Union-Find detects connected components and cycles in near-O(1) per query — faster than DFS when you only care about connectivity.

Knowledge check

InterviewYou have an unsorted array of n integers and must find all pairs summing to target T in O(n) time. Which approach is correct?

Sort the array then scan with nested loops — O(n²) after sort
Sort then binary-search for T–x for each x — O(n log n) not O(n)
Iterate once; for each x check whether T–x is in a hash set, then add x — O(n) time, O(n) space
Use two nested for-loops and break early — still O(n²) worst case

Answer

Iterate once; for each x check whether T–x is in a hash set, then add x — O(n) time, O(n) space

The hash set approach is the canonical O(n) solution. For each element x, we check in O(1) whether its complement T–x has already been seen. Sorting + binary search per element costs O(n log n), which is better than O(n²) but does not meet the O(n) requirement. Nested loops are O(n²) regardless of early exits in the worst case. The hash set trades O(n) auxiliary space for O(n) time savings — always worth volunteering this trade-off in the interview.

Exercise

Exercise 15.1 · Sliding Window — Max Consecutive Ones After K Flips Given a binary array nums and integer k, return the maximum number of consecutive 1s you can achieve after flipping at most k zeros to ones. Aim for O(n) time and O(1) space. Test: nums=[1,1,1,0,0,0,1,1,1,1,0], k=2 → 6.

Show solution

solution_15_1.py

def longest_ones(nums: list[int], k: int) -> int:
    """Sliding window: track zeros_used in the window.
    Expand right freely; shrink left when zeros_used > k."""
    left = 0
    zeros_used = 0
    best = 0
    for right, val in enumerate(nums):
        if val == 0:
            zeros_used += 1
        while zeros_used > k:
            if nums[left] == 0:
                zeros_used -= 1
            left += 1
        best = max(best, right - left + 1)
    return best

assert longest_ones([1,1,1,0,0,0,1,1,1,1,0], 2) == 6
assert longest_ones([0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], 3) == 10
assert longest_ones([0,0,0], 0) == 0
print("All tests passed")