On this page

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 pageWhat it adds beyond this overview
Module 1 indexThe study order, time budget per lesson and how the pieces fit
Two PointersSame-direction (read/write) pointers, Dutch national flag partition, trapping rain water, 4Sum and the general "k-sum" reduction
Sliding WindowWindows 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 Arrays2D prefix sums, difference arrays for range updates, prefix XOR, prefix sums modulo k, and prefix-sum + hash-map families
Matrices & 2D GridsRow-major layout, in-place rotation and transposition, spiral order, set-matrix-zeroes, 2D search
Strings in DepthUnicode and encodings, immutability costs, string building, parsing state machines, palindromes beyond two pointers
StacksParentheses matching, expression evaluation, min-stack, stack-based iterators and call-stack simulation
Queues, Deques & Circular BuffersRing buffers, queue via two stacks, deque internals (Python's block deque), BFS frontiers
Monotonic Stack & DequeNext greater element, histogram areas, sliding window maximum in
IntervalsMerge, insert, sweep line, meeting rooms, the interval scheduling exchange argument
Linked ListsPointer manipulation, Floyd's proof, reversal patterns, k-group reversal
Hash TablesHash function design, collision strategies, how dict/HashMap/unordered_map actually work
Probabilistic Data StructuresBloom filters, Count-Min sketch, HyperLogLog — approximate answers in sublinear memory
Capstone: LRU CacheBuild 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 ofWhy that pattern fits
"sorted array", "pair that sums to", "remove duplicates in place", "palindrome"Two pointersSortedness (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 windowThe 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"KadaneOptimal substructure on "best subarray ending here"
"rotate", "shift by k", "cyclic shift"Reversal / cyclic replacementRotation is a permutation that factors into reversals or cycles
"appears more than n/2 times", "majority", "stream, O(1) memory"Boyer–Moore votingPairing 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 arrayValues 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 mapA 26- or 128-slot array is the fastest hash table there is
"next greater element", "largest rectangle", "sliding window maximum"Monotonic stack / dequeElements that can never be an answer again can be discarded
"merge overlapping", "meeting rooms", "intervals"Sort + sweepSorting by start makes overlap a local question
"matrix", "grid", "rotate image", "spiral"Grid traversalIndex 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 list is an array of pointers to heap objects; an int element is a 28-byte object elsewhere in memory. Iterating still enjoys locality for the pointer array but not for the values. Java int[] and C++ std::vector<int> store the values inline; Java ArrayList<Integer> and List<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 str is an array of code points stored as 1, 2 or 4 bytes per character depending on the widest character present (PEP 393); C++ std::string is 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:

ImplementationGrowth ruleEffective factorSource
CPython listnew = size + (size >> 3) + 6, rounded down to a multiple of 4≈ 1.125× (plus a constant)Objects/listobject.c, list_resize
Java ArrayListold + (old >> 1)1.5×java.util.ArrayList#grow via ArraysSupport.newLength
C++ std::vector (libstdc++, libc++)2 × old2×bits/stl_vector.h _M_check_len; libc++ __recommend
C++ std::vector (MSVC STL)old + old / 21.5×<vector> _Calculate_growth
Go slices2× until 256 elements, then smoothly down toward 1.25×2× → 1.25×runtime/slice.go growslice (Go 1.18+)
Rust Vecmax(2 × old, 4) for small element types2×alloc/src/raw_vec.rs grow_amortized
V8 JSArray backing storeold + old / 2 + 161.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:

  1. 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.
  2. 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).

stepleftrightnums[left]nums[right]sumaction
10511516sum > target, right--
20411112sum < target, left++
31421113sum < target, left++
42441115found, 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):

leftrightwidthmin heightareamove
08818left++
187749right--
176318right--
165840right--
154416right--
143515right--
13224right--
12166right--

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.

rightcharlast indexleftwindowmax
0a-0a1
1b-0ab2
2c-0abc3
3a01bca3
4b12cab3
5c23abc3
6b45cb3
7b67b3

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):

rightaddwindow after shrinkingsum aftershrink steps (each records a length)best
02[2]2--
13[2, 3]5--
21[2, 3, 1]6--
32[3, 1, 2]6len 4 ok, drop 24
44[2, 4]6len 4 ok, drop 3; len 3 ok, drop 13
53[3]3len 3 ok, drop 2; len 2 ok, drop 42

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 .

inums[i]prefix[i+1] = prefix[i] + nums[i]
030 + 3 = 3
1-13 + -1 = 2
242 + 4 = 6
316 + 1 = 7
457 + 5 = 12
5-912 + -9 = 3

prefix = [0, 3, 2, 6, 7, 12, 3]. Queries:

query (l, r)prefix[r+1]prefix[l]sumcheck against the raw slice
(1, 3)734−1 + 4 + 1 = 4
(0, 5)303whole array = 3
(2, 2)624single element 4
(3, 5)36−31 + 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 .

inumrunning sumneed = sum − kcount of need in maptotalmap after
011−200{0: 1, 1: 1}
123011{0: 1, 1: 1, 3: 1}
236312{0: 1, 1: 1, 3: 1, 6: 1}
3−24113{0: 1, 1: 1, 3: 1, 6: 1, 4: 1}
426314{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

  1. Brute force, : for every pair , sum the slice.
  2. Prefix sums, : turns each slice sum into ; still pairs.
  3. Prefix sums, one pass, : for fixed the best is the one that minimises over . Keep a running minimum prefix and the answer is .
  4. 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.

RungTimeSpaceIdea
All slicesRe-sum every slice
Prefix + all pairs slice sums
Prefix + running minBest 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]):

inums[i]best_ending_here = max(nums[i], prev + nums[i])best_so_far
0−2−2 (start)−2
11max(1, −2+1) = 11
2−3max(−3, 1−3) = −21
34max(4, −2+4) = 44
4−1max(−1, 4−1) = 34
52max(2, 3+2) = 55
61max(1, 5+1) = 66
7−5max(−5, 6−5) = 16
84max(4, 1+4) = 56

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 :

stepoperationarray
0start, k = 3[1, 2, 3, 4, 5, 6, 7]
1reverse whole[7, 6, 5, 4, 3, 2, 1]
2reverse first k = 3[5, 6, 7, 4, 3, 2, 1]
3reverse 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 startvisits (index: value placed)
02: 1, 4: 3, 0: 5
13: 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.

ixcandidate beforecount beforeactioncandidate aftercount after
02-0count 0 → adopt x21
1221x == candidate, count++22
2122x != candidate, count--21
3121x != candidate, count--20
4120count 0 → adopt x11
5211x != candidate, count--10
6210count 0 → adopt x21

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.

stepia[i]correct index a[i]−1actionarray
1032swap a[0] and a[2][5, 1, 3, 4, 2]
2054swap a[0] and a[4][2, 1, 3, 4, 5]
3021swap a[0] and a[1][1, 2, 3, 4, 5]
4010in place, i++[1, 2, 3, 4, 5]
5121in place, i++[1, 2, 3, 4, 5]
6232in place, i++[1, 2, 3, 4, 5]
7343in place, i++[1, 2, 3, 4, 5]
8454in 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):

stepslowfastnote
011start at nums[0]
132
222meet

Phase 2, one pointer back to the start, both at speed one:

stepp1 (from nums[0])p2 (from meeting)note
012
134
222meet → 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:

OperationTypeScriptPython
Iterate charsfor (const c of s)for c in s:
Check if letterc >= 'a' && c <= 'z'c.isalpha()
Char → numbers.charCodeAt(i) - 97ord(c) - ord('a')
Number → charString.fromCharCode(n + 97)chr(n + ord('a'))
Reverses.split('').reverse().join('')s[::-1]

The same operations in the other two course languages:

OperationJavaC++
Iterate charsfor (char c : s.toCharArray())for (char c : s)
Check if letterCharacter.isLetter(c)std::isalpha(static_cast<unsigned char>(c))
Char → numbers.charAt(i) - 'a's[i] - 'a'
Number → char(char) ('a' + n)static_cast<char>('a' + n)
Reversenew StringBuilder(s).reverse().toString()std::reverse(s.begin(), s.end())
Build a string in a loopStringBuilder 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

PatternBest ForTimeSpaceKey Insight
Two PointersSorted arrays, pairsSorted order constrains movement
Sliding Window (fixed)Fixed-size subarray statsAdd right, remove left
Sliding Window (variable)Min/max subarray with constraintExpand right, shrink left
Prefix SumRange sum queries build, queryPrecompute cumulative sums
Hash Map countingFrequency, anagramsTrade space for time
Sorting firstGrouping, deduplicationSorted order reveals structure
KadaneMax-sum contiguous subarrayBest subarray ending here: extend or restart
Reversal rotationRotate / shift by k, then un-reverse the halves
Boyer–Moore votingStrict majority, streamsPairing off unequal elements cannot kill a majority
Cyclic sortValues in 1..n, missing/duplicatesValues are indices; the array is its own hash table
Floyd on an arrayDuplicate without modifyingThe 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_uring submission 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 merge step 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.add and Python append are 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:

  1. 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.
  2. Forgetting >= left in the longest-no-repeat window. Jumping left backwards to a stale index re-admits a duplicate ("abba" → wrong answer 3). Either keep the >= left guard or use a counter map and shrink while count[c] > 1.
  3. 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]) produces prefix[-1], which in Python wraps to the last element and gives a plausible-looking wrong number instead of an error.
  4. Looking up sum - k after inserting sum. For k = 0 this counts an empty subarray at every index. Lookup first, insert second.
  5. Not reducing k mod n before rotating, and rotating by k when the problem means n - k (left vs right).
  6. Trusting Boyer–Moore without the verification pass when the majority is not guaranteed.
  7. Overflow in prefix sums and Kadane. elements of magnitude sum to , past 32-bit. Use 64-bit accumulators in Java/C++; JavaScript number is exact only to , so very large sums need BigInt.
  8. Three-sum duplicate handling. Skipping duplicates of nums[i] before checking i > 0 crashes on i = 0; skipping inner duplicates without the left < right guard runs off the end.
  9. 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.
  10. Treating "subsequence" as "subarray". Windows and prefix sums are for contiguous ranges. Subsequence problems (LIS, LCS) are DP and live in Dynamic Programming.
  11. String concatenation in a loop in Python/Java/JS — quadratic in the worst case; collect and join.
  12. 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, hi pointers 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 k and 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] -= v and 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

ProblemPatternDifficulty
Two SumHash mapEasy
Best Time to Buy and Sell StockSingle pass / Kadane'sEasy
Contains DuplicateHash setEasy
Product of Array Except SelfPrefix/suffix productMedium
Maximum Subarray (Kadane's)Dynamic programming / slidingMedium
3SumSort + two pointersMedium
Longest Substring Without RepeatingSliding window + hashMedium
Minimum Window SubstringSliding window + hashHard
Trapping Rain WaterTwo pointers or stackHard
Longest Palindromic SubstringExpand from center / DPMedium

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 i and 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) whenever best improves — see max_subarray_bounds above. Same for windows: record left when best updates.
  • "What is the worst case of your hash-map solution?" Adversarial inputs can push a hash map to per operation. Java's HashMap treeifies 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), OpenJDK java/util/ArrayList.java (grow), Go runtime/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)
  • a repeats → shrink left to index 1: bca, bcab → b repeats → 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.