Core Concepts

Subsequence — elements in original relative order, not necessarily contiguous. A subarray is always a subsequence; the reverse is false. Partition — rearranging elements so all satisfying a predicate precede all that don't, without sorting.

---

Structural Invariants

---

Types / Variants

---

Traversals & Access Patterns

Two-pointer converging — l = 0, r = n-1; advance l or retreat r based on a condition. Requires sorted array or symmetric structure. Terminates when l >= r. Two-pointer parallel (fast/slow) — both pointers move forward; fast skips elements the slow pointer should not see. Used for in-place filtering, remove-duplicates, partition. Sliding window (variable size) — l and r both move forward only; shrink from left while a constraint is violated. Total pointer moves = O(n) because l never passes r and neither decrements. Index jumping — i = arr[i] or i += arr[i]. Used for cycle detection (Floyd's), jump game reachability, cyclic sort.

---

Topic-Specific Operations

---

Key Algorithms

Kadane's Algorithm

Key insight: at each position, the best subarray ending here is either arr[i] alone (start fresh) or arr[i] added to the best subarray ending at i-1. Track overall max separately.

Dutch National Flag (Three-Way Partition)

Partitions an array into three groups (e.g., 0s, 1s, 2s) in O(n) time, O(1) space. Used for Sort Colors and any 3-value rearrangement. Three pointers: lo (boundary of group 0), mid (current), hi (boundary of group 2). Swap arr[mid] based on its value; advance mid only when it lands in group 1.

Boyer-Moore Voting

Finds the majority element (appears > n/2 times) in O(n) time, O(1) space.

count = 0
for x in arr:
    if count == 0: candidate = x
    count += 1 if x == candidate else -1

Cyclic Sort

Key insight: arr[i] belongs at index arr[i] - 1; swap until arr[i] is at its correct position, then advance.

Quickselect

Finds the kth smallest element in O(n) average, O(n²) worst. Partitions around a pivot; recurse only into the relevant half.

Difference Array

For range add queries followed by a final read. D[l] += v, D[r+1] -= v applies the update in O(1). Reconstruct with prefix sum in O(n). O(n) total for q updates: O(n + q) vs O(nq) for naive.

Counting Sort / Frequency Map

When values are in a bounded range [0, k]. Count occurrences in O(n); reconstruct in O(n + k). Stable. Breaks when k >> n.

---

Advanced Techniques

Coordinate Compression

Solves: problems where values span a huge range (e.g., up to 10⁹) but there are only n distinct values; needed before applying array-indexed structures like BIT or segment tree. Mechanism: sort and deduplicate values, assign rank 0..m-1; replace each value with its rank. Queries and updates use ranks. When to prefer: value range >> n; otherwise just use values directly as indices. Complexity: O(n log n) for sorting.

Sparse Table (Range Minimum / Maximum Query)

Solves: static array range min/max in O(1) per query after O(n log n) preprocessing. Mechanism: ST[i][j] = min of arr[i..i + 2^j - 1]. Any range [l, r] covered by two overlapping windows of size 2^k where k = floor(log2(r-l+1)). When to prefer over prefix sum: when the operation is idempotent (min, max, gcd) so overlapping windows are valid; prefix sum handles sum/xor but not min/max. Complexity: O(n log n) space and build, O(1) query. Not suitable for updates.

Offline Query Processing with Sorting

Solves: range queries that can be answered more efficiently if processed in a specific order (e.g., all queries on a fixed right boundary). Mechanism: sort queries by right endpoint; sweep a pointer across the array and answer queries as their right endpoint is reached. Often combined with a hash map or prefix structure. When to prefer over online processing: when queries are given upfront and no interleaving with updates; allows amortized O(n + q) solutions where online would need O(q log n). Complexity: O((n + q) log(n + q)) including sort.

Two-Pointer with Monotonic Invariant

Solves: "longest subarray where max - min ≤ k", "number of subarrays with property P" where P is monotone in window size. Mechanism: combine sliding window with a monotonic deque to track max and min simultaneously. Window shrinks when invariant breaks; deque evicts stale or dominated elements. When to prefer: the window condition involves both maximum and minimum simultaneously; simple sliding window without auxiliary structure cannot decide shrink/grow correctly. Complexity: O(n) with deque.

---

Problem Taxonomy

By Problem Category

Problem Signal → Technique

---

Common Patterns

---

Edge Cases & Pitfalls

• Single element: two-pointer loops with l < r or l != r skip the element; sliding window of size 1 must still execute once.

• All identical values: two-pointer deduplication (3Sum) must skip duplicate values at both pointers after placing a candidate; otherwise produces duplicate triplets.

• Two-pointer termination: use l < r (not l <= r) for converging pointers to avoid processing the same element twice; use l <= r in binary search where single-element windows are valid.

• Off-by-one in window slide: when sliding a fixed window from position i to i+1, remove element at i - k (not i - k + 1); draw a concrete example with k=3.

• Modifying array during iteration: backward scan range(n-1, -1, -1) is safe for in-place removal; forward scan shifts indices and causes elements to be skipped.

• Integer overflow: Python has arbitrary precision, so sum(arr) never overflows; in Java/C++, use long for sums of int arrays.

• Midpoint overflow (Java/C++): mid = l + (r - l) // 2, not (l + r) // 2, to avoid overflow when l + r > MAX_INT.

• Python [[val] * cols] * rows trap: creates one list shared across all rows; mutations to one row affect all. Use [[val] * cols for _ in range(rows)].

• Binary search on rotated array: must determine which half is sorted before deciding which side to search; checking arr[l] <= arr[mid] (not <) handles the case where l == mid.

---

Implementation Notes

• arr[l:r] creates a copy — O(r-l) time and space. In tight loops, track l and r as indices instead.
• arr[-1] is the last element; arr[-k:] is the last k elements. Useful but can obscure bugs if k is accidentally 0 (returns empty, not full array).
• collections.Counter(arr) builds a frequency map in O(n); .most_common(k) returns top k in O(n log k).
• enumerate(arr) gives (index, value) pairs; prefer it over range(len(arr)) for readability.
• bisect.bisect_left(arr, x) returns the leftmost position to insert x keeping arr sorted (lower bound). bisect_right returns rightmost (upper bound). Both are O(log n).
• zip(arr, arr[1:]) iterates consecutive pairs without index arithmetic.

---

Cross-Topic Relations

---

Interview Reference

Must-Know Problems

Subarray / Kadane's

• Maximum Subarray (LC 53) — Kadane's baseline
• Maximum Product Subarray (LC 152) — track both max and min (negative × negative)
• Subarray Sum Equals K (LC 560) — prefix sum + hash map
• Minimum Size Subarray Sum (LC 209) — variable sliding window

Prefix Sum / Range

• Subarray Sum Divisible by K (LC 974) — prefix sum mod k

Two Pointers / Pair Sum

• Two Sum II - Input Array Is Sorted (LC 167) — converging two pointers
• 3Sum (LC 15) — sort + converging two pointers with dedup
• Container With Most Water (LC 11) — shrink the shorter side
• Trapping Rain Water (LC 42) — two-pass or two-pointer

Partition / Rearrangement

• Sort Colors (LC 75) — Dutch National Flag
• Move Zeroes (LC 283) — fast/slow two-pointer
• Rotate Array (LC 189) — triple reverse

Missing / Duplicate

• Find the Duplicate Number (LC 287) — Floyd's cycle or binary search
• First Missing Positive (LC 41) — cyclic sort / in-place negation
• Find All Numbers Disappeared in Array (LC 448) — in-place negation

Search in Sorted / Rotated

• Find Minimum in Rotated Sorted Array (LC 153) — binary search for the unsorted half boundary
• Search in Rotated Sorted Array (LC 33) — binary search; identify the sorted half each step
• Find First and Last Position (LC 34) — lower/upper bound binary search

Matrix

• Spiral Matrix (LC 54) — boundary pointer shrink
• Rotate Image (LC 48) — transpose then reverse rows
• Set Matrix Zeroes (LC 73) — use first row/col as markers

Hard / Synthesis

• Median of Two Sorted Arrays (LC 4) — binary search on partition
• Largest Rectangle in Histogram (LC 84) — monotonic stack over array

Additional LeetCode Coverage

• Summary Ranges (LC 228) — scan consecutive runs and emit start/end
• Find Pivot Index (LC 724) — prefix sum; left sum equals total minus left minus current
• Monotonic Array (LC 896) — track whether any increasing/decreasing violation occurs
• Valid Mountain Array (LC 941) — climb strictly up, then strictly down; both sides required
• Replace Elements with Greatest Element on Right Side (LC 1299) — scan from right with running maximum
• Minimum Value to Get Positive Step by Step Sum (LC 1413) — track minimum prefix sum; start must offset it to at least 1
• Kids With the Greatest Number of Candies (LC 1431) — compare each value plus extra candies against global max
• Find the Highest Altitude (LC 1732) — prefix sum over gains; track maximum altitude
• Check if Array Is Sorted and Rotated (LC 1752) — count drops; at most one rotation break is allowed

Common Interview Mistakes

• Initialising Kadane's best = 0 — fails when all elements are negative; must initialise to arr[0].
• Forgetting to skip duplicates in 3Sum after fixing the outer element and after advancing the two pointers — produces duplicate triplets.
• Using l <= r termination for converging two pointers — processes the same element twice; use l < r.
• Declaring O(n) extra space when the problem says in-place — re-read the constraint before coding.
• Building prefix sum with 0-based indexing and querying with off-by-one: P[r] - P[l-1] requires a guard for l = 0; the 1-indexed sentinel P[0] = 0 eliminates this.
• Confusing "subarray" and "subsequence" — wrong solution category entirely.
• Misidentifying which half of a rotated sorted array is sorted — must check arr[l] <= arr[mid] and handle the equals case.
• Not handling the empty-matrix case before accessing matrix[0] — runtime crash in Python.

Typical Follow-Up Escalations