How do you optimize 'Longest Substring Without Repeating Characters' (`LeetCode 3`) to jump `L` directly without shrinking one character at a time?

Maintain a hash map `last_seen` mapping each character `ch` to its most recent index. As `R` iterates over `(R, ch)` in `enumerate(s)`: if `ch in last_seen and last_seen[ch] >= L`, jump the left boundary immediately to `L = last_seen[ch] + 1`. Update `last_seen[ch] = R` and `ans = max(ans, R - L + 1)`.

Why does the standard Sliding Window fail when array elements can be negative, and what trick relates 'Subarrays with Exactly K Distinct' to Sliding Window (`LeetCode 992`)?

Standard two-pointer sliding window relies on monotonicity (expanding `R` monotonically increases sum/distinct count, shrinking `L` decreases it), which breaks when negative numbers exist. For 'Exactly $K$ Distinct Integers', `exactly(K)` is not a single pass because multiple `L` positions work for a given `R`; instead, define a helper `atMost(K)` (which adds `R - L + 1` valid subarrays ending at `R` once distinct count $\le K$) and compute `atMost(K) - atMost(K - 1)`!

How does the Rabin-Karp Rolling Hash algorithm compute substring hashes in $O(1)$ sliding time?

Treat a string `s[0..k-1]` as a base-$B$ polynomial modulo a large prime $M$: $H = (\sum_{i=0}^{k-1} s[i] \cdot B^{k-1-i}) \bmod M$ (e.g., $B = 31$ or $256$, $M = 10^9 + 7$ or $10^9 + 9$). To slide the window one step right from `s[i..i+k-1]` to `s[i+1..i+k]`, subtract the outgoing high-order character and add the incoming character in $O(1)$ time: $H_{\text{new}} = ((H - s[i] \cdot B^{k-1}) \cdot B + s[i+k]) \bmod M$. Verify matches (or use double hashing with two primes) to avoid spurious hash collisions.

Explain Kadane's Algorithm for Maximum Subarray Sum (`LeetCode 53`) and how it extends to Maximum Circular Subarray (`LeetCode 918`).

Kadane's Algorithm maintains the maximum subarray sum ending at index $i$: `curr_max = max(x, curr_max + x)` and `best = max(best, curr_max)` in $O(n)$ time and $O(1)$ space. For a Circular Array, the max subarray either: 1. Does NOT wrap around (standard `max_kadane`), or 2. Wraps around both ends, which equals `total_sum - min_kadane` (where `min_kadane` is the minimum contiguous subarray sum). Handle the edge case where all numbers are negative (if `max_kadane < 0`, return `max_kadane`).

Explain Edsger Dijkstra's Dutch National Flag Algorithm (`LeetCode 75 Sort Colors`) for 3-way in-place partitioning in one $O(n)$ pass.

Maintain three pointers `low = 0`, `mid = 0`, `high = n - 1` dividing the array into four regions (`[0..low-1]` are `0`s, `[low..mid-1]` are `1`s, `[mid..high]` are unknown, `[high+1..n-1]` are `2`s). While `mid <= high`: 1. If `nums[mid] == 0`: swap `nums[low]` and `nums[mid]`, increment BOTH `low += 1` and `mid += 1`. 2. If `nums[mid] == 1`: increment `mid += 1`. 3. If `nums[mid] == 2`: swap `nums[mid]` and `nums[high]`, decrement `high -= 1` (do NOT increment `mid` because the swapped-in element from `high` hasn't been inspected yet!).

Compare the two ways to key 'Group Anagrams' (`LeetCode 49`) in a Hash Map and their time complexities for $N$ strings of max length $K$.

1. Sorted String Key (`tuple(sorted(s))` or `"".join(sorted(s))`): Takes $O(K \log K)$ per string $\implies O(N \cdot K \log K)$ total time. 2. Character Frequency Tuple Key (count occurrences of `'a'..'z'` in an array of size 26 and convert to `tuple(counts)`): Takes $O(K)$ per string $\implies O(N \cdot K)$ optimal linear time!

Explain the step-by-step algorithm for `Next Permutation` (`LeetCode 31`) in $O(n)$ time and $O(1)$ space.

To find the lexicographically next greater permutation: 1. Scan from right to left to find the first 'pivot' index $i$ where `nums[i] < nums[i + 1]` (if no such $i$ exists, the array is in descending order—just reverse the whole array). 2. Scan from right to left in the suffix `[i+1 .. n-1]` to find the smallest element `nums[j]` that is strictly greater than `nums[i]`, and swap `nums[i]` with `nums[j]`. 3. Reverse the suffix `[i+1 .. n-1]` (which is still in descending order) to make it ascending (smallest possible).

How do you solve 'Trapping Rain Water' (`LeetCode 42`) in $O(n)$ time and $O(1)$ space using Two Pointers?

Water trapped above bar $i$ is $\max(0, \min(\text{maxL}[i], \text{maxR}[i]) - H[i])$. Instead of precomputing `maxL` and `maxR` arrays in $O(n)$ space, maintain `L = 0, R = n - 1` and running `left_max = H[0], right_max = H[n-1]`. Whenever `left_max <= right_max`, we KNOW the bottleneck at index `L` is `left_max` (regardless of unseen middle bars, since at least one bar $\ge \text{left\_max}$ exists on the right!), so add `left_max - H[L]` to `water` and advance `L += 1`; otherwise process `R` and decrement `R -= 1`.

How does a 2D Prefix Sum matrix compute the sum of any rectangular subgrid `(r1, c1)` to `(r2, c2)` in $O(1)$ time?

Using Inclusion-Exclusion, build `P` of size $(R+1) \times (C+1)$ where `P[r+1][c+1] = grid[r][c] + P[r][c+1] + P[r+1][c] - P[r][c]`. Then for any query rectangle `(r1, c1)` to `(r2, c2)` (inclusive, 0-indexed): `sum = P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]` in $O(1)$ time (`LeetCode 304`).

What is a Difference Array and how does it apply $Q$ range addition updates `[L, R, +val]` in $O(1)$ per update?

The Difference Array `D` is the inverse of Prefix Sums (`D[0] = A[0]`, `D[i] = A[i] - A[i-1]`). To add `val` to every element in `A[L..R]`, simply set `D[L] += val` and `D[R + 1] -= val` in $O(1)$ time! After all $Q$ updates are applied, take the prefix sum of `D` in $O(n)$ time to reconstruct the final array (`LeetCode 370 Range Addition`, `1094 Car Pooling`, `1109 Corporate Flight Bookings`).

How do you solve 'Subarray Sum Equals K' (`LeetCode 560`) in $O(n)$ time and $O(n)$ space when the array contains negative numbers?

Because the array can contain negative numbers, a sliding window does NOT work (expanding/shrinking is non-monotonic). Instead, combine Prefix Sums with a Hash Map `freq` initialized to `{0: 1}` (recording how many times each prefix sum has occurred so far). As you iterate and maintain `curr_sum += x`, a subarray ending at the current index sums to $K$ whenever `curr_sum - K` already exists in `freq` (`ans += freq[curr_sum - K]`), then increment `freq[curr_sum] += 1`.

Explain the Boyer-Moore Majority Vote Algorithm (`LeetCode 169` & `229`) for finding elements appearing $> \lfloor n/2 \rfloor$ or $> \lfloor n/3 \rfloor$ times in $O(n)$ time and $O(1)$ space.

Intuition: Pairing each occurrence of the majority element with a distinct non-majority element cancels them out, leaving the majority element standing. Maintain `candidate = None, count = 0`. For each `x`: if `count == 0`, set `candidate = x`; then `count += (1 if x == candidate else -1)`. (If a majority isn't guaranteed, verify `candidate` with a second counting pass). For $> \lfloor n/3 \rfloor$ (`LC 229`), there can be at most 2 such elements—maintain 2 candidates and 2 counters, decrementing both only when `x` matches neither.

What is Auxiliary Space Complexity vs. Total Space Complexity, and how does the recursion call stack affect it?

Total Space Complexity includes both the input storage and extra memory; Auxiliary Space Complexity counts ONLY the extra memory allocated by the algorithm beyond the input (plus output if required). Every active recursive call frame stays on the call stack simultaneously—so a DFS on a skewed binary tree of $n$ nodes uses $O(n)$ auxiliary call-stack space, whereas on a balanced tree it uses $O(\log n)$ space.

Why is appending to a Dynamic Array (`std::vector`, Python `list`, Java `ArrayList`) $O(1)$ amortized time even though resizing takes $O(n)$?

When capacity is reached at powers of 2 ($1, 2, 4, 8, \dots, n$), the array allocates a new buffer of size $2n$ and copies $n$ elements. Across $n$ total `append` operations, the total cost is $n$ individual writes plus the geometric sum of copies: $1 + 2 + 4 + 8 + \dots + n/2 + n < 2n$. Dividing total work $< 3n$ by $n$ operations yields $O(1)$ amortized time per append! (If it grew by a constant $+k$ instead of $\times 2$, total work would be arithmetic $\Theta(n^2)$, or $O(n)$ amortized per append).

State the three cases of the Master Theorem for divide-and-conquer recurrences $T(n) = a T(n/b) + f(n)$ where $a \ge 1, b > 1$.

Let $c_{\text{crit}} = \log_b a$ (so work at leaves is $n^{\log_b a}$): Case 1 (Leaf-heavy): If $f(n) = O(n^{c_{\text{crit}} - \epsilon})$, then $T(n) = \Theta(n^{\log_b a})$ (e.g., binary tree traversal $2T(n/2) + O(1) = \Theta(n)$). Case 2 (Balanced across levels): If $f(n) = \Theta(n^{c_{\text{crit}}} \log^k n)$, then $T(n) = \Theta(n^{c_{\text{crit}}} \log^{k+1} n)$ (e.g., Merge Sort $2T(n/2) + \Theta(n) = \Theta(n \log n)$, Binary Search $T(n/2) + \Theta(1) = \Theta(\log n)$). Case 3 (Root-heavy): If $f(n) = \Omega(n^{c_{\text{crit}} + \epsilon})$, then $T(n) = \Theta(f(n))$ (e.g., Quickselect average $T(n/2) + O(n) = \Theta(n)$).

What bitwise XOR (`^`) and bit-manipulation tricks (`x & (x - 1)`, `x & -x`) are used in $O(1)$-space array problems?

1. XOR properties: $a \oplus a = 0$, $a \oplus 0 = a$, commutative & associative—so XORing all elements in an array where every number appears twice except one (`Single Number`, `LC 136`) isolates the unique number in $O(n)$ time and $O(1)$ space. 2. `x & (x - 1)` clears the lowest set `1`-bit of `x` (Brian Kernighan's bit count; also tests if $x > 0$ is a power of two via `(x & (x - 1)) == 0`). 3. `x & (-x)` isolates ONLY the lowest set `1`-bit of `x` (used in Fenwick Trees / Binary Indexed Trees and `Single Number III` `LC 260`).

Explain the 1D Prefix Sum pattern and how it answers arbitrary range sum queries `sum(L, R)` in $O(1)$ time.

Precompute an array `P` of length $n + 1$ in $O(n)$ time where `P[0] = 0` and `P[i + 1] = P[i] + nums[i]` (so `P[k]` is the sum of the first $k$ elements). Then the sum of any contiguous subarray `nums[L..R]` (inclusive, 0-indexed) is simply `P[R + 1] - P[L]` in $O(1)$ time.

How do you solve 'Longest Consecutive Sequence' (`LeetCode 128`) in strict $O(n)$ time instead of $O(n \log n)$ sorting?

Insert all numbers into a Hash Set `num_set` in $O(n)$ time. Iterate over each unique `x` in `num_set`: ONLY start counting a streak if `x - 1 not in num_set` (meaning `x` is the true start of a consecutive sequence!). If `x - 1` is not in the set, walk `curr = x` upward (`while curr + 1 in num_set: curr += 1`) and update `best = max(best, curr - x + 1)`. Every element is visited at most twice (once in outer loop, once in inner `while`), guaranteeing $O(n)$ time!

Why does the greedy Two-Pointer approach work for 'Container With Most Water' (`LeetCode 11`) in $O(n)$ time?

Start with widest possible pointers `L = 0, R = n - 1`. The area is $(R - L) \times \min(H[L], H[R])$, which is bottlenecked by the SHORTER line. If $H[L] < H[R]$, moving the taller line $R$ inward can NEVER increase $\min(H[L], H[R'])$ above $H[L]$ while strictly decreasing width $(R' - L)$—so every remaining pair `(L, R')` with that `L` is guaranteed to be worse! Thus we can safely discard the shorter pointer (`L += 1` if $H[L] < H[R]$ else `R -= 1`) at each step.

How do you rotate an array of length $n$ to the right by $k$ steps in-place in $O(n)$ time and $O(1)$ space (`LeetCode 189`)?

Use the Three-Reverse Trick! First normalize $k = k \bmod n$. Then: 1. Reverse the entire array `[0 .. n-1]`; 2. Reverse the first $k$ elements `[0 .. k-1]`; 3. Reverse the remaining $n - k$ elements `[k .. n-1]`. Each element is swapped a constant number of times with zero extra space.

In 'Longest Repeating Character Replacement' (`LeetCode 424`), why only track `max_freq` in the sliding window?

A window of length `len = R - L + 1` can be turned into all identical characters using at most $k$ replacements if and only if `(R - L + 1) - max_freq k`, decrement `count[s[L]]` and advance `L += 1` ( shifting the window right by 1 without even needing to recompute `max_freq` downward, because only a strictly larger `max_freq` can ever produce a longer valid window!).

How does the Interval Merging / Sweep-Line pattern solve 'Merge Intervals' (`LeetCode 56`) and 'Meeting Rooms II' (`LeetCode 253`)?

Merge Intervals (`LC 56`): Sort intervals by start time $O(n \log n)$; iterate and if `curr.start <= merged[-1].end`, merge by setting `merged[-1].end = max(merged[-1].end, curr.end)`, else append `curr`. Meeting Rooms II (minimum concurrent rooms, `LC 253`): Use a Sweep-Line (separate sorted `starts` and `ends` arrays, or events `(start, +1)` and `(end, -1)` sorted by time with `-1` before `+1` on ties) and track the maximum prefix sum of active meetings in $O(n \log n)$ time.

How do you solve 'Product of Array Except Self' (`LeetCode 238`) in $O(n)$ time and $O(1)$ auxiliary space without using the division operator?

Make two passes over the output array `res` (initialized to `1`s): 1. Left-to-right pass: maintain a running `prefix_prod = 1`; at each index $i$, set `res[i] = prefix_prod` and then update `prefix_prod *= nums[i]`. 2. Right-to-left pass: maintain a running `suffix_prod = 1`; at each index $i$, multiply `res[i] *= suffix_prod` and then update `suffix_prod *= nums[i]`.

What is the universal Variable-Size Sliding Window template for finding the Longest vs. Shortest valid subarray/substring?

Initialize `L = 0` and window state (counter/map). Loop `for R in range(n):` 1. Add `A[R]` to window state. 2. For LONGEST valid window: `while window_is_invalid():` remove `A[L]` and `L += 1`; then outside the `while` loop update `ans = max(ans, R - L + 1)`. For SHORTEST valid window (e.g., Minimum Size Subarray Sum `LC 209`): `while window_is_valid():` update `ans = min(ans, R - L + 1)`, remove `A[L]`, and `L += 1`.

How does the Opposite-Ends Two Pointers pattern solve `3Sum` (`LeetCode 15`) in $O(n^2)$ time without using a Hash Set for deduplication?

1. Sort the array in $O(n \log n)$. 2. Loop outer index $i$ from $0$ to $n-3$ (if `nums[i] > 0`, break early; if $i > 0$ and `nums[i] == nums[i-1]`, `continue` to skip duplicate anchors). 3. Set `L = i + 1, R = n - 1`. While `L 0`, `R -= 1`; if `s == 0`, record triplet, increment `L += 1`, decrement `R -= 1`, and advance `while L < R and nums[L] == nums[L-1]: L += 1` to skip duplicates.

Order the common complexity classes from fastest to slowest growth, and map maximum input size $N$ that passes within a ~1-second ($10^8$ ops) interview limit.

$O(1) 10^9 \implies O(\log n)$ or $O(1)$.

Compare Separate Chaining and Open Addressing (Linear Probing, Quadratic Probing, Double Hashing, Robin Hood Hashing) for Hash Table collision resolution.

Separate Chaining: Each bucket holds a linked list (or balanced tree in Java 8 `HashMap` when chain length $\ge 8$); degrades gracefully at high load factors ($\alpha = n/m > 1$), but has poor CPU cache locality due to pointer chasing. Open Addressing: Stores all entries directly inside the contiguous bucket array for superior CPU L1/L2 cache locality; requires load factor $\alpha < 0.7–0.8$, uses tombstones on deletion, and suffers from primary clustering in Linear Probing (mitigated by Robin Hood Hashing, which swaps entries to equalize probe-sequence lengths, or SwissTable SIMD metadata bytes).

Define Big-O ($O$), Big-Omega ($\Omega$), and Big-Theta ($\Theta$) asymptotic notations.

$O(f(n))$ (Asymptotic Upper Bound): The growth rate is no faster than $c \cdot f(n)$ for $n \ge n_0$. $\Omega(f(n))$ (Asymptotic Lower Bound): The growth rate is at least $c \cdot f(n)$. $\Theta(f(n))$ (Asymptotic Tight Bound): The function is bounded both above and below by $f(n)$. Note: In coding interviews, candidates say 'Big-O' to refer to the tightest upper bound of the worst-case (or expected) runtime.

What is the Fast-and-Slow (Read/Write) Two-Pointer pattern for in-place array compaction (e.g., `Remove Duplicates from Sorted Array II`, `LeetCode 80`)?

Maintain a `write` pointer for the next valid output position and a `read` pointer scanning the array. To allow at most $k$ duplicates in a sorted array (`k = 2` for LC 80): for each `x` in `nums`: if `write < k` or `x != nums[write - k]`, set `nums[write] = x` and increment `write += 1`. Returns `write` in $O(n)$ time and $O(1)$ space.

How do you solve 'Minimum Window Substring' (`LeetCode 76`) in $O(|S| + |T|)$ time using the `have == need` counter optimization?

Instead of comparing two 52-character frequency maps at every step, count unique required characters in `T`: `need = len(countT)` and `have = 0`. When expanding `R`, if `window[ch] == countT[ch]`, increment `have += 1`. While `have == need` (valid window): record `(R - L + 1)` if smaller than current best, then pop `s[L]` from `window`—if `window[s[L]] < countT[s[L]]`, decrement `have -= 1`—and advance `L += 1`.

How does the cyclic negation / index-mapping trick solve 'First Missing Positive' (`LeetCode 41`) in $O(n)$ time and $O(1)$ space?

The first missing positive integer in an array of length $n$ MUST be in $[1, n+1]$. Using Cycle Sort in-place: for each index $i$, while $1 \le \text{nums}[i] \le n$ and `nums[nums[i] - 1] != nums[i]`, swap `nums[i]` into its rightful home index `nums[i] - 1` (each number is placed in its home at most once, so total swaps $\le n$, $O(n)$ time!). Then scan $i = 0 \dots n-1$: the first index where `nums[i] != i + 1` gives answer $i + 1$; otherwise $n + 1$.

Why must Hash Map keys in Python (`dict`/`set`) be immutable (`tuple`, `str`, `int`, `frozenset`), and what happens if a custom object mutates its `__hash__` after insertion?

A hash table determines which bucket slot an object lives in by computing `hash(key) & mask` at insertion time. If a key object's value mutated after insertion—changing its `hash(key)`—future lookups for that object would probe a completely different bucket slot and fail to find it, corrupting the hash table invariants. Note: If a custom class overrides `__eq__`, it must also implement a consistent `__hash__` (`a == b` MUST imply `hash(a) == hash(b)`).

Big-O Complexity, Arrays, Two Pointers, Sliding Window & Hashing Patterns

Foundational Software Engineering interview mastery covering Big-O time and space complexity, the Master Theorem, amortized dynamic array analysis, Prefix Sums, Difference Arrays, Kadane's Algorithm, Boyer-Moore Majority Vote, Dutch National Flag, Two Pointers, Sliding Window templates, Hash Table collision resolution, and Rabin-Karp Rolling Hash.

Level: basic
Languages: en → en
Cards: 32
Markdown: Big-O Complexity, Arrays, Two Pointers, Sliding Window & Hashing Patterns (.md)

Flashcards (32)

#	Front (Term / Question)	Back (Definition / Answer)
1	How do you optimize 'Longest Substring Without Repeating Characters' (`LeetCode 3`) to jump `L` directly without shrinking one character at a time?	Maintain a hash map `last_seen` mapping each character `ch` to its most recent index. As `R` iterates over `(R, ch)` in `enumerate(s)`: if `ch in last_seen and last_seen[ch] >= L`, jump the left boundary immediately to `L = last_seen[ch] + 1`. Update `last_seen[ch] = R` and `ans = max(ans, R - L + 1)`.
2	Why does the standard Sliding Window fail when array elements can be negative, and what trick relates 'Subarrays with Exactly K Distinct' to Sliding Window (`LeetCode 992`)?	Standard two-pointer sliding window relies on monotonicity (expanding `R` monotonically increases sum/distinct count, shrinking `L` decreases it), which breaks when negative numbers exist. For 'Exactly $K$ Distinct Integers', `exactly(K)` is not a single pass because multiple `L` positions work for a given `R`; instead, define a helper `atMost(K)` (which adds `R - L + 1` valid subarrays ending at `R` once distinct count $\le K$) and compute `atMost(K) - atMost(K - 1)`!
3	How does the Rabin-Karp Rolling Hash algorithm compute substring hashes in $O(1)$ sliding time?	Treat a string `s[0..k-1]` as a base-$B$ polynomial modulo a large prime $M$: $H = (\sum_{i=0}^{k-1} s[i] \cdot B^{k-1-i}) \bmod M$ (e.g., $B = 31$ or $256$, $M = 10^9 + 7$ or $10^9 + 9$). To slide the window one step right from `s[i..i+k-1]` to `s[i+1..i+k]`, subtract the outgoing high-order character and add the incoming character in $O(1)$ time: $H_{\text{new}} = ((H - s[i] \cdot B^{k-1}) \cdot B + s[i+k]) \bmod M$. Verify matches (or use double hashing with two primes) to avoid spurious hash collisions.
4	Explain Kadane's Algorithm for Maximum Subarray Sum (`LeetCode 53`) and how it extends to Maximum Circular Subarray (`LeetCode 918`).	Kadane's Algorithm maintains the maximum subarray sum ending at index $i$: `curr_max = max(x, curr_max + x)` and `best = max(best, curr_max)` in $O(n)$ time and $O(1)$ space. For a Circular Array, the max subarray either: 1. Does NOT wrap around (standard `max_kadane`), or 2. Wraps around both ends, which equals `total_sum - min_kadane` (where `min_kadane` is the minimum contiguous subarray sum). Handle the edge case where all numbers are negative (if `max_kadane < 0`, return `max_kadane`).
5	Explain Edsger Dijkstra's Dutch National Flag Algorithm (`LeetCode 75 Sort Colors`) for 3-way in-place partitioning in one $O(n)$ pass.	Maintain three pointers `low = 0`, `mid = 0`, `high = n - 1` dividing the array into four regions (`[0..low-1]` are `0`s, `[low..mid-1]` are `1`s, `[mid..high]` are unknown, `[high+1..n-1]` are `2`s). While `mid <= high`: 1. If `nums[mid] == 0`: swap `nums[low]` and `nums[mid]`, increment BOTH `low += 1` and `mid += 1`. 2. If `nums[mid] == 1`: increment `mid += 1`. 3. If `nums[mid] == 2`: swap `nums[mid]` and `nums[high]`, decrement `high -= 1` (do NOT increment `mid` because the swapped-in element from `high` hasn't been inspected yet!).
6	Compare the two ways to key 'Group Anagrams' (`LeetCode 49`) in a Hash Map and their time complexities for $N$ strings of max length $K$.	1. Sorted String Key (`tuple(sorted(s))` or `"".join(sorted(s))`): Takes $O(K \log K)$ per string $\implies O(N \cdot K \log K)$ total time. 2. Character Frequency Tuple Key (count occurrences of `'a'..'z'` in an array of size 26 and convert to `tuple(counts)`): Takes $O(K)$ per string $\implies O(N \cdot K)$ optimal linear time!
7	Explain the step-by-step algorithm for `Next Permutation` (`LeetCode 31`) in $O(n)$ time and $O(1)$ space.	To find the lexicographically next greater permutation: 1. Scan from right to left to find the first 'pivot' index $i$ where `nums[i] < nums[i + 1]` (if no such $i$ exists, the array is in descending order—just reverse the whole array). 2. Scan from right to left in the suffix `[i+1 .. n-1]` to find the smallest element `nums[j]` that is strictly greater than `nums[i]`, and swap `nums[i]` with `nums[j]`. 3. Reverse the suffix `[i+1 .. n-1]` (which is still in descending order) to make it ascending (smallest possible).
8	How do you solve 'Trapping Rain Water' (`LeetCode 42`) in $O(n)$ time and $O(1)$ space using Two Pointers?	Water trapped above bar $i$ is $\max(0, \min(\text{maxL}[i], \text{maxR}[i]) - H[i])$. Instead of precomputing `maxL` and `maxR` arrays in $O(n)$ space, maintain `L = 0, R = n - 1` and running `left_max = H[0], right_max = H[n-1]`. Whenever `left_max <= right_max`, we KNOW the bottleneck at index `L` is `left_max` (regardless of unseen middle bars, since at least one bar $\ge \text{left\_max}$ exists on the right!), so add `left_max - H[L]` to `water` and advance `L += 1`; otherwise process `R` and decrement `R -= 1`.
9	How does a 2D Prefix Sum matrix compute the sum of any rectangular subgrid `(r1, c1)` to `(r2, c2)` in $O(1)$ time?	Using Inclusion-Exclusion, build `P` of size $(R+1) \times (C+1)$ where `P[r+1][c+1] = grid[r][c] + P[r][c+1] + P[r+1][c] - P[r][c]`. Then for any query rectangle `(r1, c1)` to `(r2, c2)` (inclusive, 0-indexed): `sum = P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]` in $O(1)$ time (`LeetCode 304`).
10	What is a Difference Array and how does it apply $Q$ range addition updates `[L, R, +val]` in $O(1)$ per update?	The Difference Array `D` is the inverse of Prefix Sums (`D[0] = A[0]`, `D[i] = A[i] - A[i-1]`). To add `val` to every element in `A[L..R]`, simply set `D[L] += val` and `D[R + 1] -= val` in $O(1)$ time! After all $Q$ updates are applied, take the prefix sum of `D` in $O(n)$ time to reconstruct the final array (`LeetCode 370 Range Addition`, `1094 Car Pooling`, `1109 Corporate Flight Bookings`).
11	How do you solve 'Subarray Sum Equals K' (`LeetCode 560`) in $O(n)$ time and $O(n)$ space when the array contains negative numbers?	Because the array can contain negative numbers, a sliding window does NOT work (expanding/shrinking is non-monotonic). Instead, combine Prefix Sums with a Hash Map `freq` initialized to `{0: 1}` (recording how many times each prefix sum has occurred so far). As you iterate and maintain `curr_sum += x`, a subarray ending at the current index sums to $K$ whenever `curr_sum - K` already exists in `freq` (`ans += freq[curr_sum - K]`), then increment `freq[curr_sum] += 1`.
12	Explain the Boyer-Moore Majority Vote Algorithm (`LeetCode 169` & `229`) for finding elements appearing gt; \lfloor n/2 \rfloor$ or gt; \lfloor n/3 \rfloor$ times in $O(n)$ time and $O(1)$ space.	Intuition: Pairing each occurrence of the majority element with a distinct non-majority element cancels them out, leaving the majority element standing. Maintain `candidate = None, count = 0`. For each `x`: if `count == 0`, set `candidate = x`; then `count += (1 if x == candidate else -1)`. (If a majority isn't guaranteed, verify `candidate` with a second counting pass). For gt; \lfloor n/3 \rfloor$ (`LC 229`), there can be at most 2 such elements—maintain 2 candidates and 2 counters, decrementing both only when `x` matches neither.
13	What is Auxiliary Space Complexity vs. Total Space Complexity, and how does the recursion call stack affect it?	Total Space Complexity includes both the input storage and extra memory; Auxiliary Space Complexity counts ONLY the extra memory allocated by the algorithm beyond the input (plus output if required). Every active recursive call frame stays on the call stack simultaneously—so a DFS on a skewed binary tree of $n$ nodes uses $O(n)$ auxiliary call-stack space, whereas on a balanced tree it uses $O(\log n)$ space.
14	Why is appending to a Dynamic Array (`std::vector`, Python `list`, Java `ArrayList`) $O(1)$ amortized time even though resizing takes $O(n)$?	When capacity is reached at powers of 2 ($1, 2, 4, 8, \dots, n$), the array allocates a new buffer of size $2n$ and copies $n$ elements. Across $n$ total `append` operations, the total cost is $n$ individual writes plus the geometric sum of copies: $1 + 2 + 4 + 8 + \dots + n/2 + n < 2n$. Dividing total work lt; 3n$ by $n$ operations yields $O(1)$ amortized time per append! (If it grew by a constant $+k$ instead of $\times 2$, total work would be arithmetic $\Theta(n^2)$, or $O(n)$ amortized per append).
15	State the three cases of the Master Theorem for divide-and-conquer recurrences $T(n) = a T(n/b) + f(n)$ where $a \ge 1, b > 1$.	Let $c_{\text{crit}} = \log_b a$ (so work at leaves is $n^{\log_b a}$): Case 1 (Leaf-heavy): If $f(n) = O(n^{c_{\text{crit}} - \epsilon})$, then $T(n) = \Theta(n^{\log_b a})$ (e.g., binary tree traversal $2T(n/2) + O(1) = \Theta(n)$). Case 2 (Balanced across levels): If $f(n) = \Theta(n^{c_{\text{crit}}} \log^k n)$, then $T(n) = \Theta(n^{c_{\text{crit}}} \log^{k+1} n)$ (e.g., Merge Sort $2T(n/2) + \Theta(n) = \Theta(n \log n)$, Binary Search $T(n/2) + \Theta(1) = \Theta(\log n)$). Case 3 (Root-heavy): If $f(n) = \Omega(n^{c_{\text{crit}} + \epsilon})$, then $T(n) = \Theta(f(n))$ (e.g., Quickselect average $T(n/2) + O(n) = \Theta(n)$).
16	What bitwise XOR (`^`) and bit-manipulation tricks (`x & (x - 1)`, `x & -x`) are used in $O(1)$-space array problems?	1. XOR properties: $a \oplus a = 0$, $a \oplus 0 = a$, commutative & associative—so XORing all elements in an array where every number appears twice except one (`Single Number`, `LC 136`) isolates the unique number in $O(n)$ time and $O(1)$ space. 2. `x & (x - 1)` clears the lowest set `1`-bit of `x` (Brian Kernighan's bit count; also tests if $x > 0$ is a power of two via `(x & (x - 1)) == 0`). 3. `x & (-x)` isolates ONLY the lowest set `1`-bit of `x` (used in Fenwick Trees / Binary Indexed Trees and `Single Number III` `LC 260`).
17	Explain the 1D Prefix Sum pattern and how it answers arbitrary range sum queries `sum(L, R)` in $O(1)$ time.	Precompute an array `P` of length $n + 1$ in $O(n)$ time where `P[0] = 0` and `P[i + 1] = P[i] + nums[i]` (so `P[k]` is the sum of the first $k$ elements). Then the sum of any contiguous subarray `nums[L..R]` (inclusive, 0-indexed) is simply `P[R + 1] - P[L]` in $O(1)$ time.
18	How do you solve 'Longest Consecutive Sequence' (`LeetCode 128`) in strict $O(n)$ time instead of $O(n \log n)$ sorting?	Insert all numbers into a Hash Set `num_set` in $O(n)$ time. Iterate over each unique `x` in `num_set`: ONLY start counting a streak if `x - 1 not in num_set` (meaning `x` is the true start of a consecutive sequence!). If `x - 1` is not in the set, walk `curr = x` upward (`while curr + 1 in num_set: curr += 1`) and update `best = max(best, curr - x + 1)`. Every element is visited at most twice (once in outer loop, once in inner `while`), guaranteeing $O(n)$ time!
19	Why does the greedy Two-Pointer approach work for 'Container With Most Water' (`LeetCode 11`) in $O(n)$ time?	Start with widest possible pointers `L = 0, R = n - 1`. The area is $(R - L) \times \min(H[L], H[R])$, which is bottlenecked by the SHORTER line. If $H[L] < H[R]$, moving the taller line $R$ inward can NEVER increase $\min(H[L], H[R'])$ above $H[L]$ while strictly decreasing width $(R' - L)$—so every remaining pair `(L, R')` with that `L` is guaranteed to be worse! Thus we can safely discard the shorter pointer (`L += 1` if $H[L] < H[R]$ else `R -= 1`) at each step.
20	How do you rotate an array of length $n$ to the right by $k$ steps in-place in $O(n)$ time and $O(1)$ space (`LeetCode 189`)?	Use the Three-Reverse Trick! First normalize $k = k \bmod n$. Then: 1. Reverse the entire array `[0 .. n-1]`; 2. Reverse the first $k$ elements `[0 .. k-1]`; 3. Reverse the remaining $n - k$ elements `[k .. n-1]`. Each element is swapped a constant number of times with zero extra space.
21	In 'Longest Repeating Character Replacement' (`LeetCode 424`), why only track `max_freq` in the sliding window?	A window of length `len = R - L + 1` can be turned into all identical characters using at most $k$ replacements if and only if `(R - L + 1) - max_freq <= k`, where `max_freq` is the count of the single most frequent character in the window. Whenever `(R - L + 1) - max_freq > k`, decrement `count[s[L]]` and advance `L += 1` ( shifting the window right by 1 without even needing to recompute `max_freq` downward, because only a strictly larger `max_freq` can ever produce a longer valid window!).
22	How does the Interval Merging / Sweep-Line pattern solve 'Merge Intervals' (`LeetCode 56`) and 'Meeting Rooms II' (`LeetCode 253`)?	Merge Intervals (`LC 56`): Sort intervals by start time $O(n \log n)$; iterate and if `curr.start <= merged[-1].end`, merge by setting `merged[-1].end = max(merged[-1].end, curr.end)`, else append `curr`. Meeting Rooms II (minimum concurrent rooms, `LC 253`): Use a Sweep-Line (separate sorted `starts` and `ends` arrays, or events `(start, +1)` and `(end, -1)` sorted by time with `-1` before `+1` on ties) and track the maximum prefix sum of active meetings in $O(n \log n)$ time.
23	How do you solve 'Product of Array Except Self' (`LeetCode 238`) in $O(n)$ time and $O(1)$ auxiliary space without using the division operator?	Make two passes over the output array `res` (initialized to `1`s): 1. Left-to-right pass: maintain a running `prefix_prod = 1`; at each index $i$, set `res[i] = prefix_prod` and then update `prefix_prod = nums[i]`. 2. Right-to-left pass: maintain a running `suffix_prod = 1`; at each index $i$, multiply `res[i] = suffix_prod` and then update `suffix_prod *= nums[i]`.
24	What is the universal Variable-Size Sliding Window template for finding the Longest vs. Shortest valid subarray/substring?	Initialize `L = 0` and window state (counter/map). Loop `for R in range(n):` 1. Add `A[R]` to window state. 2. For LONGEST valid window: `while window_is_invalid():` remove `A[L]` and `L += 1`; then outside the `while` loop update `ans = max(ans, R - L + 1)`. For SHORTEST valid window (e.g., Minimum Size Subarray Sum `LC 209`): `while window_is_valid():` update `ans = min(ans, R - L + 1)`, remove `A[L]`, and `L += 1`.
25	How does the Opposite-Ends Two Pointers pattern solve `3Sum` (`LeetCode 15`) in $O(n^2)$ time without using a Hash Set for deduplication?	1. Sort the array in $O(n \log n)$. 2. Loop outer index $i$ from $0$ to $n-3$ (if `nums[i] > 0`, break early; if $i > 0$ and `nums[i] == nums[i-1]`, `continue` to skip duplicate anchors). 3. Set `L = i + 1, R = n - 1`. While `L < R`: compute `s = nums[i] + nums[L] + nums[R]`. If `s < 0`, `L += 1`; if `s > 0`, `R -= 1`; if `s == 0`, record triplet, increment `L += 1`, decrement `R -= 1`, and advance `while L < R and nums[L] == nums[L-1]: L += 1` to skip duplicates.
26	Order the common complexity classes from fastest to slowest growth, and map maximum input size $N$ that passes within a ~1-second ($10^8$ ops) interview limit.	$O(1) < O(\log n) < O(\sqrt{n}) < O(n) < O(n \log n) < O(n^2) < O(2^n) < O(n!)$. Input size guide: $N \le 11 \implies O(n!)$; $N \le 20 \implies O(2^n)$ or $O(n 2^n)$ (backtracking/bitmask DP); $N \le 500 \implies O(n^3)$; $N \le 5,000 \implies O(n^2)$; $N \le 2 \times 10^5 \implies O(n \log n)$ (sorting/heap/divide & conquer); $N \le 10^6–10^7 \implies O(n)$; $N > 10^9 \implies O(\log n)$ or $O(1)$.
27	Compare Separate Chaining and Open Addressing (Linear Probing, Quadratic Probing, Double Hashing, Robin Hood Hashing) for Hash Table collision resolution.	Separate Chaining: Each bucket holds a linked list (or balanced tree in Java 8 `HashMap` when chain length $\ge 8$); degrades gracefully at high load factors ($\alpha = n/m > 1$), but has poor CPU cache locality due to pointer chasing. Open Addressing: Stores all entries directly inside the contiguous bucket array for superior CPU L1/L2 cache locality; requires load factor $\alpha < 0.7–0.8$, uses tombstones on deletion, and suffers from primary clustering in Linear Probing (mitigated by Robin Hood Hashing, which swaps entries to equalize probe-sequence lengths, or SwissTable SIMD metadata bytes).
28	Define Big-O ($O$), Big-Omega ($\Omega$), and Big-Theta ($\Theta$) asymptotic notations.	$O(f(n))$ (Asymptotic Upper Bound): The growth rate is no faster than $c \cdot f(n)$ for $n \ge n_0$. $\Omega(f(n))$ (Asymptotic Lower Bound): The growth rate is at least $c \cdot f(n)$. $\Theta(f(n))$ (Asymptotic Tight Bound): The function is bounded both above and below by $f(n)$. Note: In coding interviews, candidates say 'Big-O' to refer to the tightest upper bound of the worst-case (or expected) runtime.
29	What is the Fast-and-Slow (Read/Write) Two-Pointer pattern for in-place array compaction (e.g., `Remove Duplicates from Sorted Array II`, `LeetCode 80`)?	Maintain a `write` pointer for the next valid output position and a `read` pointer scanning the array. To allow at most $k$ duplicates in a sorted array (`k = 2` for LC 80): for each `x` in `nums`: if `write < k` or `x != nums[write - k]`, set `nums[write] = x` and increment `write += 1`. Returns `write` in $O(n)$ time and $O(1)$ space.
30	How do you solve 'Minimum Window Substring' (`LeetCode 76`) in $O(\|S\| + \|T\|)$ time using the `have == need` counter optimization?	Instead of comparing two 52-character frequency maps at every step, count unique required characters in `T`: `need = len(countT)` and `have = 0`. When expanding `R`, if `window[ch] == countT[ch]`, increment `have += 1`. While `have == need` (valid window): record `(R - L + 1)` if smaller than current best, then pop `s[L]` from `window`—if `window[s[L]] < countT[s[L]]`, decrement `have -= 1`—and advance `L += 1`.
31	How does the cyclic negation / index-mapping trick solve 'First Missing Positive' (`LeetCode 41`) in $O(n)$ time and $O(1)$ space?	The first missing positive integer in an array of length $n$ MUST be in $[1, n+1]$. Using Cycle Sort in-place: for each index $i$, while $1 \le \text{nums}[i] \le n$ and `nums[nums[i] - 1] != nums[i]`, swap `nums[i]` into its rightful home index `nums[i] - 1` (each number is placed in its home at most once, so total swaps $\le n$, $O(n)$ time!). Then scan $i = 0 \dots n-1$: the first index where `nums[i] != i + 1` gives answer $i + 1$; otherwise $n + 1$.
32	Why must Hash Map keys in Python (`dict`/`set`) be immutable (`tuple`, `str`, `int`, `frozenset`), and what happens if a custom object mutates its `__hash__` after insertion?	A hash table determines which bucket slot an object lives in by computing `hash(key) & mask` at insertion time. If a key object's value mutated after insertion—changing its `hash(key)`—future lookups for that object would probe a completely different bucket slot and fail to find it, corrupting the hash table invariants. Note: If a custom class overrides `__eq__`, it must also implement a consistent `__hash__` (`a == b` MUST imply `hash(a) == hash(b)`).