Arrays & Strings
Arrays and strings account for roughly 30% of all interview questions. They are the simplest data structures — contiguous memory with indexed access — but the patterns built on top of them are subtle and powerful. If you master nothing else, master this.
This page is the overview lesson of Module 1 (Linear Data Structures). It teaches every core array pattern once, with a proof and a hand trace for each, and then points down into the deep pages where each pattern gets its own full treatment. Read it end to end before the deep pages; come back to it as the map.
How this module is organised
Module 1 is about data that lives in a line: arrays, strings, stacks, queues, linked lists and the hash tables that index them. The overview you are reading covers the patterns that every later module assumes you know cold. Each deep page below takes one of those patterns and goes further — more variants, more proofs, harder problems.
flowchart TD
OV["Arrays & Strings (this page)"] --> TP["Two Pointers"]
OV --> SW["Sliding Window"]
OV --> PS["Prefix Sums & Difference Arrays"]
OV --> MG["Matrices & 2D Grids"]
OV --> SD["Strings in Depth"]
OV --> ST["Stacks"]
ST --> MS["Monotonic Stack & Deque"]
OV --> QD["Queues, Deques & Ring Buffers"]
QD --> MS
OV --> IV["Intervals & Sweep Line"]
OV --> LL["Linked Lists"]
OV --> HT["Hash Tables"]
HT --> PD["Probabilistic Structures"]
LL --> CAP["Capstone: LRU Cache"]
HT --> CAP
| Deep page | What it adds beyond this overview |
|---|---|
| Module 1 index | The study order, time budget per lesson and how the pieces fit |
| Two Pointers | Same-direction (read/write) pointers, Dutch national flag partition, trapping rain water, 4Sum and the general "k-sum" reduction |
| Sliding Window | Windows with frequency counters, "at most k distinct", the "exactly k = at most k − at most (k−1)" trick, and when a window is not valid |
| Prefix Sums & Difference Arrays | 2D prefix sums, difference arrays for range updates, prefix XOR, prefix sums modulo k, and prefix-sum + hash-map families |
| Matrices & 2D Grids | Row-major layout, in-place rotation and transposition, spiral order, set-matrix-zeroes, 2D search |
| Strings in Depth | Unicode and encodings, immutability costs, string building, parsing state machines, palindromes beyond two pointers |
| Stacks | Parentheses matching, expression evaluation, min-stack, stack-based iterators and call-stack simulation |
| Queues, Deques & Circular Buffers | Ring buffers, queue via two stacks, deque internals (Python's block deque), BFS frontiers |
| Monotonic Stack & Deque | Next greater element, histogram areas, sliding window maximum in |
| Intervals | Merge, insert, sweep line, meeting rooms, the interval scheduling exchange argument |
| Linked Lists | Pointer manipulation, Floyd's proof, reversal patterns, k-group reversal |
| Hash Tables | Hash function design, collision strategies, how dict/HashMap/unordered_map actually work |
| Probabilistic Data Structures | Bloom filters, Count-Min sketch, HyperLogLog — approximate answers in sublinear memory |
| Capstone: LRU Cache | Build a benchmarked LRU cache from a doubly linked list and a hash map |
Prerequisites for this page are light: Complexity Analysis for the Big-O vocabulary and amortized arguments, and How Data Structures Live in Memory for why "contiguous" matters so much.
Pattern triggers
Before any technique, train the reflex: a problem statement contains literal signals that name the pattern. Scan for these first.
| If the problem says… / the input has… | Think of | Why that pattern fits |
|---|---|---|
| "sorted array", "pair that sums to", "remove duplicates in place", "palindrome" | Two pointers | Sortedness (or symmetry) lets one pointer's move rule out a whole set of candidates |
| "contiguous subarray", "substring", "longest/shortest … such that", "at most k" | Sliding window | The property is monotone in the window boundaries: growing never un-breaks a broken window |
| "sum of elements between indices l and r", "many range queries", "count subarrays whose sum is k" | Prefix sums (+ hash map when counting) | Subarray sum = difference of two prefix sums, so one pass answers every range |
| "maximum sum subarray", "best gain", "largest contiguous profit" | Kadane | Optimal substructure on "best subarray ending here" |
| "rotate", "shift by k", "cyclic shift" | Reversal / cyclic replacement | Rotation is a permutation that factors into reversals or cycles |
| "appears more than n/2 times", "majority", "stream, O(1) memory" | Boyer–Moore voting | Pairing off unequal elements cannot eliminate a true majority |
| "numbers from 1 to n", "one missing", "one duplicate", "O(1) extra space, don't modify" | Cyclic sort / Floyd on an array | Values double as indices, so the array is its own hash table (or its own linked list) |
| "frequency", "anagram", "count of each character" | Counting array / hash map | A 26- or 128-slot array is the fastest hash table there is |
| "next greater element", "largest rectangle", "sliding window maximum" | Monotonic stack / deque | Elements that can never be an answer again can be discarded |
| "merge overlapping", "meeting rooms", "intervals" | Sort + sweep | Sorting by start makes overlap a local question |
| "matrix", "grid", "rotate image", "spiral" | Grid traversal | Index arithmetic on row-major storage |
When two triggers fire at once (for example "sorted" and "contiguous"), the stronger constraint usually wins: sorted + pairs is two pointers; contiguous + constraint is a window; contiguous + sum + negatives is prefix sums with a hash map, because the window's monotonicity breaks on negative numbers (see the quiz at the end).
Array Fundamentals
An array stores elements in contiguous memory locations. This gives you:
- access by index
- insertion/deletion (elements must shift)
- search (unsorted), search (sorted)
- Excellent cache locality (elements are adjacent in memory)
Production Note
In most languages, the "array" you use daily is actually a dynamic array (JavaScript Array, Python list, Java ArrayList). These double in capacity when full, giving amortized append but occasionally triggering resizes. Know the difference — it comes up in system design discussions about memory allocation.
Memory layout and why "contiguous" wins
Index access is because the address of element is one multiplication and one addition: . No search, no pointer chase. The second, less obvious win is spatial locality: a CPU does not fetch one element from memory, it fetches a whole cache line (64 bytes on every mainstream x86 and ARM core). A line holds sixteen 32-bit integers, so a sequential scan pays one memory round-trip per sixteen elements, and the hardware prefetcher notices the stride and starts fetching the next lines before you ask. A linked list, by contrast, pays a potential cache miss on every node (see Linked Lists and How Data Structures Live in Memory).
Two layout facts matter for the languages in this course:
- Boxed vs unboxed. A Python
listis an array of pointers to heap objects; anintelement is a 28-byte object elsewhere in memory. Iterating still enjoys locality for the pointer array but not for the values. Javaint[]and C++std::vector<int>store the values inline; JavaArrayList<Integer>andList<Integer>box them. JavaScript engines (V8) store a "packed SMI" array of small integers unboxed until you put a non-integer in it, at which point the whole array transitions to a slower element kind. - Strings are arrays of code units, not of characters. Java and JavaScript strings are UTF-16 code units; Python
stris an array of code points stored as 1, 2 or 4 bytes per character depending on the widest character present (PEP 393); C++std::stringis bytes. "Length" and "index i" mean different things in each. Strings in Depth covers the consequences.
Dynamic arrays: growth factors and amortized O(1) append
A dynamic array keeps a capacity ≥ size buffer. Appending into spare capacity is one store. When size == capacity, it allocates a larger buffer, copies every element and frees the old one. The question is how much larger, and whether the copies make append expensive.
Real implementations disagree on the factor:
| Implementation | Growth rule | Effective factor | Source |
|---|---|---|---|
CPython list | new = size + (size >> 3) + 6, rounded down to a multiple of 4 | ≈ 1.125× (plus a constant) | Objects/listobject.c, list_resize |
Java ArrayList | old + (old >> 1) | 1.5× | java.util.ArrayList#grow via ArraysSupport.newLength |
C++ std::vector (libstdc++, libc++) | 2 × old | 2× | bits/stl_vector.h _M_check_len; libc++ __recommend |
C++ std::vector (MSVC STL) | old + old / 2 | 1.5× | <vector> _Calculate_growth |
| Go slices | 2× until 256 elements, then smoothly down toward 1.25× | 2× → 1.25× | runtime/slice.go growslice (Go 1.18+) |
Rust Vec | max(2 × old, 4) for small element types | 2× | alloc/src/raw_vec.rs grow_amortized |
V8 JSArray backing store | old + old / 2 + 16 | 1.5× (+16) | src/objects/js-objects.h NewElementsCapacity |
Why not always double? Doubling wastes up to 50% of the buffer and, because each new buffer is bigger than the sum of all previous ones, a naive allocator can never reuse the freed blocks for the next growth. A factor below the golden ratio () makes the sum of previous buffers eventually exceed the next request, so freed memory can be reused; this is the argument Facebook's folly::FBVector documentation gives for 1.5. CPython's small factor trades more copies for tighter memory, which fits its boxed-pointer arrays.
You can watch CPython grow a list by reading its allocated size:
import sys
def capacity_steps(n: int) -> list[tuple[int, int]]:
"""Return (length, implied capacity) at each point the list's buffer grew.
Implied capacity = (allocated bytes - header) / 8 on a 64-bit build."""
lst: list[int] = []
header = sys.getsizeof(lst) # the empty list's header size
steps, last = [], header
for i in range(1, n + 1):
lst.append(i)
size = sys.getsizeof(lst)
if size != last:
steps.append((i, (size - header) // 8))
last = size
return steps
steps = capacity_steps(60)
lengths = [length for length, _ in steps]
caps = [cap for _, cap in steps]
# Far fewer resizes than appends, and capacity is non-decreasing.
assert len(steps) < 60 // 4
assert caps == sorted(caps)
assert all(cap >= length for length, cap in steps)
print("growth points:", steps)
# On CPython 3.12-3.14 (64-bit) this prints
# [(1, 4), (5, 8), (9, 16), (17, 24), (25, 32), (33, 40), (41, 52), (53, 64)]
On CPython 3.14 the output is [(1, 4), (5, 8), (9, 16), (17, 24), (25, 32), (33, 40), (41, 52), (53, 64)]: eight resizes for sixty appends, exactly as size + size/8 + 6 rounded to a multiple of four predicts.
Amortized analysis by the aggregate method. Take the simplest case, doubling from capacity 1. Appending elements triggers copies at sizes . Total elements copied:
Add the stores themselves and the whole sequence costs fewer than elementary operations, so the amortized cost per append is below 3, a constant. The same bound holds for any factor : the copies form a geometric series with ratio , summing to at most . For that is copies, for it is — CPython's small factor costs about three times more copying than doubling, in exchange for memory. For 17 appends with doubling the copy total is , matching the bound.
Two consequences you should be able to recite:
- A single append can still cost . If your system has a latency budget per operation (a game frame, a real-time audio callback), amortized is not good enough; pre-size the array (
reserve,ensureCapacity,[None] * n) or use a structure with worst-case append such as a chunked deque. - Growth by a constant addend (say, +16 each time) is total — the copies form an arithmetic series. Any geometric factor beats any additive rule asymptotically; this is the whole point of the analysis in Complexity Analysis.
Inserting in the middle is a different story: every element after the insertion point shifts, so it is no matter the growth policy. When a problem needs many middle insertions, the answer is a different structure — a linked list if you hold the node, a balanced tree or a gap buffer if you do not.
Pattern 1: Two Pointers
The two-pointer technique uses two indices that move through the array, typically from opposite ends or from the same starting point. It converts brute-force solutions into single-pass solutions.
When to Use
- Sorted array problems (pair sum, triplet sum)
- Removing duplicates in-place
- Partitioning arrays
- Palindrome checking
Two shapes recur. Opposite ends (left at 0, right at , move toward each other) suits sorted pair problems and palindromes. Same direction (a slow "write" pointer and a fast "read" pointer) suits in-place filtering: remove duplicates, move zeroes, partition. The deep page Two Pointers treats the second shape and the three-way Dutch national flag partition in full; here the focus is the opposite-ends shape and its proof.
Classic Problem: Two Sum (Sorted Array)
Given a sorted array, find two numbers that add up to a target.
def two_sum_sorted(nums: list[int], target: int) -> tuple[int, int]:
left, right = 0, len(nums) - 1
while left < right:
current_sum = nums[left] + nums[right]
if current_sum == target:
return (left, right)
elif current_sum < target:
left += 1 # need a bigger sum
else:
right -= 1 # need a smaller sum
return (-1, -1) # no solution found
# --- self-check (same data in all four languages) ---
assert two_sum_sorted([1, 2, 4, 7, 11, 15], 15) == (2, 4)
assert two_sum_sorted([2, 7, 11, 15], 9) == (0, 1)
assert two_sum_sorted([1, 2, 3], 100) == (-1, -1)
assert two_sum_sorted([-3, -1, 0, 2, 5], -1) == (0, 3)
print("two_sum_sorted OK")
public class TwoSumSorted {
static int[] twoSumSorted(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) return new int[]{left, right};
if (sum < target) left++; // need a bigger sum
else right--; // need a smaller sum
}
return new int[]{-1, -1};
}
static void check(int[] got, int a, int b) {
if (got[0] != a || got[1] != b)
throw new AssertionError("expected (" + a + "," + b + ") got (" + got[0] + "," + got[1] + ")");
}
public static void main(String[] args) {
check(twoSumSorted(new int[]{1, 2, 4, 7, 11, 15}, 15), 2, 4);
check(twoSumSorted(new int[]{2, 7, 11, 15}, 9), 0, 1);
check(twoSumSorted(new int[]{1, 2, 3}, 100), -1, -1);
check(twoSumSorted(new int[]{-3, -1, 0, 2, 5}, -1), 0, 3);
System.out.println("twoSumSorted OK");
}
}
#include <cassert>
#include <iostream>
#include <utility>
#include <vector>
std::pair<int, int> twoSumSorted(const std::vector<int>& nums, int target) {
int left = 0, right = static_cast<int>(nums.size()) - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) return {left, right};
if (sum < target) ++left; // need a bigger sum
else --right; // need a smaller sum
}
return {-1, -1};
}
int main() {
assert(twoSumSorted({1, 2, 4, 7, 11, 15}, 15) == std::make_pair(2, 4));
assert(twoSumSorted({2, 7, 11, 15}, 9) == std::make_pair(0, 1));
assert(twoSumSorted({1, 2, 3}, 100) == std::make_pair(-1, -1));
assert(twoSumSorted({-3, -1, 0, 2, 5}, -1) == std::make_pair(0, 3));
std::cout << "twoSumSorted OK\n";
}
import assert from "node:assert/strict";
function twoSumSorted(nums: number[], target: number): [number, number] {
let left = 0;
let right = nums.length - 1;
while (left < right) {
const sum = nums[left] + nums[right];
if (sum === target) {
return [left, right];
} else if (sum < target) {
left++; // need a bigger sum → move left pointer right
} else {
right--; // need a smaller sum → move right pointer left
}
}
return [-1, -1]; // no solution found
}
// --- self-check ---
assert.deepEqual(twoSumSorted([1, 2, 4, 7, 11, 15], 15), [2, 4]);
assert.deepEqual(twoSumSorted([2, 7, 11, 15], 9), [0, 1]);
assert.deepEqual(twoSumSorted([1, 2, 3], 100), [-1, -1]);
assert.deepEqual(twoSumSorted([-3, -1, 0, 2, 5], -1), [0, 3]);
console.log("twoSumSorted OK");
Complexity: time, space.
Why it works: Since the array is sorted, moving the left pointer increases the sum and moving the right pointer decreases it. We're guaranteed to find the pair if it exists because we never skip a valid combination.
Trace: two-sum on a sorted array
nums = [1, 2, 4, 7, 11, 15], target = 15. Each row is one loop iteration (computed by script).
| step | left | right | nums[left] | nums[right] | sum | action |
|---|---|---|---|---|---|---|
| 1 | 0 | 5 | 1 | 15 | 16 | sum > target, right-- |
| 2 | 0 | 4 | 1 | 11 | 12 | sum < target, left++ |
| 3 | 1 | 4 | 2 | 11 | 13 | sum < target, left++ |
| 4 | 2 | 4 | 4 | 11 | 15 | found, return (2, 4) |
Four iterations instead of the pairs brute force would examine. The total number of iterations is at most because every iteration moves exactly one pointer one step and they start apart.
Proof: why two pointers never skips the answer
The informal argument above ("we never skip a valid combination") deserves a precise statement, because the same elimination argument underlies every opposite-ends two-pointer algorithm.
Claim. If a pair with and exists, the algorithm returns a valid pair.
Invariant. At the start of every iteration, and for some valid pair . In words: a solution still lies inside the closed window .
Proof by induction on iterations. Initially and . Suppose the invariant holds and the algorithm does not return this iteration. Two cases.
- . Then for every , by sortedness. So index cannot be the smaller index of any solution inside the window; in particular , hence and incrementing it preserves .
- . Symmetrically, cannot be the larger index of any solution, so and decrementing preserves the invariant.
The loop ends either by returning (a correct pair, since it checks the sum) or when , which contradicts . So if a solution exists the loop must return one.
The key move — "this index can be ruled out as a participant in any remaining solution" — is what makes two pointers an elimination algorithm in disguise: each step discards a full row or column of the pair matrix, which is why steps suffice.
Classic Problem: Container With Most Water
Given heights, find two lines that form a container holding the most water.
def max_area(height: list[int]) -> int:
left, right = 0, len(height) - 1
max_water = 0
while left < right:
width = right - left
h = min(height[left], height[right])
max_water = max(max_water, width * h)
if height[left] < height[right]:
left += 1
else:
right -= 1
return max_water
# --- self-check ---
assert max_area([1, 8, 6, 2, 5, 4, 8, 3, 7]) == 49
assert max_area([1, 1]) == 1
assert max_area([4, 3, 2, 1, 4]) == 16
assert max_area([1, 2, 1]) == 2
print("max_area OK")
public class MaxArea {
static int maxArea(int[] height) {
int left = 0, right = height.length - 1, best = 0;
while (left < right) {
int width = right - left;
int h = Math.min(height[left], height[right]);
best = Math.max(best, width * h);
// Move the pointer at the shorter line: moving the taller
// one can never increase the area since width shrinks.
if (height[left] < height[right]) left++;
else right--;
}
return best;
}
public static void main(String[] args) {
if (maxArea(new int[]{1, 8, 6, 2, 5, 4, 8, 3, 7}) != 49) throw new AssertionError();
if (maxArea(new int[]{1, 1}) != 1) throw new AssertionError();
if (maxArea(new int[]{4, 3, 2, 1, 4}) != 16) throw new AssertionError();
if (maxArea(new int[]{1, 2, 1}) != 2) throw new AssertionError();
System.out.println("maxArea OK");
}
}
#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
int maxArea(const std::vector<int>& height) {
int left = 0, right = static_cast<int>(height.size()) - 1, best = 0;
while (left < right) {
int width = right - left;
int h = std::min(height[left], height[right]);
best = std::max(best, width * h);
if (height[left] < height[right]) ++left;
else --right;
}
return best;
}
int main() {
assert(maxArea({1, 8, 6, 2, 5, 4, 8, 3, 7}) == 49);
assert(maxArea({1, 1}) == 1);
assert(maxArea({4, 3, 2, 1, 4}) == 16);
assert(maxArea({1, 2, 1}) == 2);
std::cout << "maxArea OK\n";
}
import assert from "node:assert/strict";
function maxArea(height: number[]): number {
let left = 0;
let right = height.length - 1;
let maxWater = 0;
while (left < right) {
const width = right - left;
const h = Math.min(height[left], height[right]);
maxWater = Math.max(maxWater, width * h);
// Move the pointer at the shorter line — moving the taller
// line can never increase the area since width is shrinking
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return maxWater;
}
// --- self-check ---
assert.equal(maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]), 49);
assert.equal(maxArea([1, 1]), 1);
assert.equal(maxArea([4, 3, 2, 1, 4]), 16);
assert.equal(maxArea([1, 2, 1]), 2);
console.log("maxArea OK");
Complexity: time, space.
Trace on [1, 8, 6, 2, 5, 4, 8, 3, 7] (the LeetCode example; answer 49):
| left | right | width | min height | area | move |
|---|---|---|---|---|---|
| 0 | 8 | 8 | 1 | 8 | left++ |
| 1 | 8 | 7 | 7 | 49 | right-- |
| 1 | 7 | 6 | 3 | 18 | right-- |
| 1 | 6 | 5 | 8 | 40 | right-- |
| 1 | 5 | 4 | 4 | 16 | right-- |
| 1 | 4 | 3 | 5 | 15 | right-- |
| 1 | 3 | 2 | 2 | 4 | right-- |
| 1 | 2 | 1 | 6 | 6 | right-- |
Why moving the shorter line is safe. Suppose . Any container that keeps left and uses some has width strictly smaller and height at most (the min cannot exceed the shorter wall), so its area is strictly smaller than the current one, which we have already recorded. Therefore no unexamined container with left as its left wall can beat the best so far, and left can be retired. This is the same elimination argument as two-sum, with "area cannot improve" replacing "sum cannot match".
Three Sum Pattern
For problems requiring three elements (like 3Sum), fix one element and run two pointers on the rest:
def three_sum(nums: list[int]) -> list[list[int]]:
nums.sort()
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue # skip duplicates
left, right = i + 1, len(nums) - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total == 0:
result.append([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left + 1]:
left += 1
while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1
elif total < 0:
left += 1
else:
right -= 1
return result
# --- self-check ---
assert three_sum([-1, 0, 1, 2, -1, -4]) == [[-1, -1, 2], [-1, 0, 1]]
assert three_sum([0, 0, 0, 0]) == [[0, 0, 0]]
assert three_sum([1, 2, 3]) == []
print("three_sum OK")
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class ThreeSum {
static List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue; // skip duplicates
int left = i + 1, right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
result.add(List.of(nums[i], nums[left], nums[right]));
while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 1]) right--;
left++;
right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return result;
}
public static void main(String[] args) {
List<List<Integer>> r = threeSum(new int[]{-1, 0, 1, 2, -1, -4});
if (!r.equals(List.of(List.of(-1, -1, 2), List.of(-1, 0, 1)))) throw new AssertionError(r);
if (!threeSum(new int[]{0, 0, 0, 0}).equals(List.of(List.of(0, 0, 0)))) throw new AssertionError();
if (!threeSum(new int[]{1, 2, 3}).isEmpty()) throw new AssertionError();
System.out.println("threeSum OK");
}
}
#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
std::vector<std::vector<int>> threeSum(std::vector<int> nums) {
std::sort(nums.begin(), nums.end());
std::vector<std::vector<int>> result;
int n = static_cast<int>(nums.size());
for (int i = 0; i + 2 < n; ++i) {
if (i > 0 && nums[i] == nums[i - 1]) continue; // skip duplicates
int left = i + 1, right = n - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
result.push_back({nums[i], nums[left], nums[right]});
while (left < right && nums[left] == nums[left + 1]) ++left;
while (left < right && nums[right] == nums[right - 1]) --right;
++left;
--right;
} else if (sum < 0) {
++left;
} else {
--right;
}
}
}
return result;
}
int main() {
std::vector<std::vector<int>> expected = {{-1, -1, 2}, {-1, 0, 1}};
assert(threeSum({-1, 0, 1, 2, -1, -4}) == expected);
std::vector<std::vector<int>> zeros = {{0, 0, 0}};
assert(threeSum({0, 0, 0, 0}) == zeros);
assert(threeSum({1, 2, 3}).empty());
std::cout << "threeSum OK\n";
}
import assert from "node:assert/strict";
function threeSum(nums: number[]): number[][] {
nums.sort((a, b) => a - b);
const result: number[][] = [];
for (let i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] === nums[i - 1]) continue; // skip duplicates
let left = i + 1;
let right = nums.length - 1;
while (left < right) {
const sum = nums[i] + nums[left] + nums[right];
if (sum === 0) {
result.push([nums[i], nums[left], nums[right]]);
while (left < right && nums[left] === nums[left + 1]) left++;
while (left < right && nums[right] === nums[right - 1]) right--;
left++;
right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return result;
}
// --- self-check ---
assert.deepEqual(threeSum([-1, 0, 1, 2, -1, -4]), [[-1, -1, 2], [-1, 0, 1]]);
assert.deepEqual(threeSum([0, 0, 0, 0]), [[0, 0, 0]]);
assert.deepEqual(threeSum([1, 2, 3]), []);
console.log("threeSum OK");
Complexity: time (sort + nested two-pointer), extra space (ignoring output).
The duplicate-skipping lines are where most wrong submissions come from. Skipping nums[i] == nums[i-1] prevents the same first element from generating the same triples twice; the inner skips after a hit prevent the same (left, right) values from being reported again. Both are only valid because the array is sorted, which groups duplicates. The general "k-sum" reduction (fix one, recurse on k−1, two pointers at k = 2) is on the Two Pointers page.
Pattern 2: Sliding Window
The sliding window maintains a "window" of elements as it moves across the array. It is the go-to technique for subarray/substring problems.
When to Use
- "Find the longest/shortest subarray with property X"
- "Find all subarrays/substrings matching a condition"
- Contiguous sequence problems with a constraint
The condition under the hood is monotonicity of the predicate in the window boundaries: if a window is "bad" (violates the constraint), every window that contains it is also bad; equivalently, shrinking a bad window from the left is the only way to make it good again. Sum ≥ target with non-negative elements, "at most k distinct characters", "no repeated character" all have this property. "Sum equals exactly k" with negative numbers does not — extending the window can make the sum go up or down — which is why that problem needs prefix sums and a hash map instead (Pattern 3).
Fixed-Size Window
graph LR
subgraph "Array: [2, 1, 5, 1, 3, 2]"
direction LR
A["Window k=3"] --> B["[2,1,5] → sum=8"]
B --> C["[1,5,1] → sum=7"]
C --> D["[5,1,3] → sum=9"]
D --> E["[1,3,2] → sum=6"]
end
def max_sum_subarray(nums: list[int], k: int) -> int:
window_sum = sum(nums[:k])
max_sum = window_sum
for i in range(k, len(nums)):
window_sum += nums[i] - nums[i - k]
max_sum = max(max_sum, window_sum)
return max_sum
# --- self-check ---
assert max_sum_subarray([2, 1, 5, 1, 3, 2], 3) == 9
assert max_sum_subarray([1, 2, 3, 4, 5], 1) == 5
assert max_sum_subarray([5, -1, -2, 7], 2) == 5
assert max_sum_subarray([1, 2, 3], 3) == 6
print("max_sum_subarray OK")
public class MaxSumSubarray {
static int maxSumSubarray(int[] nums, int k) {
int windowSum = 0;
for (int i = 0; i < k; i++) windowSum += nums[i]; // build the first window
int maxSum = windowSum;
for (int i = k; i < nums.length; i++) {
windowSum += nums[i] - nums[i - k]; // add right, drop left
maxSum = Math.max(maxSum, windowSum);
}
return maxSum;
}
public static void main(String[] args) {
if (maxSumSubarray(new int[]{2, 1, 5, 1, 3, 2}, 3) != 9) throw new AssertionError();
if (maxSumSubarray(new int[]{1, 2, 3, 4, 5}, 1) != 5) throw new AssertionError();
if (maxSumSubarray(new int[]{5, -1, -2, 7}, 2) != 5) throw new AssertionError();
if (maxSumSubarray(new int[]{1, 2, 3}, 3) != 6) throw new AssertionError();
System.out.println("maxSumSubarray OK");
}
}
#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
int maxSumSubarray(const std::vector<int>& nums, int k) {
int windowSum = 0;
for (int i = 0; i < k; ++i) windowSum += nums[i];
int maxSum = windowSum;
for (int i = k; i < static_cast<int>(nums.size()); ++i) {
windowSum += nums[i] - nums[i - k];
maxSum = std::max(maxSum, windowSum);
}
return maxSum;
}
int main() {
assert(maxSumSubarray({2, 1, 5, 1, 3, 2}, 3) == 9);
assert(maxSumSubarray({1, 2, 3, 4, 5}, 1) == 5);
assert(maxSumSubarray({5, -1, -2, 7}, 2) == 5);
assert(maxSumSubarray({1, 2, 3}, 3) == 6);
std::cout << "maxSumSubarray OK\n";
}
import assert from "node:assert/strict";
function maxSumSubarray(nums: number[], k: number): number {
let windowSum = 0;
// Build the initial window
for (let i = 0; i < k; i++) {
windowSum += nums[i];
}
let maxSum = windowSum;
// Slide the window: add the right element, remove the left
for (let i = k; i < nums.length; i++) {
windowSum += nums[i] - nums[i - k];
maxSum = Math.max(maxSum, windowSum);
}
return maxSum;
}
// --- self-check ---
assert.equal(maxSumSubarray([2, 1, 5, 1, 3, 2], 3), 9);
assert.equal(maxSumSubarray([1, 2, 3, 4, 5], 1), 5);
assert.equal(maxSumSubarray([5, -1, -2, 7], 2), 5);
assert.equal(maxSumSubarray([1, 2, 3], 3), 6);
console.log("maxSumSubarray OK");
Complexity: time, space.
A fixed window is really a prefix-sum difference computed incrementally: . Nothing about the predicate matters here; the fixed window works for any associative, invertible aggregate (sum, XOR, product without zeros, counts). It does not work for min or max, which have no inverse — for those you need the monotonic deque.
Variable-Size Window
For variable windows, expand the right boundary until a condition breaks, then shrink the left boundary until the condition is restored.
Classic Problem: Longest Substring Without Repeating Characters
def length_of_longest_substring(s: str) -> int:
char_index: dict[str, int] = {}
max_len = 0
left = 0
for right, char in enumerate(s):
if char in char_index and char_index[char] >= left:
left = char_index[char] + 1
char_index[char] = right
max_len = max(max_len, right - left + 1)
return max_len
# --- self-check ---
assert length_of_longest_substring("abcabcbb") == 3
assert length_of_longest_substring("bbbbb") == 1
assert length_of_longest_substring("pwwkew") == 3
assert length_of_longest_substring("") == 0
assert length_of_longest_substring("abba") == 2
print("length_of_longest_substring OK")
import java.util.HashMap;
import java.util.Map;
public class LongestNoRepeat {
static int lengthOfLongestSubstring(String s) {
Map<Character, Integer> lastIndex = new HashMap<>();
int maxLen = 0, left = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
Integer seen = lastIndex.get(c);
// Only jump if the previous occurrence is inside the current window.
if (seen != null && seen >= left) left = seen + 1;
lastIndex.put(c, right);
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
public static void main(String[] args) {
if (lengthOfLongestSubstring("abcabcbb") != 3) throw new AssertionError();
if (lengthOfLongestSubstring("bbbbb") != 1) throw new AssertionError();
if (lengthOfLongestSubstring("pwwkew") != 3) throw new AssertionError();
if (lengthOfLongestSubstring("") != 0) throw new AssertionError();
if (lengthOfLongestSubstring("abba") != 2) throw new AssertionError();
System.out.println("lengthOfLongestSubstring OK");
}
}
#include <algorithm>
#include <cassert>
#include <iostream>
#include <string>
#include <unordered_map>
int lengthOfLongestSubstring(const std::string& s) {
std::unordered_map<char, int> lastIndex;
int maxLen = 0, left = 0;
for (int right = 0; right < static_cast<int>(s.size()); ++right) {
char c = s[right];
auto it = lastIndex.find(c);
if (it != lastIndex.end() && it->second >= left) left = it->second + 1;
lastIndex[c] = right;
maxLen = std::max(maxLen, right - left + 1);
}
return maxLen;
}
int main() {
assert(lengthOfLongestSubstring("abcabcbb") == 3);
assert(lengthOfLongestSubstring("bbbbb") == 1);
assert(lengthOfLongestSubstring("pwwkew") == 3);
assert(lengthOfLongestSubstring("") == 0);
assert(lengthOfLongestSubstring("abba") == 2);
std::cout << "lengthOfLongestSubstring OK\n";
}
import assert from "node:assert/strict";
function lengthOfLongestSubstring(s: string): number {
const charIndex = new Map<string, number>();
let maxLen = 0;
let left = 0;
for (let right = 0; right < s.length; right++) {
const char = s[right];
// If character was seen and is within the current window, shrink
if (charIndex.has(char) && charIndex.get(char)! >= left) {
left = charIndex.get(char)! + 1;
}
charIndex.set(char, right);
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
// --- self-check ---
assert.equal(lengthOfLongestSubstring("abcabcbb"), 3);
assert.equal(lengthOfLongestSubstring("bbbbb"), 1);
assert.equal(lengthOfLongestSubstring("pwwkew"), 3);
assert.equal(lengthOfLongestSubstring(""), 0);
assert.equal(lengthOfLongestSubstring("abba"), 2);
console.log("lengthOfLongestSubstring OK");
Complexity: time, space where is the alphabet size.
Trace on "abcabcbb" (answer 3). The last index column is the previous position of the character before this step; left jumps only when that position is inside the window.
| right | char | last index | left | window | max |
|---|---|---|---|---|---|
| 0 | a | - | 0 | a | 1 |
| 1 | b | - | 0 | ab | 2 |
| 2 | c | - | 0 | abc | 3 |
| 3 | a | 0 | 1 | bca | 3 |
| 4 | b | 1 | 2 | cab | 3 |
| 5 | c | 2 | 3 | abc | 3 |
| 6 | b | 4 | 5 | cb | 3 |
| 7 | b | 6 | 7 | b | 3 |
The >= left check is the subtle part. The string "abba" exposes it: at right = 3 (the second a), the map says a was last at 0, but left has already moved to 2 because of the double b. Jumping back to left = 1 would re-admit the second b and report length 3 for a window "bba" that contains a repeat. With the check, left stays at 2 and the answer is correctly 2.
The window invariant and its proof
Every variable-size window algorithm maintains the same invariant, and proving it once lets you trust all of them.
Setup. Let be the predicate "the window is good". Assume monotonicity: if is false then is false for every and (bigger windows containing a bad window are bad). Equivalently, for each fixed there is a threshold such that holds exactly when , and is non-decreasing in .
Invariant (for "longest good window"). After processing index , — the smallest left endpoint that makes good — and best equals the longest good window ending at any .
Proof sketch. Induction on . When advances to , the window may have become bad. The shrink loop moves left right one step at a time while the window is bad. It stops at the first with true, which by definition is ; it never needs to move left backwards because by monotonicity. Recording then captures the longest good window ending at , because any longer one would start before and be bad.
Why it is linear. right increments exactly times. left only ever increments, and never beyond right + 1, so it increments at most times in total across the whole run — regardless of how many times the inner while loop fires on any single step. Total pointer moves , so the algorithm is with work per move (plus the cost of updating the counter structure, which is for a hash map or a fixed-alphabet array). This "each pointer moves monotonically, so total moves are bounded" argument is the amortized core of every two-pointer and window technique.
For the "shortest good window" variant (minimum size subarray with sum ≥ target), the roles flip: the window is bad until it reaches the target, then we shrink while it stays good and record each good length. Here is that trace on [2, 3, 1, 2, 4, 3], target 7 (the Try It Yourself Problem 3 below; answer 2):
| right | add | window after shrinking | sum after | shrink steps (each records a length) | best |
|---|---|---|---|---|---|
| 0 | 2 | [2] | 2 | - | - |
| 1 | 3 | [2, 3] | 5 | - | - |
| 2 | 1 | [2, 3, 1] | 6 | - | - |
| 3 | 2 | [3, 1, 2] | 6 | len 4 ok, drop 2 | 4 |
| 4 | 4 | [2, 4] | 6 | len 4 ok, drop 3; len 3 ok, drop 1 | 3 |
| 5 | 3 | [3] | 3 | len 3 ok, drop 2; len 2 ok, drop 4 | 2 |
Notice left moved 0, 0, 0, 1, 2, 2 steps per row — five moves in total for six elements, exactly the "at most total" bound.
Minimum Window Substring
This is the hardest sliding window pattern — find the minimum window in s that contains all characters in t.
from collections import Counter
def min_window(s: str, t: str) -> str:
need = Counter(t)
required = len(need)
have = 0
window_counts: dict[str, int] = {}
result = ""
result_len = float("inf")
left = 0
for right, char in enumerate(s):
window_counts[char] = window_counts.get(char, 0) + 1
if char in need and window_counts[char] == need[char]:
have += 1
while have == required:
if right - left + 1 < result_len:
result_len = right - left + 1
result = s[left:right + 1]
left_char = s[left]
window_counts[left_char] -= 1
if left_char in need and window_counts[left_char] < need[left_char]:
have -= 1
left += 1
return result
# --- self-check ---
assert min_window("ADOBECODEBANC", "ABC") == "BANC"
assert min_window("a", "a") == "a"
assert min_window("a", "aa") == ""
assert min_window("aa", "aa") == "aa"
print("min_window OK")
import java.util.HashMap;
import java.util.Map;
public class MinWindow {
static String minWindow(String s, String t) {
Map<Character, Integer> need = new HashMap<>();
for (char c : t.toCharArray()) need.merge(c, 1, Integer::sum);
int required = need.size(), have = 0, left = 0;
int bestLen = Integer.MAX_VALUE, bestStart = 0;
Map<Character, Integer> window = new HashMap<>();
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
window.merge(c, 1, Integer::sum);
if (need.containsKey(c) && window.get(c).intValue() == need.get(c).intValue()) have++;
while (have == required) {
if (right - left + 1 < bestLen) {
bestLen = right - left + 1;
bestStart = left;
}
char lc = s.charAt(left);
window.merge(lc, -1, Integer::sum);
if (need.containsKey(lc) && window.get(lc) < need.get(lc)) have--;
left++;
}
}
return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestStart, bestStart + bestLen);
}
public static void main(String[] args) {
if (!minWindow("ADOBECODEBANC", "ABC").equals("BANC")) throw new AssertionError();
if (!minWindow("a", "a").equals("a")) throw new AssertionError();
if (!minWindow("a", "aa").equals("")) throw new AssertionError();
if (!minWindow("aa", "aa").equals("aa")) throw new AssertionError();
System.out.println("minWindow OK");
}
}
#include <cassert>
#include <climits>
#include <iostream>
#include <string>
#include <unordered_map>
std::string minWindow(const std::string& s, const std::string& t) {
std::unordered_map<char, int> need, window;
for (char c : t) need[c]++;
int required = static_cast<int>(need.size()), have = 0, left = 0;
int bestLen = INT_MAX, bestStart = 0;
for (int right = 0; right < static_cast<int>(s.size()); ++right) {
char c = s[right];
window[c]++;
auto nit = need.find(c);
if (nit != need.end() && window[c] == nit->second) have++;
while (have == required) {
if (right - left + 1 < bestLen) {
bestLen = right - left + 1;
bestStart = left;
}
char lc = s[left];
window[lc]--;
auto lit = need.find(lc);
if (lit != need.end() && window[lc] < lit->second) have--;
++left;
}
}
return bestLen == INT_MAX ? "" : s.substr(bestStart, bestLen);
}
int main() {
assert(minWindow("ADOBECODEBANC", "ABC") == "BANC");
assert(minWindow("a", "a") == "a");
assert(minWindow("a", "aa") == "");
assert(minWindow("aa", "aa") == "aa");
std::cout << "minWindow OK\n";
}
import assert from "node:assert/strict";
function minWindow(s: string, t: string): string {
const need = new Map<string, number>();
for (const c of t) need.set(c, (need.get(c) || 0) + 1);
let have = 0;
const required = need.size;
const windowCounts = new Map<string, number>();
let result = "";
let resultLen = Infinity;
let left = 0;
for (let right = 0; right < s.length; right++) {
const char = s[right];
windowCounts.set(char, (windowCounts.get(char) || 0) + 1);
if (need.has(char) && windowCounts.get(char) === need.get(char)) {
have++;
}
while (have === required) {
// Update result if this window is smaller
if (right - left + 1 < resultLen) {
resultLen = right - left + 1;
result = s.slice(left, right + 1);
}
// Shrink window from the left
const leftChar = s[left];
windowCounts.set(leftChar, windowCounts.get(leftChar)! - 1);
if (need.has(leftChar) && windowCounts.get(leftChar)! < need.get(leftChar)!) {
have--;
}
left++;
}
}
return result;
}
// --- self-check ---
assert.equal(minWindow("ADOBECODEBANC", "ABC"), "BANC");
assert.equal(minWindow("a", "a"), "a");
assert.equal(minWindow("a", "aa"), "");
assert.equal(minWindow("aa", "aa"), "aa");
console.log("minWindow OK");
Complexity: time, space.
The have / required counter is the trick that keeps each step . Without it you would compare the whole window_counts map against need on every step — per step, overall. have counts how many distinct required characters are currently satisfied and changes only at the exact moment a count crosses its requirement (upwards on expansion, downwards on shrink), so maintaining it is a constant amount of work. Windows with counters, "at most k distinct", and the "exactly k = atMost(k) − atMost(k−1)" identity are developed on the Sliding Window page.
Pattern 3: Prefix Sums
A prefix sum array stores cumulative sums, allowing you to compute the sum of any subarray in time after preprocessing.
def build_prefix_sum(nums: list[int]) -> list[int]:
prefix = [0] * (len(nums) + 1)
for i in range(len(nums)):
prefix[i + 1] = prefix[i] + nums[i]
return prefix
def range_sum(prefix: list[int], left: int, right: int) -> int:
return prefix[right + 1] - prefix[left]
def subarray_sum(nums: list[int], k: int) -> int:
"""Count subarrays summing to k using prefix sum + hash map."""
prefix_count = {0: 1}
current_sum = 0
count = 0
for num in nums:
current_sum += num
if current_sum - k in prefix_count:
count += prefix_count[current_sum - k]
prefix_count[current_sum] = prefix_count.get(current_sum, 0) + 1
return count
# --- self-check ---
p = build_prefix_sum([3, -1, 4, 1, 5, -9])
assert p == [0, 3, 2, 6, 7, 12, 3]
assert range_sum(p, 1, 3) == 4
assert range_sum(p, 0, 5) == 3
assert range_sum(p, 3, 5) == -3
assert subarray_sum([1, 2, 3, -2, 2], 3) == 4
assert subarray_sum([1, 1, 1], 2) == 2
assert subarray_sum([1], 0) == 0
print("prefix sums OK")
import java.util.HashMap;
import java.util.Map;
public class PrefixSums {
static long[] buildPrefixSum(int[] nums) {
long[] prefix = new long[nums.length + 1]; // long: sums can overflow int
for (int i = 0; i < nums.length; i++) prefix[i + 1] = prefix[i] + nums[i];
return prefix;
}
static long rangeSum(long[] prefix, int left, int right) {
return prefix[right + 1] - prefix[left];
}
/** Count subarrays summing to k with prefix sums + hash map. */
static int subarraySum(int[] nums, int k) {
Map<Long, Integer> prefixCount = new HashMap<>();
prefixCount.put(0L, 1);
long sum = 0;
int count = 0;
for (int num : nums) {
sum += num;
count += prefixCount.getOrDefault(sum - k, 0);
prefixCount.merge(sum, 1, Integer::sum);
}
return count;
}
public static void main(String[] args) {
long[] p = buildPrefixSum(new int[]{3, -1, 4, 1, 5, -9});
if (!java.util.Arrays.equals(p, new long[]{0, 3, 2, 6, 7, 12, 3})) throw new AssertionError();
if (rangeSum(p, 1, 3) != 4) throw new AssertionError();
if (rangeSum(p, 0, 5) != 3) throw new AssertionError();
if (rangeSum(p, 3, 5) != -3) throw new AssertionError();
if (subarraySum(new int[]{1, 2, 3, -2, 2}, 3) != 4) throw new AssertionError();
if (subarraySum(new int[]{1, 1, 1}, 2) != 2) throw new AssertionError();
if (subarraySum(new int[]{1}, 0) != 0) throw new AssertionError();
System.out.println("prefix sums OK");
}
}
#include <cassert>
#include <cstdint>
#include <iostream>
#include <unordered_map>
#include <vector>
std::vector<int64_t> buildPrefixSum(const std::vector<int>& nums) {
std::vector<int64_t> prefix(nums.size() + 1, 0);
for (size_t i = 0; i < nums.size(); ++i) prefix[i + 1] = prefix[i] + nums[i];
return prefix;
}
int64_t rangeSum(const std::vector<int64_t>& prefix, int left, int right) {
return prefix[right + 1] - prefix[left];
}
// Count subarrays summing to k with prefix sums + hash map.
int subarraySum(const std::vector<int>& nums, int k) {
std::unordered_map<int64_t, int> prefixCount{{0, 1}};
int64_t sum = 0;
int count = 0;
for (int num : nums) {
sum += num;
auto it = prefixCount.find(sum - k);
if (it != prefixCount.end()) count += it->second;
prefixCount[sum]++;
}
return count;
}
int main() {
auto p = buildPrefixSum({3, -1, 4, 1, 5, -9});
assert((p == std::vector<int64_t>{0, 3, 2, 6, 7, 12, 3}));
assert(rangeSum(p, 1, 3) == 4);
assert(rangeSum(p, 0, 5) == 3);
assert(rangeSum(p, 3, 5) == -3);
assert(subarraySum({1, 2, 3, -2, 2}, 3) == 4);
assert(subarraySum({1, 1, 1}, 2) == 2);
assert(subarraySum({1}, 0) == 0);
std::cout << "prefix sums OK\n";
}
import assert from "node:assert/strict";
function buildPrefixSum(nums: number[]): number[] {
const prefix = new Array(nums.length + 1).fill(0);
for (let i = 0; i < nums.length; i++) {
prefix[i + 1] = prefix[i] + nums[i];
}
return prefix;
}
function rangeSum(prefix: number[], left: number, right: number): number {
return prefix[right + 1] - prefix[left];
}
// Subarray Sum Equals K — count subarrays summing to k
function subarraySum(nums: number[], k: number): number {
const prefixCount = new Map<number, number>();
prefixCount.set(0, 1);
let sum = 0;
let count = 0;
for (const num of nums) {
sum += num;
if (prefixCount.has(sum - k)) {
count += prefixCount.get(sum - k)!;
}
prefixCount.set(sum, (prefixCount.get(sum) || 0) + 1);
}
return count;
}
// --- self-check ---
const p = buildPrefixSum([3, -1, 4, 1, 5, -9]);
assert.deepEqual(p, [0, 3, 2, 6, 7, 12, 3]);
assert.equal(rangeSum(p, 1, 3), 4);
assert.equal(rangeSum(p, 0, 5), 3);
assert.equal(rangeSum(p, 3, 5), -3);
assert.equal(subarraySum([1, 2, 3, -2, 2], 3), 4);
assert.equal(subarraySum([1, 1, 1], 2), 2);
assert.equal(subarraySum([1], 0), 0);
console.log("prefix sums OK");
Complexity: preprocessing, per range query. Subarray sum equals K: time, space.
WARNING
Prefix sums work for sum queries. For min/max range queries, you need a Segment Tree or Sparse Table.
Trace: building and querying a prefix array
nums = [3, -1, 4, 1, 5, -9]. The extra leading zero (prefix has entries) is what makes every range formula uniform — no special case for .
| i | nums[i] | prefix[i+1] = prefix[i] + nums[i] |
|---|---|---|
| 0 | 3 | 0 + 3 = 3 |
| 1 | -1 | 3 + -1 = 2 |
| 2 | 4 | 2 + 4 = 6 |
| 3 | 1 | 6 + 1 = 7 |
| 4 | 5 | 7 + 5 = 12 |
| 5 | -9 | 12 + -9 = 3 |
prefix = [0, 3, 2, 6, 7, 12, 3]. Queries:
| query (l, r) | prefix[r+1] | prefix[l] | sum | check against the raw slice |
|---|---|---|---|---|
| (1, 3) | 7 | 3 | 4 | −1 + 4 + 1 = 4 |
| (0, 5) | 3 | 0 | 3 | whole array = 3 |
| (2, 2) | 6 | 2 | 4 | single element 4 |
| (3, 5) | 3 | 6 | −3 | 1 + 5 − 9 = −3 |
Correctness is a one-line telescoping argument: . Negative numbers are no problem because subtraction of sums is exact; the only hazard is overflow of the running total in fixed-width integers, which is why the Java and C++ versions above accumulate in 64 bits.
Trace: counting subarrays with sum k
nums = [1, 2, 3, -2, 2], k = 3. The map stores how many prefixes have each value. At step , every earlier prefix equal to marks the start of a subarray ending at with sum exactly .
| i | num | running sum | need = sum − k | count of need in map | total | map after |
|---|---|---|---|---|---|---|
| 0 | 1 | 1 | −2 | 0 | 0 | {0: 1, 1: 1} |
| 1 | 2 | 3 | 0 | 1 | 1 | {0: 1, 1: 1, 3: 1} |
| 2 | 3 | 6 | 3 | 1 | 2 | {0: 1, 1: 1, 3: 1, 6: 1} |
| 3 | −2 | 4 | 1 | 1 | 3 | {0: 1, 1: 1, 3: 1, 6: 1, 4: 1} |
| 4 | 2 | 6 | 3 | 1 | 4 | {0: 1, 1: 1, 3: 1, 6: 2, 4: 1} |
The four subarrays are [1,2], [3], [2,3,-2] and [3,-2,2]. Note the order of operations: look up sum - k before inserting the current sum; otherwise a k = 0 query would count the empty subarray at every position. The seed {0: 1} represents the empty prefix and is what lets a subarray that starts at index 0 be counted.
This prefix-sum-plus-hash-map family is huge: subarray sum divisible by k (store sum mod k), longest subarray with equal 0s and 1s (map 0 → −1, store first index of each sum), number of nice subarrays, and more. The Prefix Sums & Difference Arrays page catalogues them and adds difference arrays — the inverse operation, which turns many range updates into each — and 2D prefix sums for rectangle queries, which Matrices & Grids applies to image problems.
Pattern 4: Kadane's Algorithm (Maximum Subarray)
Given an array that may contain negatives, find the contiguous subarray with the largest sum. The problem dates from Ulf Grenander's 1977 work on pattern detection in digitised images; the linear algorithm was found by Jay Kadane in a seminar at Carnegie Mellon and popularised in Jon Bentley's Programming Pearls (Column 8, "Algorithm Design Techniques"). It is the smallest example of dynamic programming you will ever meet, and it recurs in finance (best buy/sell window), genomics (maximum-scoring segments) and anywhere else you need the best run in a signal.
The ladder: brute force → prefix sums → Kadane
- Brute force, : for every pair , sum the slice.
- Prefix sums, : turns each slice sum into ; still pairs.
- Prefix sums, one pass, : for fixed the best is the one that minimises over . Keep a running minimum prefix and the answer is .
- Kadane, , space, no prefix array: define = maximum sum of a subarray that ends exactly at . Then
and the answer is . Only the previous value is needed, so one variable suffices.
| Rung | Time | Space | Idea |
|---|---|---|---|
| All slices | Re-sum every slice | ||
| Prefix + all pairs | slice sums | ||
| Prefix + running min | Best start for each end is the minimum prefix so far | ||
| Kadane | "Best subarray ending here" recurrence |
Trace
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4] (answer 6, the subarray [4, -1, 2, 1]):
| i | nums[i] | best_ending_here = max(nums[i], prev + nums[i]) | best_so_far |
|---|---|---|---|
| 0 | −2 | −2 (start) | −2 |
| 1 | 1 | max(1, −2+1) = 1 | 1 |
| 2 | −3 | max(−3, 1−3) = −2 | 1 |
| 3 | 4 | max(4, −2+4) = 4 | 4 |
| 4 | −1 | max(−1, 4−1) = 3 | 4 |
| 5 | 2 | max(2, 3+2) = 5 | 5 |
| 6 | 1 | max(1, 5+1) = 6 | 6 |
| 7 | −5 | max(−5, 6−5) = 1 | 6 |
| 8 | 4 | max(4, 1+4) = 5 | 6 |
At the running sum is discarded: "start fresh at 4" beats "carry the negative baggage". That is the entire algorithm.
Proof
Claim. equals the maximum sum over all subarrays ending at .
Proof. A subarray ending at either has length 1 (sum ) or is some subarray ending at extended by . In the second case its sum is (sum of a subarray ending at ) , which is maximised by choosing the best subarray ending at — this is the optimal substructure: the extension adds the same constant to every candidate, so it preserves their ordering. Taking the max of the two cases covers all subarrays ending at . Every subarray ends somewhere, so ranges over all subarrays.
Two conventions to settle before coding: with "at least one element required", initialise both variables to (an all-negative array returns its largest element, not 0). If the empty subarray is allowed, initialise to 0 and clamp best_end at 0 — the classic "maximum subarray sum, possibly empty" in competitive programming.
def max_subarray(nums: list[int]) -> int:
best_end = best = nums[0]
for x in nums[1:]:
best_end = max(x, best_end + x) # extend or start fresh
best = max(best, best_end)
return best
def max_subarray_bounds(nums: list[int]) -> tuple[int, int, int]:
"""Kadane that also reports the (start, end) of a winning subarray."""
best_end, best = nums[0], nums[0]
start = best_start = best_end_idx = 0
for i in range(1, len(nums)):
if best_end + nums[i] < nums[i]:
best_end, start = nums[i], i
else:
best_end += nums[i]
if best_end > best:
best, best_start, best_end_idx = best_end, start, i
return best, best_start, best_end_idx
assert max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]) == 6
assert max_subarray([-3, -1, -2]) == -1 # all negative: largest element
assert max_subarray([5]) == 5
assert max_subarray([1, 2, 3, -10, 4, 5]) == 9
assert max_subarray_bounds([-2, 1, -3, 4, -1, 2, 1, -5, 4]) == (6, 3, 6)
print("kadane OK")
public class Kadane {
static int maxSubarray(int[] nums) {
int bestEnd = nums[0], best = nums[0];
for (int i = 1; i < nums.length; i++) {
bestEnd = Math.max(nums[i], bestEnd + nums[i]); // extend or start fresh
best = Math.max(best, bestEnd);
}
return best;
}
/** Returns {bestSum, start, end} of a winning subarray. */
static int[] maxSubarrayBounds(int[] nums) {
int bestEnd = nums[0], best = nums[0], start = 0, bestStart = 0, bestEndIdx = 0;
for (int i = 1; i < nums.length; i++) {
if (bestEnd + nums[i] < nums[i]) { bestEnd = nums[i]; start = i; }
else bestEnd += nums[i];
if (bestEnd > best) { best = bestEnd; bestStart = start; bestEndIdx = i; }
}
return new int[]{best, bestStart, bestEndIdx};
}
public static void main(String[] args) {
if (maxSubarray(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4}) != 6) throw new AssertionError();
if (maxSubarray(new int[]{-3, -1, -2}) != -1) throw new AssertionError();
if (maxSubarray(new int[]{5}) != 5) throw new AssertionError();
if (maxSubarray(new int[]{1, 2, 3, -10, 4, 5}) != 9) throw new AssertionError();
int[] b = maxSubarrayBounds(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4});
if (b[0] != 6 || b[1] != 3 || b[2] != 6) throw new AssertionError();
System.out.println("kadane OK");
}
}
#include <algorithm>
#include <array>
#include <cassert>
#include <iostream>
#include <vector>
int maxSubarray(const std::vector<int>& nums) {
int bestEnd = nums[0], best = nums[0];
for (size_t i = 1; i < nums.size(); ++i) {
bestEnd = std::max(nums[i], bestEnd + nums[i]); // extend or start fresh
best = std::max(best, bestEnd);
}
return best;
}
// Returns {bestSum, start, end} of a winning subarray.
std::array<int, 3> maxSubarrayBounds(const std::vector<int>& nums) {
int bestEnd = nums[0], best = nums[0], start = 0, bestStart = 0, bestEndIdx = 0;
for (int i = 1; i < static_cast<int>(nums.size()); ++i) {
if (bestEnd + nums[i] < nums[i]) { bestEnd = nums[i]; start = i; }
else bestEnd += nums[i];
if (bestEnd > best) { best = bestEnd; bestStart = start; bestEndIdx = i; }
}
return {best, bestStart, bestEndIdx};
}
int main() {
assert(maxSubarray({-2, 1, -3, 4, -1, 2, 1, -5, 4}) == 6);
assert(maxSubarray({-3, -1, -2}) == -1);
assert(maxSubarray({5}) == 5);
assert(maxSubarray({1, 2, 3, -10, 4, 5}) == 9);
auto b = maxSubarrayBounds({-2, 1, -3, 4, -1, 2, 1, -5, 4});
assert((b == std::array<int, 3>{6, 3, 6}));
std::cout << "kadane OK\n";
}
import assert from "node:assert/strict";
function maxSubarray(nums: number[]): number {
let bestEnd = nums[0];
let best = nums[0];
for (let i = 1; i < nums.length; i++) {
bestEnd = Math.max(nums[i], bestEnd + nums[i]); // extend or start fresh
best = Math.max(best, bestEnd);
}
return best;
}
/** Returns [bestSum, start, end] of a winning subarray. */
function maxSubarrayBounds(nums: number[]): [number, number, number] {
let bestEnd = nums[0], best = nums[0], start = 0, bestStart = 0, bestEndIdx = 0;
for (let i = 1; i < nums.length; i++) {
if (bestEnd + nums[i] < nums[i]) { bestEnd = nums[i]; start = i; }
else bestEnd += nums[i];
if (bestEnd > best) { best = bestEnd; bestStart = start; bestEndIdx = i; }
}
return [best, bestStart, bestEndIdx];
}
assert.equal(maxSubarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]), 6);
assert.equal(maxSubarray([-3, -1, -2]), -1);
assert.equal(maxSubarray([5]), 5);
assert.equal(maxSubarray([1, 2, 3, -10, 4, 5]), 9);
assert.deepEqual(maxSubarrayBounds([-2, 1, -3, 4, -1, 2, 1, -5, 4]), [6, 3, 6]);
console.log("kadane OK");
Variants worth knowing. Best time to buy and sell stock is Kadane on the day-to-day differences (or, equivalently, "running minimum price so far"). Maximum product subarray needs both the running max and running min because a negative flips them. Maximum sum circular subarray is , with care for the all-negative case. The full DP view is in Dynamic Programming.
Pattern 5: Rotate an Array Three Ways
Rotate [1, 2, 3, 4, 5, 6, 7] right by k = 3 to get [5, 6, 7, 1, 2, 3, 4]. Element at index moves to index . The problem is trivial with extra memory and surprisingly rich in place.
Way 1 — extra array, time, space: out[(i + k) % n] = nums[i], then copy back. Always correct, always the baseline to mention first.
Way 2 — three reversals, time, space. Reverse the whole array, then reverse the first elements, then reverse the remaining :
| step | operation | array |
|---|---|---|
| 0 | start, k = 3 | [1, 2, 3, 4, 5, 6, 7] |
| 1 | reverse whole | [7, 6, 5, 4, 3, 2, 1] |
| 2 | reverse first k = 3 | [5, 6, 7, 4, 3, 2, 1] |
| 3 | reverse the rest | [5, 6, 7, 1, 2, 3, 4] |
Why it works. Write the array as two blocks where ; the target is . Let denote reversal. Reversing the whole thing gives . Reversing the first elements turns back into ; reversing the last turns back into . Result . Each element is touched exactly twice (two of the three reversals move it), so the constant is small, and the access pattern is sequential — cache-friendly. This is Bentley's "hand rotation" from Programming Pearls; the same identity underlies rotating words in a sentence.
Way 3 — cyclic replacements, time, space, each element moved exactly once. Pick index 0, carry its value to index , carry the displaced value to , and so on; the cycle closes after moves. Then start the next cycle at index 1, and so on, for cycles total. Trace for [1, 2, 3, 4, 5, 6], k = 2 ( cycles):
| cycle start | visits (index: value placed) |
|---|---|
| 0 | 2: 1, 4: 3, 0: 5 |
| 1 | 3: 2, 5: 4, 1: 6 |
Result [5, 6, 1, 2, 3, 4]. The count of cycles is because the map decomposes into cosets of the subgroup generated by , which has order . This "juggling" method is in Knuth's TAOCP and in Gries and Mills' 1981 work on in-place rotation; in practice the reversal method is just as fast and far harder to get wrong.
from math import gcd
def rotate_extra(nums: list[int], k: int) -> list[int]:
n = len(nums)
k %= n
out = [0] * n
for i, x in enumerate(nums):
out[(i + k) % n] = x
return out
def rotate_reverse(nums: list[int], k: int) -> None:
"""In place, three reversals."""
n = len(nums)
k %= n
def rev(lo: int, hi: int) -> None: # reverse nums[lo..hi] inclusive
while lo < hi:
nums[lo], nums[hi] = nums[hi], nums[lo]
lo += 1
hi -= 1
rev(0, n - 1)
rev(0, k - 1)
rev(k, n - 1)
def rotate_cycles(nums: list[int], k: int) -> None:
"""In place, each element moved exactly once, gcd(n, k) cycles."""
n = len(nums)
k %= n
if k == 0:
return
for start in range(gcd(n, k)):
cur, carry = start, nums[start]
while True:
nxt = (cur + k) % n
nums[nxt], carry = carry, nums[nxt]
cur = nxt
if cur == start:
break
base = [1, 2, 3, 4, 5, 6, 7]
assert rotate_extra(base, 3) == [5, 6, 7, 1, 2, 3, 4]
a = base[:]; rotate_reverse(a, 3); assert a == [5, 6, 7, 1, 2, 3, 4]
b = base[:]; rotate_cycles(b, 3); assert b == [5, 6, 7, 1, 2, 3, 4]
c = [1, 2, 3, 4, 5, 6]; rotate_cycles(c, 2); assert c == [5, 6, 1, 2, 3, 4]
d = [1, 2]; rotate_reverse(d, 5); assert d == [2, 1] # k > n wraps
e = [1]; rotate_cycles(e, 0); assert e == [1]
print("rotate OK")
import java.util.Arrays;
public class RotateArray {
static int[] rotateExtra(int[] nums, int k) {
int n = nums.length;
k %= n;
int[] out = new int[n];
for (int i = 0; i < n; i++) out[(i + k) % n] = nums[i];
return out;
}
static void reverse(int[] a, int lo, int hi) {
while (lo < hi) { int t = a[lo]; a[lo++] = a[hi]; a[hi--] = t; }
}
static void rotateReverse(int[] nums, int k) { // in place, three reversals
int n = nums.length;
k %= n;
reverse(nums, 0, n - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, n - 1);
}
static int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
static void rotateCycles(int[] nums, int k) { // in place, gcd(n,k) cycles
int n = nums.length;
k %= n;
if (k == 0) return;
for (int start = 0; start < gcd(n, k); start++) {
int cur = start, carry = nums[start];
do {
int nxt = (cur + k) % n;
int tmp = nums[nxt];
nums[nxt] = carry;
carry = tmp;
cur = nxt;
} while (cur != start);
}
}
public static void main(String[] args) {
int[] base = {1, 2, 3, 4, 5, 6, 7};
int[] want = {5, 6, 7, 1, 2, 3, 4};
if (!Arrays.equals(rotateExtra(base, 3), want)) throw new AssertionError();
int[] a = base.clone(); rotateReverse(a, 3); if (!Arrays.equals(a, want)) throw new AssertionError();
int[] b = base.clone(); rotateCycles(b, 3); if (!Arrays.equals(b, want)) throw new AssertionError();
int[] c = {1, 2, 3, 4, 5, 6}; rotateCycles(c, 2); if (!Arrays.equals(c, new int[]{5, 6, 1, 2, 3, 4})) throw new AssertionError();
int[] d = {1, 2}; rotateReverse(d, 5); if (!Arrays.equals(d, new int[]{2, 1})) throw new AssertionError();
int[] e = {1}; rotateCycles(e, 0); if (!Arrays.equals(e, new int[]{1})) throw new AssertionError();
System.out.println("rotate OK");
}
}
#include <algorithm>
#include <cassert>
#include <iostream>
#include <numeric>
#include <vector>
std::vector<int> rotateExtra(const std::vector<int>& nums, int k) {
int n = static_cast<int>(nums.size());
k %= n;
std::vector<int> out(n);
for (int i = 0; i < n; ++i) out[(i + k) % n] = nums[i];
return out;
}
void rotateReverse(std::vector<int>& nums, int k) { // in place, three reversals
int n = static_cast<int>(nums.size());
k %= n;
std::reverse(nums.begin(), nums.end());
std::reverse(nums.begin(), nums.begin() + k);
std::reverse(nums.begin() + k, nums.end());
}
void rotateCycles(std::vector<int>& nums, int k) { // in place, gcd(n,k) cycles
int n = static_cast<int>(nums.size());
k %= n;
if (k == 0) return;
int cycles = std::gcd(n, k);
for (int start = 0; start < cycles; ++start) {
int cur = start, carry = nums[start];
do {
int nxt = (cur + k) % n;
std::swap(nums[nxt], carry);
cur = nxt;
} while (cur != start);
}
}
int main() {
std::vector<int> base = {1, 2, 3, 4, 5, 6, 7};
std::vector<int> want = {5, 6, 7, 1, 2, 3, 4};
assert(rotateExtra(base, 3) == want);
auto a = base; rotateReverse(a, 3); assert(a == want);
auto b = base; rotateCycles(b, 3); assert(b == want);
std::vector<int> c = {1, 2, 3, 4, 5, 6}; rotateCycles(c, 2); assert((c == std::vector<int>{5, 6, 1, 2, 3, 4}));
std::vector<int> d = {1, 2}; rotateReverse(d, 5); assert((d == std::vector<int>{2, 1}));
std::vector<int> e = {1}; rotateCycles(e, 0); assert((e == std::vector<int>{1}));
// The standard library has it too: std::rotate(first, middle, last) rotates left.
auto f = base; std::rotate(f.begin(), f.begin() + (7 - 3), f.end()); assert(f == want);
std::cout << "rotate OK\n";
}
import assert from "node:assert/strict";
function rotateExtra(nums: number[], k: number): number[] {
const n = nums.length;
k %= n;
const out = new Array<number>(n);
for (let i = 0; i < n; i++) out[(i + k) % n] = nums[i];
return out;
}
function reverseRange(a: number[], lo: number, hi: number): void {
while (lo < hi) { const t = a[lo]; a[lo++] = a[hi]; a[hi--] = t; }
}
function rotateReverse(nums: number[], k: number): void { // in place, three reversals
const n = nums.length;
k %= n;
reverseRange(nums, 0, n - 1);
reverseRange(nums, 0, k - 1);
reverseRange(nums, k, n - 1);
}
function gcd(a: number, b: number): number { return b === 0 ? a : gcd(b, a % b); }
function rotateCycles(nums: number[], k: number): void { // in place, gcd(n,k) cycles
const n = nums.length;
k %= n;
if (k === 0) return;
const cycles = gcd(n, k);
for (let start = 0; start < cycles; start++) {
let cur = start, carry = nums[start];
do {
const nxt = (cur + k) % n;
const tmp = nums[nxt];
nums[nxt] = carry;
carry = tmp;
cur = nxt;
} while (cur !== start);
}
}
const base = [1, 2, 3, 4, 5, 6, 7];
const want = [5, 6, 7, 1, 2, 3, 4];
assert.deepEqual(rotateExtra(base, 3), want);
const a = [...base]; rotateReverse(a, 3); assert.deepEqual(a, want);
const b = [...base]; rotateCycles(b, 3); assert.deepEqual(b, want);
const c = [1, 2, 3, 4, 5, 6]; rotateCycles(c, 2); assert.deepEqual(c, [5, 6, 1, 2, 3, 4]);
const d = [1, 2]; rotateReverse(d, 5); assert.deepEqual(d, [2, 1]);
const e = [1]; rotateCycles(e, 0); assert.deepEqual(e, [1]);
console.log("rotate OK");
Always reduce k %= n first: a rotation by is the identity, and a k larger than n will otherwise index out of range in the reversal method. For a left rotation by , rotate right by (or swap the order of the two partial reversals).
Pattern 6: Majority Element (Boyer–Moore Voting)
Given an array with elements where one value appears more than times, find it in time and space. Robert Boyer and J Strother Moore devised the algorithm in 1980 (published as "MJRTY — A Fast Majority Vote Algorithm", 1991), and it is the archetype of a streaming algorithm: one pass, two words of memory.
Mechanics. Keep a candidate and a count. For each element: if count == 0, adopt the element as the candidate with count = 1; else if the element equals the candidate, count += 1; else count -= 1.
| i | x | candidate before | count before | action | candidate after | count after |
|---|---|---|---|---|---|---|
| 0 | 2 | - | 0 | count 0 → adopt x | 2 | 1 |
| 1 | 2 | 2 | 1 | x == candidate, count++ | 2 | 2 |
| 2 | 1 | 2 | 2 | x != candidate, count-- | 2 | 1 |
| 3 | 1 | 2 | 1 | x != candidate, count-- | 2 | 0 |
| 4 | 1 | 2 | 0 | count 0 → adopt x | 1 | 1 |
| 5 | 2 | 1 | 1 | x != candidate, count-- | 1 | 0 |
| 6 | 2 | 1 | 0 | count 0 → adopt x | 2 | 1 |
Input [2, 2, 1, 1, 1, 2, 2]; the candidate at the end is 2, which occurs 4 of 7 times.
Proof. Think of each count -= 1 as pairing the current element with one earlier occurrence of the candidate and discarding both; a count == 0 → adopt starts a fresh group. Every discarded pair consists of two different values, so a true majority value loses at most one copy per pair, while the pair also removes one non- element. Suppose occurs times and let be the number of pairs discarded; the pairs remove exactly elements in total, at most of which are copies of . After all pairing, the survivors are count copies of the final candidate. If the final candidate were not , then all copies of were discarded inside pairs, so , which means elements were discarded — more than exist. Contradiction. So the survivor is .
The verification pass is not optional. If no majority exists the algorithm still returns a candidate — on [1, 2, 3] it returns 3 — so unless the problem guarantees a majority, do a second pass counting the candidate. The generalisation to "elements appearing more than times" keeps candidates (Misra–Gries, 1982) and is the ancestor of the heavy-hitter sketches in Probabilistic Data Structures.
def majority_element(nums: list[int]) -> int:
"""Assumes a majority (> n/2) exists."""
candidate, count = None, 0
for x in nums:
if count == 0:
candidate, count = x, 1
elif x == candidate:
count += 1
else:
count -= 1
return candidate
def majority_or_none(nums: list[int]) -> int | None:
"""Verified version: returns None when no strict majority exists."""
cand = majority_element(nums)
return cand if nums.count(cand) > len(nums) // 2 else None
assert majority_element([2, 2, 1, 1, 1, 2, 2]) == 2
assert majority_element([3, 2, 3]) == 3
assert majority_element([1]) == 1
assert majority_or_none([1, 2, 3]) is None # Boyer-Moore alone would say 3
assert majority_or_none([1, 2, 2]) == 2
print("boyer-moore OK")
public class MajorityElement {
static int majorityElement(int[] nums) { // assumes a majority exists
int candidate = 0, count = 0;
for (int x : nums) {
if (count == 0) { candidate = x; count = 1; }
else if (x == candidate) count++;
else count--;
}
return candidate;
}
/** Verified version: returns null when there is no strict majority. */
static Integer majorityOrNull(int[] nums) {
int cand = majorityElement(nums), occurrences = 0;
for (int x : nums) if (x == cand) occurrences++;
return occurrences > nums.length / 2 ? cand : null;
}
public static void main(String[] args) {
if (majorityElement(new int[]{2, 2, 1, 1, 1, 2, 2}) != 2) throw new AssertionError();
if (majorityElement(new int[]{3, 2, 3}) != 3) throw new AssertionError();
if (majorityElement(new int[]{1}) != 1) throw new AssertionError();
if (majorityOrNull(new int[]{1, 2, 3}) != null) throw new AssertionError();
if (majorityOrNull(new int[]{1, 2, 2}) != 2) throw new AssertionError();
System.out.println("boyer-moore OK");
}
}
#include <algorithm>
#include <cassert>
#include <iostream>
#include <optional>
#include <vector>
int majorityElement(const std::vector<int>& nums) { // assumes a majority exists
int candidate = 0, count = 0;
for (int x : nums) {
if (count == 0) { candidate = x; count = 1; }
else if (x == candidate) ++count;
else --count;
}
return candidate;
}
// Verified version: empty optional when there is no strict majority.
std::optional<int> majorityOrNone(const std::vector<int>& nums) {
int cand = majorityElement(nums);
auto occurrences = std::count(nums.begin(), nums.end(), cand);
if (occurrences > static_cast<long long>(nums.size()) / 2) return cand;
return std::nullopt;
}
int main() {
assert(majorityElement({2, 2, 1, 1, 1, 2, 2}) == 2);
assert(majorityElement({3, 2, 3}) == 3);
assert(majorityElement({1}) == 1);
assert(!majorityOrNone({1, 2, 3}).has_value());
assert(majorityOrNone({1, 2, 2}).value() == 2);
std::cout << "boyer-moore OK\n";
}
import assert from "node:assert/strict";
function majorityElement(nums: number[]): number { // assumes a majority exists
let candidate = 0, count = 0;
for (const x of nums) {
if (count === 0) { candidate = x; count = 1; }
else if (x === candidate) count++;
else count--;
}
return candidate;
}
/** Verified version: null when there is no strict majority. */
function majorityOrNull(nums: number[]): number | null {
const cand = majorityElement(nums);
const occurrences = nums.filter(x => x === cand).length;
return occurrences > Math.floor(nums.length / 2) ? cand : null;
}
assert.equal(majorityElement([2, 2, 1, 1, 1, 2, 2]), 2);
assert.equal(majorityElement([3, 2, 3]), 3);
assert.equal(majorityElement([1]), 1);
assert.equal(majorityOrNull([1, 2, 3]), null);
assert.equal(majorityOrNull([1, 2, 2]), 2);
console.log("boyer-moore OK");
Pattern 7: Cyclic Sort, Missing Numbers and Floyd on an Array
When an array holds values drawn from (or ), the values are also valid indices. That coincidence turns the array into its own hash table — and, read differently, into its own linked list. Three techniques exploit it.
Cyclic sort
Put every value at index by swapping: at position , while is not already at its home, swap it into its home. The displaced element is then examined at the same position.
| step | i | a[i] | correct index a[i]−1 | action | array |
|---|---|---|---|---|---|
| 1 | 0 | 3 | 2 | swap a[0] and a[2] | [5, 1, 3, 4, 2] |
| 2 | 0 | 5 | 4 | swap a[0] and a[4] | [2, 1, 3, 4, 5] |
| 3 | 0 | 2 | 1 | swap a[0] and a[1] | [1, 2, 3, 4, 5] |
| 4 | 0 | 1 | 0 | in place, i++ | [1, 2, 3, 4, 5] |
| 5 | 1 | 2 | 1 | in place, i++ | [1, 2, 3, 4, 5] |
| 6 | 2 | 3 | 2 | in place, i++ | [1, 2, 3, 4, 5] |
| 7 | 3 | 4 | 3 | in place, i++ | [1, 2, 3, 4, 5] |
| 8 | 4 | 5 | 4 | in place, i++ | [1, 2, 3, 4, 5] |
Why it is despite the nested loop. Every swap places at least one element at its final home, and an element at its home is never moved again. So there are at most swaps in total, plus increments of . After a cyclic sort, a single scan finds every index with : those are the missing numbers (and the value sitting there is a duplicate). This solves missing number, find all duplicates, find all disappeared numbers and first missing positive (ignore values outside ) in time and extra space, without the "mark visited by negating" trick that breaks on zeros and non-positive inputs.
Missing number: three one-liners
For with one value missing: (sum formula; use 64-bit); or (XOR cancels every present value — see Bit Manipulation); or cyclic sort and scan. The XOR version never overflows.
Find the duplicate without modifying the array: Floyd on an array
Array of integers in with exactly one value repeated (possibly many times); find it in time, space, without modifying the array. Cyclic sort is out (it mutates), a hash set is out (space). The trick: treat the array as a function and start walking from index 0. Since values are in , you never visit index 0 again, so the walk is a path that enters a cycle. Two indices pointing to the same value means two edges into one node — the duplicate is the entry point of the cycle, and Floyd's tortoise-and-hare finds it.
Trace on [1, 3, 4, 2, 2] (both pointers start at nums[0] = 1):
| step | slow | fast | note |
|---|---|---|---|
| 0 | 1 | 1 | start at nums[0] |
| 1 | 3 | 2 | |
| 2 | 2 | 2 | meet |
Phase 2, one pointer back to the start, both at speed one:
| step | p1 (from nums[0]) | p2 (from meeting) | note |
|---|---|---|---|
| 0 | 1 | 2 | |
| 1 | 3 | 4 | |
| 2 | 2 | 2 | meet → duplicate |
The duplicate is 2. The proof that phase 2 lands on the cycle entry is exactly the proof for linked lists, given in full on the Linked Lists page (the argument); only the "next pointer" has changed from a field to an array lookup. The only subtle point is why the duplicate must be the cycle entry: the entry node is the unique node with two distinct predecessors on the walk (one from the tail, one from inside the cycle), and two predecessors means two indices with .
def cyclic_sort(nums: list[int]) -> None:
"""Values are 1..n; afterwards nums[i] == i + 1 wherever possible."""
i = 0
while i < len(nums):
home = nums[i] - 1
if nums[i] != nums[home]:
nums[i], nums[home] = nums[home], nums[i]
else:
i += 1
def missing_number_xor(nums: list[int]) -> int:
"""nums holds 0..n with one missing."""
x = 0
for i, v in enumerate(nums):
x ^= i ^ v
return x ^ len(nums)
def find_disappeared(nums: list[int]) -> list[int]:
"""All values of 1..n missing from nums (nums may have duplicates)."""
cyclic_sort(nums)
return [i + 1 for i, v in enumerate(nums) if v != i + 1]
def find_duplicate(nums: list[int]) -> int:
"""n+1 values in 1..n, one repeated; O(1) space, array not modified."""
slow = fast = nums[0]
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
p1, p2 = nums[0], slow
while p1 != p2:
p1, p2 = nums[p1], nums[p2]
return p1
a = [3, 1, 5, 4, 2]; cyclic_sort(a); assert a == [1, 2, 3, 4, 5]
assert missing_number_xor([3, 0, 1]) == 2
assert missing_number_xor([0]) == 1
assert find_disappeared([4, 3, 2, 7, 8, 2, 3, 1]) == [5, 6]
assert find_duplicate([1, 3, 4, 2, 2]) == 2
assert find_duplicate([3, 1, 3, 4, 2]) == 3
assert find_duplicate([2, 2, 2, 2, 2]) == 2
print("cyclic sort OK")
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class CyclicSort {
static void cyclicSort(int[] nums) { // values 1..n
int i = 0;
while (i < nums.length) {
int home = nums[i] - 1;
if (nums[i] != nums[home]) { int t = nums[i]; nums[i] = nums[home]; nums[home] = t; }
else i++;
}
}
static int missingNumberXor(int[] nums) { // nums holds 0..n with one missing
int x = nums.length;
for (int i = 0; i < nums.length; i++) x ^= i ^ nums[i];
return x;
}
static List<Integer> findDisappeared(int[] nums) {
cyclicSort(nums);
List<Integer> out = new ArrayList<>();
for (int i = 0; i < nums.length; i++) if (nums[i] != i + 1) out.add(i + 1);
return out;
}
static int findDuplicate(int[] nums) { // Floyd on the array, read-only
int slow = nums[0], fast = nums[0];
do { slow = nums[slow]; fast = nums[nums[fast]]; } while (slow != fast);
int p1 = nums[0], p2 = slow;
while (p1 != p2) { p1 = nums[p1]; p2 = nums[p2]; }
return p1;
}
public static void main(String[] args) {
int[] a = {3, 1, 5, 4, 2}; cyclicSort(a);
if (!Arrays.equals(a, new int[]{1, 2, 3, 4, 5})) throw new AssertionError();
if (missingNumberXor(new int[]{3, 0, 1}) != 2) throw new AssertionError();
if (missingNumberXor(new int[]{0}) != 1) throw new AssertionError();
if (!findDisappeared(new int[]{4, 3, 2, 7, 8, 2, 3, 1}).equals(List.of(5, 6))) throw new AssertionError();
if (findDuplicate(new int[]{1, 3, 4, 2, 2}) != 2) throw new AssertionError();
if (findDuplicate(new int[]{3, 1, 3, 4, 2}) != 3) throw new AssertionError();
if (findDuplicate(new int[]{2, 2, 2, 2, 2}) != 2) throw new AssertionError();
System.out.println("cyclic sort OK");
}
}
#include <cassert>
#include <iostream>
#include <utility>
#include <vector>
void cyclicSort(std::vector<int>& nums) { // values 1..n
size_t i = 0;
while (i < nums.size()) {
int home = nums[i] - 1;
if (nums[i] != nums[home]) std::swap(nums[i], nums[home]);
else ++i;
}
}
int missingNumberXor(const std::vector<int>& nums) { // nums holds 0..n, one missing
int x = static_cast<int>(nums.size());
for (int i = 0; i < static_cast<int>(nums.size()); ++i) x ^= i ^ nums[i];
return x;
}
std::vector<int> findDisappeared(std::vector<int> nums) {
cyclicSort(nums);
std::vector<int> out;
for (int i = 0; i < static_cast<int>(nums.size()); ++i) if (nums[i] != i + 1) out.push_back(i + 1);
return out;
}
int findDuplicate(const std::vector<int>& nums) { // Floyd on the array, read-only
int slow = nums[0], fast = nums[0];
do { slow = nums[slow]; fast = nums[nums[fast]]; } while (slow != fast);
int p1 = nums[0], p2 = slow;
while (p1 != p2) { p1 = nums[p1]; p2 = nums[p2]; }
return p1;
}
int main() {
std::vector<int> a = {3, 1, 5, 4, 2}; cyclicSort(a);
assert((a == std::vector<int>{1, 2, 3, 4, 5}));
assert(missingNumberXor({3, 0, 1}) == 2);
assert(missingNumberXor({0}) == 1);
assert((findDisappeared({4, 3, 2, 7, 8, 2, 3, 1}) == std::vector<int>{5, 6}));
assert(findDuplicate({1, 3, 4, 2, 2}) == 2);
assert(findDuplicate({3, 1, 3, 4, 2}) == 3);
assert(findDuplicate({2, 2, 2, 2, 2}) == 2);
std::cout << "cyclic sort OK\n";
}
import assert from "node:assert/strict";
function cyclicSort(nums: number[]): void { // values 1..n
let i = 0;
while (i < nums.length) {
const home = nums[i] - 1;
if (nums[i] !== nums[home]) { const t = nums[i]; nums[i] = nums[home]; nums[home] = t; }
else i++;
}
}
function missingNumberXor(nums: number[]): number { // nums holds 0..n, one missing
let x = nums.length;
for (let i = 0; i < nums.length; i++) x ^= i ^ nums[i];
return x;
}
function findDisappeared(nums: number[]): number[] {
cyclicSort(nums);
const out: number[] = [];
for (let i = 0; i < nums.length; i++) if (nums[i] !== i + 1) out.push(i + 1);
return out;
}
function findDuplicate(nums: number[]): number { // Floyd on the array, read-only
let slow = nums[0], fast = nums[0];
do { slow = nums[slow]; fast = nums[nums[fast]]; } while (slow !== fast);
let p1 = nums[0], p2 = slow;
while (p1 !== p2) { p1 = nums[p1]; p2 = nums[p2]; }
return p1;
}
const a = [3, 1, 5, 4, 2]; cyclicSort(a); assert.deepEqual(a, [1, 2, 3, 4, 5]);
assert.equal(missingNumberXor([3, 0, 1]), 2);
assert.equal(missingNumberXor([0]), 1);
assert.deepEqual(findDisappeared([4, 3, 2, 7, 8, 2, 3, 1]), [5, 6]);
assert.equal(findDuplicate([1, 3, 4, 2, 2]), 2);
assert.equal(findDuplicate([3, 1, 3, 4, 2]), 3);
assert.equal(findDuplicate([2, 2, 2, 2, 2]), 2);
console.log("cyclic sort OK");
String Manipulation Techniques
String as Character Array
Most string problems reduce to array problems once you treat strings as arrays of characters. Key operations:
| Operation | TypeScript | Python |
|---|---|---|
| Iterate chars | for (const c of s) | for c in s: |
| Check if letter | c >= 'a' && c <= 'z' | c.isalpha() |
| Char → number | s.charCodeAt(i) - 97 | ord(c) - ord('a') |
| Number → char | String.fromCharCode(n + 97) | chr(n + ord('a')) |
| Reverse | s.split('').reverse().join('') | s[::-1] |
The same operations in the other two course languages:
| Operation | Java | C++ |
|---|---|---|
| Iterate chars | for (char c : s.toCharArray()) | for (char c : s) |
| Check if letter | Character.isLetter(c) | std::isalpha(static_cast<unsigned char>(c)) |
| Char → number | s.charAt(i) - 'a' | s[i] - 'a' |
| Number → char | (char) ('a' + n) | static_cast<char>('a' + n) |
| Reverse | new StringBuilder(s).reverse().toString() | std::reverse(s.begin(), s.end()) |
| Build a string in a loop | StringBuilder sb; sb.append(c) | std::string out; out.push_back(c) |
Strings are immutable in three of the four languages
Python str, Java String and JavaScript strings cannot be changed in place; every s += c allocates a new string and copies the old one, so building a string of length by repeated concatenation is in principle. (CPython has an optimisation that resizes in place when the left operand has a reference count of one, and V8 builds a rope of pieces and flattens lazily; neither is a guarantee you should design around.) The idiom is to collect pieces in a list / StringBuilder / array and join once at the end. C++ std::string is mutable and push_back is amortised for the same dynamic-array reason as std::vector. When a problem says "in place" on a string in Python or Java, convert to a list or char[] first; the interviewer knows this and wants to see that you do too. The full story — code units, grapheme clusters, why len("é") can be 1 or 2 — is on Strings in Depth.
Palindrome Check
def is_palindrome(s: str) -> bool:
left, right = 0, len(s) - 1
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
# --- self-check ---
assert is_palindrome("racecar")
assert is_palindrome("")
assert is_palindrome("a")
assert is_palindrome("abba")
assert not is_palindrome("abc")
print("is_palindrome OK")
public class Palindrome {
static boolean isPalindrome(String s) {
int left = 0, right = s.length() - 1;
while (left < right) {
if (s.charAt(left) != s.charAt(right)) return false;
left++;
right--;
}
return true;
}
public static void main(String[] args) {
if (!isPalindrome("racecar")) throw new AssertionError();
if (!isPalindrome("")) throw new AssertionError();
if (!isPalindrome("a")) throw new AssertionError();
if (!isPalindrome("abba")) throw new AssertionError();
if (isPalindrome("abc")) throw new AssertionError();
System.out.println("isPalindrome OK");
}
}
#include <cassert>
#include <iostream>
#include <string>
bool isPalindrome(const std::string& s) {
int left = 0, right = static_cast<int>(s.size()) - 1;
while (left < right) {
if (s[left] != s[right]) return false;
++left;
--right;
}
return true;
}
int main() {
assert(isPalindrome("racecar"));
assert(isPalindrome(""));
assert(isPalindrome("a"));
assert(isPalindrome("abba"));
assert(!isPalindrome("abc"));
std::cout << "isPalindrome OK\n";
}
import assert from "node:assert/strict";
function isPalindrome(s: string): boolean {
let left = 0;
let right = s.length - 1;
while (left < right) {
if (s[left] !== s[right]) return false;
left++;
right--;
}
return true;
}
// --- self-check ---
assert.equal(isPalindrome("racecar"), true);
assert.equal(isPalindrome(""), true);
assert.equal(isPalindrome("a"), true);
assert.equal(isPalindrome("abba"), true);
assert.equal(isPalindrome("abc"), false);
console.log("isPalindrome OK");
Anagram Detection
Two strings are anagrams if they have the same character frequencies.
from collections import Counter
def is_anagram(s: str, t: str) -> bool:
return Counter(s) == Counter(t)
# --- self-check ---
assert is_anagram("anagram", "nagaram")
assert not is_anagram("rat", "car")
assert is_anagram("", "")
assert not is_anagram("a", "ab")
print("is_anagram OK")
public class Anagram {
static boolean isAnagram(String s, String t) {
if (s.length() != t.length()) return false;
int[] count = new int[26]; // lowercase ASCII alphabet
for (int i = 0; i < s.length(); i++) {
count[s.charAt(i) - 'a']++;
count[t.charAt(i) - 'a']--;
}
for (int c : count) if (c != 0) return false;
return true;
}
public static void main(String[] args) {
if (!isAnagram("anagram", "nagaram")) throw new AssertionError();
if (isAnagram("rat", "car")) throw new AssertionError();
if (!isAnagram("", "")) throw new AssertionError();
if (isAnagram("a", "ab")) throw new AssertionError();
System.out.println("isAnagram OK");
}
}
#include <array>
#include <cassert>
#include <iostream>
#include <string>
bool isAnagram(const std::string& s, const std::string& t) {
if (s.size() != t.size()) return false;
std::array<int, 26> count{}; // lowercase ASCII alphabet
for (size_t i = 0; i < s.size(); ++i) {
count[s[i] - 'a']++;
count[t[i] - 'a']--;
}
for (int c : count) if (c != 0) return false;
return true;
}
int main() {
assert(isAnagram("anagram", "nagaram"));
assert(!isAnagram("rat", "car"));
assert(isAnagram("", ""));
assert(!isAnagram("a", "ab"));
std::cout << "isAnagram OK\n";
}
import assert from "node:assert/strict";
function isAnagram(s: string, t: string): boolean {
if (s.length !== t.length) return false;
const count = new Array(26).fill(0);
for (let i = 0; i < s.length; i++) {
count[s.charCodeAt(i) - 97]++;
count[t.charCodeAt(i) - 97]--;
}
return count.every(c => c === 0);
}
// --- self-check ---
assert.equal(isAnagram("anagram", "nagaram"), true);
assert.equal(isAnagram("rat", "car"), false);
assert.equal(isAnagram("", ""), true);
assert.equal(isAnagram("a", "ab"), false);
console.log("isAnagram OK");
The 26-slot counting array is the fastest hash table you will ever use: no hashing, no collisions, one cache line. Reach for it whenever the alphabet is small and known; fall back to a hash map (as the Python Counter does) when the alphabet is Unicode. The single-pass "increment for s, decrement for t, check all zero" trick avoids building two tables and comparing them.
String Hashing (Rabin-Karp)
For substring matching, rolling hash gives average time:
Python:
def rabin_karp(text: str, pattern: str) -> int:
"""Find first occurrence of pattern in text using rolling hash."""
if len(pattern) > len(text):
return -1
BASE = 31
MOD = 10**9 + 7
n, m = len(text), len(pattern)
# Compute hash of pattern and first window
pattern_hash = 0
window_hash = 0
power = 1
for i in range(m):
pattern_hash = (pattern_hash + ord(pattern[i]) * power) % MOD
window_hash = (window_hash + ord(text[i]) * power) % MOD
if i < m - 1:
power = (power * BASE) % MOD
if window_hash == pattern_hash and text[:m] == pattern:
return 0
for i in range(1, n - m + 1):
# Remove leftmost char, add rightmost char
window_hash = (window_hash - ord(text[i - 1])) % MOD
window_hash = (window_hash * pow(BASE, MOD - 2, MOD)) % MOD
window_hash = (window_hash + ord(text[i + m - 1]) * power) % MOD
if window_hash == pattern_hash and text[i:i + m] == pattern:
return i
return -1
This implementation weights the leftmost character by and the rightmost by , so sliding the window means subtracting the leftmost term, dividing the whole hash by BASE (multiplying by the modular inverse pow(BASE, MOD - 2, MOD), valid because MOD is prime) and adding the new character times . The more common textbook orientation weights the leftmost character by , so the slide is "subtract , multiply by BASE, add the new character" — no inverse needed. Both are correct; the second avoids a modular exponentiation per step (or you precompute the inverse once). The text[i:i+m] == pattern check after a hash match is what makes the algorithm exact rather than probabilistic: a hash match is a candidate, the comparison confirms it. Hash function quality, double hashing to defeat anti-hash tests, and the full Rabin–Karp / polynomial-hash family are on Hash Tables and String Algorithms.
Pattern Comparison Table
| Pattern | Best For | Time | Space | Key Insight |
|---|---|---|---|---|
| Two Pointers | Sorted arrays, pairs | Sorted order constrains movement | ||
| Sliding Window (fixed) | Fixed-size subarray stats | Add right, remove left | ||
| Sliding Window (variable) | Min/max subarray with constraint | Expand right, shrink left | ||
| Prefix Sum | Range sum queries | build, query | Precompute cumulative sums | |
| Hash Map counting | Frequency, anagrams | Trade space for time | ||
| Sorting first | Grouping, deduplication | Sorted order reveals structure | ||
| Kadane | Max-sum contiguous subarray | Best subarray ending here: extend or restart | ||
| Reversal rotation | Rotate / shift by k | , then un-reverse the halves | ||
| Boyer–Moore voting | Strict majority, streams | Pairing off unequal elements cannot kill a majority | ||
| Cyclic sort | Values in 1..n, missing/duplicates | Values are indices; the array is its own hash table | ||
| Floyd on an array | Duplicate without modifying | The array is its own linked list; duplicate = cycle entry |
Real-world uses
These patterns are not interview folklore; they are load-bearing in production systems.
- Ring buffers and fixed windows. Audio drivers, network card descriptor rings, Linux's
io_uringsubmission queue and the kernel log buffer are all circular arrays indexed modulo capacity — the fixed-window idea made persistent. Details in Queues, Deques & Circular Buffers and the Linux networking stack. - TCP flow control is literally a sliding window: the receiver advertises how many bytes it can accept, the sender keeps
[last_acked, last_acked + window)in flight and slides the left edge as ACKs arrive. See TCP/IP Deep Dive. - Rate limiters use sliding-window counters or logs to answer "how many requests in the last 60 seconds" in amortised; the design trade-offs are in Rate Limiting and the hands-on build in Build a Rate Limiter.
- Prefix sums in analytical databases. Columnar engines store running aggregates or per-block min/max/sum so that a range aggregate touches metadata instead of rows; ClickHouse internals and OLTP vs OLAP show the layouts. In graphics, the summed-area table (2D prefix sum, Crow 1984) lets the Viola–Jones face detector evaluate thousands of rectangle features per pixel in constant time each.
- Kadane in signal processing and bioinformatics. Maximum-scoring segment problems — finding the GC-rich stretch of a genome, the most profitable trading window, the burstiest interval in a log — are Kadane with a per-element score.
- Boyer–Moore and Misra–Gries in telemetry. Finding frequent flows in a router or hot keys in a cache from a single pass over a stream, with bounded memory, is the "heavy hitters" problem; the deterministic answer is Misra–Gries, the probabilistic one is Count-Min sketch (Probabilistic Data Structures).
- Two pointers inside merge sort, merging sorted runs in LSM-tree compaction and in the
mergestep of external sorting. Every time two sorted sequences are combined, two indices walk forward together; see Storage Engines and Sorting & Searching. - Dynamic-array growth is why
std::vector::push_back,ArrayList.addand Pythonappendare fast enough to be the default container everywhere, and why high-frequency systems pre-size them: a resize in the middle of a latency-critical path is a visible tail-latency spike. The allocator side of that story is in Memory Allocators. - Cyclic sort's "values as indices" is how counting sort and radix sort work (Sorting & Searching), and how a kernel maps a small dense ID space (file descriptors, PIDs) to a flat table with no hashing at all.
Common Edge Cases
Always Handle These
- Empty array/string: Return 0, empty string, or handle explicitly
- Single element: Often a valid answer by itself
- All same elements: Test deduplication logic
- Negative numbers: Two sum with negatives, prefix sums going negative
- Integer overflow: Sum of large numbers can overflow 32-bit integers
- Unicode strings: In production, "length" can be misleading with multi-byte characters
Pitfalls
The mistakes that actually show up in code review and in failed submissions:
- Sliding a window over negatives. The shrink step assumes removing an element reduces the aggregate. With negative numbers "sum ≥ target" is no longer monotone, so the window silently returns wrong answers (it compiles, it passes the sample). Switch to prefix sums + hash map, or to a monotonic deque of prefix sums for "shortest subarray with sum ≥ k" with negatives.
- Forgetting
>= leftin the longest-no-repeat window. Jumpingleftbackwards to a stale index re-admits a duplicate ("abba"→ wrong answer 3). Either keep the>= leftguard or use a counter map and shrink whilecount[c] > 1. - Off-by-one in prefix indices. With the convention,
sum(l, r) = prefix[r+1] - prefix[l]. Mixing it with a 0-based convention (prefix[r] - prefix[l-1]) producesprefix[-1], which in Python wraps to the last element and gives a plausible-looking wrong number instead of an error. - Looking up
sum - kafter insertingsum. Fork = 0this counts an empty subarray at every index. Lookup first, insert second. - Not reducing
k mod nbefore rotating, and rotating bykwhen the problem meansn - k(left vs right). - Trusting Boyer–Moore without the verification pass when the majority is not guaranteed.
- Overflow in prefix sums and Kadane. elements of magnitude sum to , past 32-bit. Use 64-bit accumulators in Java/C++; JavaScript
numberis exact only to , so very large sums needBigInt. - Three-sum duplicate handling. Skipping duplicates of
nums[i]before checkingi > 0crashes oni = 0; skipping inner duplicates without theleft < rightguard runs off the end. - Mutating the input when the problem forbids it (find-the-duplicate), or mutating a Python list while iterating over it with
for x in nums. - Treating "subsequence" as "subarray". Windows and prefix sums are for contiguous ranges. Subsequence problems (LIS, LCS) are DP and live in Dynamic Programming.
- String concatenation in a loop in Python/Java/JS — quadratic in the worst case; collect and join.
- Comparing floats for equality in two-pointer sum problems with decimal inputs; use integers (cents, not dollars) or a tolerance.
Variations
- Same-direction two pointers (read/write). Remove duplicates from a sorted array, move zeroes, remove element: the write pointer marks the boundary of the kept prefix, the read pointer scans. Invariant:
nums[0..write)is the answer so far. Two Pointers. - Three-way partition (Dutch national flag).
lo,mid,hipointers sort an array of three distinct values in one pass; the same idea is the partition step of quicksort (Sorting & Searching). - Two pointers on two arrays. Merge two sorted arrays, intersection of two sorted arrays, "is subsequence". Each pointer advances independently; total moves .
- Sliding window with a frequency counter. Longest substring with at most distinct, longest repeating character replacement, permutation in string. Sliding Window.
- "Exactly k" via "at most k". converts a non-monotone predicate into two monotone ones.
- Prefix XOR, prefix product, prefix modulo. The prefix idea works for any group operation; with modulo, store
sum mod kand look for equal residues ("subarray sum divisible by k"). Prefix Sums. - Difference array. The inverse of prefix sum: to add to every element in , do
diff[l] += v; diff[r+1] -= vand prefix-sum once at the end — per range update. - 2D prefix sums and grid rotation. Rectangle sums in , in-place matrix rotation as transpose + reverse rows. Matrices & Grids.
- Monotonic stack / deque. Sliding window maximum in , next greater element, largest rectangle in histogram. Monotonic Stack & Deque.
- Kadane relatives. Maximum product subarray (track min and max), maximum circular subarray, maximum sum of two non-overlapping subarrays (prefix-Kadane + suffix-Kadane).
- Misra–Gries. Boyer–Moore generalised to "more than times" with counters.
- Binary search over the answer. When "is there a window of length with property X" is monotone in , binary search and check each candidate with a fixed window — but often simpler than a variable window. Sorting & Searching.
Practice Problems
| Problem | Pattern | Difficulty |
|---|---|---|
| Two Sum | Hash map | Easy |
| Best Time to Buy and Sell Stock | Single pass / Kadane's | Easy |
| Contains Duplicate | Hash set | Easy |
| Product of Array Except Self | Prefix/suffix product | Medium |
| Maximum Subarray (Kadane's) | Dynamic programming / sliding | Medium |
| 3Sum | Sort + two pointers | Medium |
| Longest Substring Without Repeating | Sliding window + hash | Medium |
| Minimum Window Substring | Sliding window + hash | Hard |
| Trapping Rain Water | Two pointers or stack | Hard |
| Longest Palindromic Substring | Expand from center / DP | Medium |
Practice ladder
Fifteen problems, easiest first. Each description is in our own words; follow the link for the official statement. Do them in order — each one assumes the muscle built by the previous ones.
1. Two Sum (LeetCode 1) — Return the indices of two elements whose sum is a target; the array is not sorted. Teaches the complement-lookup hash map and why sorting would lose the indices.
Hint
For each element, ask "have I already seen target - x?" One pass, one dictionary from value to index.
2. Valid Palindrome (LeetCode 125) — Decide whether a sentence reads the same backwards once you drop non-alphanumerics and ignore case. Teaches opposite-end pointers that must skip characters.
Hint
Advance each pointer past non-alphanumeric characters before comparing. Do not build a cleaned copy — that is the -space solution the interviewer wants you to avoid.
3. Remove Duplicates from Sorted Array (LeetCode 26) — Compact a sorted array in place so each value appears once; return the new length. Teaches the same-direction read/write pointer pair.
Hint
write starts at 1. For each read, if nums[read] != nums[write-1], copy it to write and advance.
4. Best Time to Buy and Sell Stock (LeetCode 121) — One buy then one sell; maximise profit. Teaches Kadane in disguise.
Hint
Track the minimum price so far; the best sale today is price - min_so_far. Equivalently run Kadane on day-to-day differences.
Solution
def max_profit(prices: list[int]) -> int:
min_price, best = float("inf"), 0
for p in prices:
min_price = min(min_price, p)
best = max(best, p - min_price)
return best
assert max_profit([7, 1, 5, 3, 6, 4]) == 5
assert max_profit([7, 6, 4, 3, 1]) == 0
print("ok")
time, space. The running minimum is the "best start" for the current end — the same optimal-substructure argument as Kadane.
5. Two Sum II – Input Array Is Sorted (LeetCode 167) — Same as Two Sum but sorted and 1-indexed, and you must use extra space. Teaches the two-pointer proof above in its purest form.
Hint
Exactly the two_sum_sorted function on this page; add 1 to both indices.
6. Maximum Subarray (LeetCode 53) — Largest sum of a contiguous subarray with negatives present. Teaches Kadane directly.
Hint
best_end = max(x, best_end + x). Initialise with nums[0], not 0, because the subarray must be non-empty.
7. Container With Most Water (LeetCode 11) — Pick two vertical lines to hold the most water. Teaches the "retire the shorter wall" elimination argument.
Hint
Width only shrinks as pointers move inward, so the only way to gain area is a taller minimum. Moving the taller wall cannot help.
8. Rotate Array (LeetCode 189) — Rotate right by k in place. Teaches the three-reversal identity.
Hint
k %= n, then reverse all, reverse [0, k), reverse [k, n). Try the cyclic version as a follow-up and count the cycles.
9. Majority Element (LeetCode 169) — The value appearing more than times, in space. Teaches Boyer–Moore and why the proof needs a strict majority.
Hint
Candidate and counter. Then ask yourself what the algorithm returns on [1, 2, 3] and why that is fine here.
10. Minimum Size Subarray Sum (LeetCode 209) — Shortest contiguous run of positive integers with sum at least a target. Teaches the "shortest good window" shrink loop.
Hint
Expand right until the sum reaches the target, then shrink left while it still does, recording each length. The follow-up asks for — prefix sums + binary search.
Solution
def min_subarray_len(target: int, nums: list[int]) -> int:
left, total, best = 0, 0, float("inf")
for right, x in enumerate(nums):
total += x
while total >= target:
best = min(best, right - left + 1)
total -= nums[left]
left += 1
return 0 if best == float("inf") else best
assert min_subarray_len(7, [2, 3, 1, 2, 4, 3]) == 2
assert min_subarray_len(4, [1, 4, 4]) == 1
assert min_subarray_len(11, [1, 1, 1, 1, 1, 1, 1, 1]) == 0
print("ok")
time, space; each pointer moves at most times. Positivity is what makes "shrink while good" valid.
11. Longest Substring Without Repeating Characters (LeetCode 3) — Teaches the "last seen index" jump and the >= left guard.
Hint
Trace "abba" by hand before you submit.
12. Subarray Sum Equals K (LeetCode 560) — Count contiguous subarrays summing to k, negatives allowed. Teaches prefix sum + hash map and why a window fails here.
Hint
Map from prefix value to count, seeded with {0: 1}. Look up sum - k before inserting sum.
Solution
def subarray_sum(nums: list[int], k: int) -> int:
seen = {0: 1}
total = count = 0
for x in nums:
total += x
count += seen.get(total - k, 0)
seen[total] = seen.get(total, 0) + 1
return count
assert subarray_sum([1, 1, 1], 2) == 2
assert subarray_sum([1, 2, 3], 3) == 2
assert subarray_sum([1, -1, 0], 0) == 3
print("ok")
time, space. Each earlier prefix equal to total - k is the left boundary of a subarray with sum k ending here.
13. 3Sum (LeetCode 15) — All unique triples summing to zero. Teaches fix-one-then-two-pointers and the duplicate-skipping discipline.
Hint
Sort. Skip nums[i] == nums[i-1]. After each hit, skip equal values on both inner pointers before moving them.
14. Find the Duplicate Number (LeetCode 287) — numbers in , one repeated; space, array read-only. Teaches Floyd on an array.
Hint
slow = nums[slow], fast = nums[nums[fast]], then reset one pointer to nums[0]. Why is the duplicate the cycle entry? Because the entry has two incoming edges.
Solution
def find_duplicate(nums: list[int]) -> int:
slow = fast = nums[0]
while True:
slow, fast = nums[slow], nums[nums[fast]]
if slow == fast:
break
p = nums[0]
while p != slow:
p, slow = nums[p], nums[slow]
return p
assert find_duplicate([1, 3, 4, 2, 2]) == 2
assert find_duplicate([3, 1, 3, 4, 2]) == 3
print("ok")
time, space. The proof is the Floyd argument on the Linked Lists page with next replaced by array lookup.
15. Minimum Window Substring (LeetCode 76) — Smallest window of s containing every character of t with multiplicity. Teaches windows with counters and the have / required trick.
Hint
Maintain have = number of distinct characters whose window count has reached the required count. Only when have == required does the window qualify; then shrink.
Beyond the ladder. Trapping Rain Water (LeetCode 42) (two pointers with running maxima, or a monotonic stack), First Missing Positive (LeetCode 41) (cyclic sort with out-of-range values ignored), Maximum Sum Circular Subarray (LeetCode 918), Product of Array Except Self (LeetCode 238) (prefix and suffix products without division), and on CSES: Sum of Two Values (CSES 1640), Maximum Subarray Sum (CSES 1643), Subarray Sums II (CSES 1661), Static Range Sum Queries (CSES 1646) and Playlist (CSES 1141) — the last is longest-no-repeat on integers with up to , where a Python dict is fine but a set with per-step remove is cleaner.
Common mistakes & interview follow-ups
What interviewers ask after you have the solution, with the answers they want to hear:
- "What if the array is a stream and you cannot store it?" Kadane, Boyer–Moore and fixed windows are already streaming ( state). Prefix-sum counting still works online (the hash map grows with distinct prefix values). Opposite-end two pointers do not — they need random access to the right end; if the stream is sorted you can fall back to a hash set of seen values.
- "What if the array does not fit in memory?" Patterns with sequential access (windows, Kadane, prefix sums) work from disk in one pass; two pointers from both ends need two sequential cursors, which is fine on files but not on a network stream. For range queries on huge data, store block-level prefix sums (as columnar databases do) and scan only the partial blocks at the ends.
- "What if there are negative numbers?" The question is aimed at sliding window. Answer: the shrink step's monotonicity breaks; switch to prefix sums + hash map for exact sums, or to a monotonic deque over prefix sums for "shortest subarray with sum ≥ k" (LeetCode 862).
- "Can you do it without sorting?" For two-sum, yes — hash map. For three-sum, sorting is what enables duplicate-skipping and two pointers; without it you need a hash set per
iand a set of canonical triples, which is time but extra space and messier. - "Can you return the subarray, not just the sum?" Track the start index whenever Kadane restarts and record
(start, i)wheneverbestimproves — seemax_subarray_boundsabove. Same for windows: recordleftwhenbestupdates. - "What is the worst case of your hash-map solution?" Adversarial inputs can push a hash map to per operation. Java's
HashMaptreeifies long chains to ; Python randomises the string hash seed. If the keys are small integers, a counting array has no worst case at all. Hash Tables covers hash flooding. - "How does this change for Unicode?" Alphabet size is no longer 26 or 128, so
int[26]becomes a hash map; "length" counts code units, not characters, in Java/JS. Mention normalisation if the problem compares strings for equality. - "Why is your amortised append not good enough here?" Because a single append can still copy the whole array; in a latency-sensitive loop, pre-size or use a chunked structure.
- "Prove the two-pointer solution is correct." Give the elimination invariant: a solution remains inside
[left, right], and each move discards an index that cannot participate in any remaining solution.
Further Reading
- Hash Tables — the data structure powering most array/string patterns
- Sorting & Searching — binary search on sorted arrays
- Dynamic Programming — when sliding window isn't enough
- Trees: Tries — for prefix-based string problems
- Complexity Analysis — the amortised argument behind dynamic arrays, formally
- How Data Structures Live in Memory — cache lines, boxing, and why contiguous storage wins
- Linked Lists — the full proof of Floyd's algorithm used by find-the-duplicate
- Jon Bentley, Programming Pearls, 2nd ed., Column 2 (rotation) and Column 8 (maximum subarray) — the original expositions of the reversal trick and Kadane's algorithm
- Robert Boyer and J Strother Moore, "MJRTY — A Fast Majority Vote Algorithm", in Automated Reasoning: Essays in Honor of Woody Bledsoe, 1991 (written 1980)
- Donald Knuth, The Art of Computer Programming, Vol. 1 §1.3.3 (permutations and cycles) and Vol. 3 §5.2 (sorting by counting)
- CLRS, Introduction to Algorithms, 4th ed., §4.1 (maximum-subarray via divide and conquer, for comparison with Kadane) and Ch. 16 (amortised analysis)
- CPython
Objects/listobject.c(list_resize), OpenJDKjava/util/ArrayList.java(grow), Goruntime/slice.go(growslice) — the growth policies quoted above
Try It Yourself
Problem 1: Given array [3, 1, 4, 1, 5, 9], find two numbers that sum to 10.
Solution
Sort the array: [1, 1, 3, 4, 5, 9]. Use two pointers.
- Left=0 (1), Right=5 (9) → sum=10. Answer: [1, 9]
Problem 2: Find the length of the longest substring without repeating characters in "abcabcbb".
Solution
Use a sliding window with a hash map to track the last seen index of each character.
- Window expands right:
a,ab,abc(length 3) arepeats → shrink left to index 1:bca,bcab→brepeats → shrink- Maximum window length encountered: 3 (
"abc")
Problem 3: Given [2, 3, 1, 2, 4, 3] and target sum 7, find the minimal length subarray with sum >= 7.
Solution
Use a variable-size sliding window. Expand right to increase sum, shrink left when sum >= 7.
- Window
[2,3,1,2]sum=8 >= 7, length=4. Shrink:[3,1,2]sum=6 < 7. - Expand:
[3,1,2,4]sum=10, length=4. Shrink:[1,2,4]sum=7, length=3. Shrink:[2,4]sum=6 < 7. - Expand:
[2,4,3]sum=9, length=3. Shrink:[4,3]sum=7, length=2. Answer: 2 (subarray[4, 3])
Problem 4: Check if "racecar" is a palindrome using the two-pointer technique.
Solution
Use two pointers starting from both ends:
- Left=0 (
r), Right=6 (r) → match, move inward - Left=1 (
a), Right=5 (a) → match - Left=2 (
c), Right=4 (c) → match - Left=3 (
e), Right=3 → pointers crossed Answer: Yes, it is a palindrome.
Problem 5: Given nums = [1, 1, 1] and k = 2, count the number of subarrays that sum to k.
Solution
Use prefix sum with a hash map.
- prefix=0: map={0:1}
- prefix=1: check 1-2=-1 (not in map), map={0:1, 1:1}
- prefix=2: check 2-2=0 (in map, count=1), map={0:1, 1:1, 2:1}
- prefix=3: check 3-2=1 (in map, count=2), map={0:1, 1:1, 2:1, 3:1}
Answer: 2 (subarrays
[1,1]at indices 0-1 and 1-2)
Problem 6: Run Kadane's algorithm on [5, -9, 6, -2, 3] by hand. What is the answer, and at which index does the algorithm "restart"?
Solution
best_end: 5, max(−9, 5−9) = −4, max(6, −4+6) = 6 (restart at index 2), max(−2, 6−2) = 4, max(3, 4+3) = 7. best ends at 7 (subarray [6, -2, 3]). The restart happens at index 2 because carrying −4 into 6 is worse than starting fresh.
Problem 7: Rotate [1, 2, 3, 4, 5] right by k = 7 using the reversal method.
Solution
k mod n = 2. Reverse all: [5, 4, 3, 2, 1]. Reverse first 2: [4, 5, 3, 2, 1]. Reverse the rest: [4, 5, 1, 2, 3]. Answer: [4, 5, 1, 2, 3]. Forgetting the modulo would try to reverse the first 7 elements of a 5-element array.
Quick Quiz
1. What is the time complexity of the two-pointer technique on a sorted array?
- a)
- b)
- c)
- d)
Answer
c) — Each pointer moves at most steps total, so the combined work is linear.
2. When using a sliding window, what determines whether to use a fixed-size or variable-size window?
- a) Whether the array is sorted
- b) Whether the problem specifies a fixed window size or asks for min/max length satisfying a constraint
- c) Whether the elements are positive or negative
- d) The size of the input array
Answer
b) Whether the problem specifies a fixed window size or asks for min/max length satisfying a constraint — Fixed-size windows have a known . Variable-size windows expand and shrink to find the optimal length meeting a condition.
3. What does a prefix sum array allow you to do in time?
- a) Find the minimum element in a range
- b) Sort a subarray
- c) Compute the sum of any subarray
- d) Find duplicates in a range
Answer
c) Compute the sum of any subarray — After preprocessing, sum(l, r) = prefix[r+1] - prefix[l] is .
4. In the "Subarray Sum Equals K" problem, why do we use a hash map with prefix sums instead of a simple sliding window?
- a) Sliding window is slower
- b) Sliding window only works when all elements are positive; prefix sum + hash map handles negatives
- c) Hash maps use less memory
- d) It is just a style preference
Answer
b) Sliding window only works when all elements are positive; prefix sum + hash map handles negatives — The sliding window shrink step relies on the invariant that removing elements decreases the sum, which breaks with negative numbers.
5. What is the space complexity of the "Longest Substring Without Repeating Characters" solution?
- a)
- b)
- c)
- d) where is the alphabet size
Answer
d) — The hash map stores at most one entry per unique character. For a fixed alphabet (e.g., ASCII with 128 characters), this is effectively , but in the general case it is bounded by both the string length and alphabet size.
6. A dynamic array grows by a constant 16 slots each time it fills. What is the total cost of appends?
- a)
- b)
- c)
- d)
Answer
c) — The copies at sizes form an arithmetic series summing to . Only a geometric growth factor makes the copies a geometric series bounded by a constant times .
7. Boyer–Moore returns candidate 3 on [1, 2, 3]. Is the algorithm wrong?
- a) Yes, it should return "no majority"
- b) No — the guarantee only holds when a strict majority exists; a verification pass is required otherwise
- c) Yes, it should return 1
- d) No, 3 is the majority
Answer
b) — The pairing argument proves that if a value occurs more than times it survives; it says nothing about the output when no such value exists. Count the candidate in a second pass when the majority is not guaranteed.