4 — Arrays and sliding windows

An array is a block of equally sized slots laid out one after another in memory. Almost every technique in this chapter exploits one of two consequences of that layout: any slot can be reached in constant time from its index, and neighboring slots are cheap to visit in order. The techniques themselves (two pointers, sliding windows, prefix sums and the rest) are ways of avoiding the nested loop that a direct reading of most array problems suggests, turning $O(n^2)$ or $O(nk)$ scans into a single $O(n)$ pass.

Timings in this chapter were measured with Python 3.14 on one Mac. Exact numbers will differ on other machines; the ratios and growth patterns are what matter.

How arrays sit in memory

A C array of n 8-byte integers is 8n contiguous bytes. Element i lives at address base + 8 * i, so indexing is one multiply and one add, whatever n is. That is the origin of “array access is O(1)”.

index:     0        1        2        3        4
         +--------+--------+--------+--------+--------+
address: | 1000   | 1008   | 1016   | 1024   | 1032   |
value:   |   17   |   -4   |   99   |    0   |   23   |
         +--------+--------+--------+--------+--------+
element i is at 1000 + 8*i

A Python list is one level removed. It is a contiguous array of pointers to objects, and each object (an int, a str, anything) lives wherever the allocator put it. Indexing a list is still O(1), since it finds the pointer by address arithmetic, but reading the value means following that pointer somewhere else in memory. The array module and bytes/bytearray store raw values contiguously, as C does.

Python list                      the int objects, wherever they landed
+------+------+------+           +-----------+    +-----------+
| ptr0 | ptr1 | ptr2 | --------> | int 17    |    | int 99    |
+------+------+------+     \     +-----------+    +-----------+
                            \--> +-----------+
                                 | int -4    |
                                 +-----------+

Why contiguity matters

Big-O counts operations, not memory traffic, and that hides the largest constant factor in modern hardware. A CPU does not fetch single bytes from main memory; it fetches 64-byte cache lines, and its prefetcher notices sequential patterns and fetches the next lines before they are asked for. Reading an array in order therefore costs roughly one main-memory trip per eight 8-byte elements, often less, while reading it in random order can cost one trip per element once the array no longer fits in cache.

Python’s interpreter overhead hides much of this, but not all of it. The first measurement walks an array.array of 64-bit integers twice: once with indices 0, 1, 2, ... and once with the same indices shuffled. The Python work per element is identical; only the memory access order changes.

At 10,000 elements (80 KB) everything fits in cache and the order is irrelevant. At 10 million (80 MB) the random walk is four times slower for exactly the same instructions.

The second measurement shows the same effect inside a plain list. A list of a million freshly created int objects has its pointers in allocation order, so the objects themselves sit roughly in address order. Shuffling the list leaves the same objects in place but scrambles the order in which sum visits them:

Same list length, same values, same O(n) algorithm, up to six times slower. This is why linked structures lose to arrays in practice even when their Big-O is equal (see Linked lists), and why databases such as PostgreSQL arrange data in pages and prefer sequential scans when a query touches a large fraction of a table.

Traversal order in a 2D structure is the same issue. Summing a 2000 × 2000 list of lists row by row took 60 ms; column by column took 182 ms. Part of that gap is the extra m[r] lookup in the inner loop of the column version, but the rest is locality: row-major order walks each row’s pointer array in sequence.

Dynamic arrays

A fixed array cannot grow. A dynamic array (Python list, C++ std::vector, Java ArrayList) keeps a larger buffer than it needs and tracks two numbers, the length and the capacity. Appending writes into the spare slot. When the buffer is full, it allocates a bigger one, copies everything across, and frees the old one.

If the capacity grows by a constant factor each time, the total copying over n appends is a geometric series bounded by a constant times n, so each append is O(1) amortized even though an individual append that triggers a resize is O(n). Growing by a constant amount instead gives O(n) amortized per append. The argument is worked through in Complexity.

CPython grows lists by about 12.5% plus a small constant (the new capacity is roughly n + n/8 + 6, rounded down to a multiple of 4). Watching sys.getsizeof while appending shows the capacities it picks:

import sys

a, last, caps = [], sys.getsizeof([]), []
for i in range(100):
    a.append(i)
    size = sys.getsizeof(a)
    if size != last:
        caps.append((len(a), (size - 56) // 8))   # (length that triggered it, new capacity)
        last = size
print(caps)

[(1, 4), (5, 8), (9, 16), (17, 24), (25, 32), (33, 40), (41, 52), (53, 64), (65, 76), (77, 92), (93, 108)]

A small growth factor wastes less memory but resizes more often; it is still a constant factor, so appends remain amortized O(1).

The costs of the common list operations follow directly from the layout:

Building a list of 100,000 elements by append took 6.2 ns per operation; building it with insert(0, x) took 15,423 ns per operation on average, 2,500 times slower, because each insert shifts everything already there. Where both ends are needed, collections.deque gives O(1) at each end (see Stacks and queues).

Two pointers

Two-pointer techniques keep two indices into the array and move them according to a rule that guarantees no candidate answer is skipped. Each pointer only moves forward (or only backward), so the total number of moves is at most 2n: O(n) time, O(1) extra space. The art lies in the invariant that justifies discarding candidates.

Opposite direction

Start one pointer at each end and walk them toward each other. The classic example is Two Sum II on a sorted array: find two entries summing to target.

def two_sum_sorted(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        s = nums[lo] + nums[hi]
        if s == target:
            return lo, hi
        if s < target:
            lo += 1
        else:
            hi -= 1
    return None

The invariant: no valid pair uses an index outside [lo, hi]. If nums[lo] + nums[hi] < target, then nums[lo] paired with anything in the range is at most nums[lo] + nums[hi], which is too small, so lo can be dropped. The symmetric argument drops hi. Each step discards one index, so the loop runs at most n − 1 times.

nums = [1, 3, 4, 6, 9, 11], target = 10

lo=0 hi=5   1 + 11 = 12  > 10  -> hi--
lo=0 hi=4   1 +  9 = 10  == 10 -> answer (0, 4)

The precondition is sorted input. On unsorted input the same problem is solved in O(n) with a hash map (see Hashing), or in O(n log n) by sorting first.

Container With Most Water uses the same shape. Given wall heights, choose two walls maximizing (j − i) * min(h[i], h[j]). Moving the taller wall inward can never help (width shrinks and the height is still capped by the shorter wall), so the shorter wall is the one to discard.

def max_area(heights):
    lo, hi = 0, len(heights) - 1
    best = 0
    while lo < hi:
        best = max(best, (hi - lo) * min(heights[lo], heights[hi]))
        if heights[lo] < heights[hi]:
            lo += 1
        else:
            hi -= 1
    return best

Trapping Rain Water is the harder relative. Water above bar i is min(max_left(i), max_right(i)) − h[i]. Precomputing both maxima arrays gives O(n) time and O(n) space. Two pointers get it in O(1) space: whichever side currently has the lower bar is bounded by its own side’s running maximum, because the other side is already known to contain something at least as tall.

def trap(heights):
    lo, hi = 0, len(heights) - 1
    left_max = right_max = water = 0
    while lo < hi:
        if heights[lo] < heights[hi]:
            left_max = max(left_max, heights[lo])
            water += left_max - heights[lo]
            lo += 1
        else:
            right_max = max(right_max, heights[hi])
            water += right_max - heights[hi]
            hi -= 1
    return water

For [0,1,0,2,1,0,1,3,2,1,2,1] it returns 6. Reversing an array in place, checking a palindrome, and the reversal-based rotation later in this chapter are all opposite-direction two-pointer loops too.

Same direction (read and write pointers)

Both pointers start at the left. A fast “read” pointer scans every element; a slow “write” pointer marks where the next kept element goes. Everything before write is the finished output. This compacts an array in place in one pass.

Remove Duplicates from Sorted Array:

def remove_duplicates(nums):
    if not nums:
        return 0
    write = 1
    for read in range(1, len(nums)):
        if nums[read] != nums[write - 1]:
            nums[write] = nums[read]
            write += 1
    return write

nums = [1, 1, 2, 2, 2, 3]
read=1  nums[1]=1 == nums[0]=1        skip
read=2  nums[2]=2 != 1  write nums[1]=2, write=2
read=3  2 == nums[1]                  skip
read=4  2 == nums[1]                  skip
read=5  3 != 2          write nums[2]=3, write=3
result: first 3 slots [1, 2, 3]

Move Zeroes is the same loop with a swap instead of a copy, which keeps the non-zero elements in their original order (the operation is stable) and pushes zeros to the end:

def move_zeroes(nums):
    write = 0
    for read in range(len(nums)):
        if nums[read] != 0:
            nums[write], nums[read] = nums[read], nums[write]
            write += 1

The fast-and-slow pointer pattern on linked lists (finding the middle, detecting cycles) is a different use of “same direction” in which the pointers move at different speeds; it is covered in Linked lists. On arrays, the same idea finds a duplicate in an array of n + 1 values from 1..n by treating i -> nums[i] as a linked list with a cycle.

Three pointers and 3Sum

3Sum asks for all unique triples summing to zero. The brute force is $O(n^3)$. Sorting and then fixing the first element reduces the rest to Two Sum II on the suffix, giving $O(n^2)$ total:

def three_sum(nums):
    nums = sorted(nums)
    n = len(nums)
    out = []
    for i in range(n - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue                      # same first element, same triples
        if nums[i] > 0:
            break                         # three positives cannot sum to 0
        lo, hi = i + 1, n - 1
        while lo < hi:
            s = nums[i] + nums[lo] + nums[hi]
            if s < 0:
                lo += 1
            elif s > 0:
                hi -= 1
            else:
                out.append((nums[i], nums[lo], nums[hi]))
                lo += 1
                hi -= 1
                while lo < hi and nums[lo] == nums[lo - 1]:
                    lo += 1               # skip duplicate second elements
    return out

>>> three_sum([-1, 0, 1, 2, -1, -4])
[(-1, -1, 2), (-1, 0, 1)]

The duplicate handling is where most implementations go wrong. Skipping equal values of nums[i] and of nums[lo] after a match is enough; skipping equal nums[hi] as well is harmless but unnecessary, since once nums[lo] changes the matching nums[hi] must change too. 4Sum adds one more fixed index for $O(n^3)$; in general k-Sum by this method is $O(n^{k-1})$.

Merging two sorted arrays is the other common three-pointer loop: one read pointer per input plus one write pointer. Filling from the back (Merge Sorted Array, where the first array has spare space at its end) avoids overwriting unread elements.

Sliding window

A sliding window is a contiguous range [left, right] that moves across the array, with some summary of its contents (a sum, a count map, a set) maintained incrementally. When an element enters, the summary is updated; when one leaves, it is reverted. Each element enters once and leaves at most once, so the whole scan is O(n) even though it considers O(n) windows that would each cost O(k) to evaluate from scratch.

The precondition that is easy to miss: the window technique needs the property being tracked to be monotone in window size. If a window is invalid, every larger window containing it must also be invalid (so shrinking is the only fix), or if valid, every smaller one inside must be valid. “Sum of positive numbers at most S” qualifies. “Sum equals k” with negative numbers allowed does not, which is why that problem needs prefix sums instead.

Fixed size: Maximum Average Subarray

Find the contiguous subarray of length k with the largest average. Recomputing each window’s sum is $O(nk)$. Sliding adds the entering element and subtracts the leaving one:

def max_average(nums, k):
    window = sum(nums[:k])
    best = window
    for i in range(k, len(nums)):
        window += nums[i] - nums[i - k]
        best = max(best, window)
    return best / k

nums = [1, 12, -5, -6, 50, 3], k = 4
[1 12 -5 -6] 50  3     sum = 2
 1 [12 -5 -6 50]  3    sum = 2 - 1 + 50 = 51
 1 12 [-5 -6 50  3]    sum = 51 - 12 + 3 = 42
best = 51, average 12.75

On 100,000 random integers:

The window version is flat in k; the naive version grows linearly with it (its constant is small because sum over a slice runs in C).

With floating-point data, a running sum accumulates rounding error over millions of steps. Recomputing the sum from scratch every few thousand steps, or using math.fsum on the final candidates, keeps it honest.

Variable size: Longest Substring Without Repeating Characters

Here the window grows on the right and, when it becomes invalid, shrinks from the left until it is valid again. The answer is the largest valid window seen.

A useful refinement stores the last index of each character, so the left edge can jump directly past the previous occurrence instead of stepping one at a time:

def longest_unique(s):
    last = {}
    left = best = 0
    for right, ch in enumerate(s):
        if ch in last and last[ch] >= left:
            left = last[ch] + 1
        last[ch] = right
        best = max(best, right - left + 1)
    return best

s = "abcabcbb"
right=0 'a'  window "a"        best 1
right=1 'b'  window "ab"       best 2
right=2 'c'  window "abc"      best 3
right=3 'a'  last a=0 -> left=1   window "bca"  best 3
right=4 'b'  last b=1 -> left=2   window "cab"
right=5 'c'  last c=2 -> left=3   window "abc"
right=6 'b'  last b=4 -> left=5   window "cb"
right=7 'b'  last b=6 -> left=7   window "b"
answer 3

The check last[ch] >= left matters: an old occurrence that is already outside the window must not move left backward. O(n) time; space is O(min(n, alphabet size)).

Shrinkable window: Minimum Window Substring

Given s and t, find the shortest substring of s containing every character of t with multiplicity. This is the canonical “shrink while valid” window: grow right until the window covers t, then shrink left as far as possible while it still covers t, record the result, and continue.

The efficient trick is to keep a single integer missing, the number of characters of t not yet covered, rather than comparing two count maps on every step.

from collections import Counter

def min_window(s, t):
    need = Counter(t)          # need[c] > 0: still missing; < 0: surplus in window
    missing = len(t)
    left = 0
    best = (0, float("inf"))
    for right, ch in enumerate(s):
        if need[ch] > 0:
            missing -= 1
        need[ch] -= 1
        if missing == 0:
            while need[s[left]] < 0:       # drop surplus characters from the left
                need[s[left]] += 1
                left += 1
            if right - left < best[1] - best[0]:
                best = (left, right)
            need[s[left]] += 1             # give up one required char, keep sliding
            missing += 1
            left += 1
    return "" if best[1] == float("inf") else s[best[0]:best[1] + 1]

For s = "ADOBECODEBANC", t = "ABC" it returns "BANC". Every index enters once and leaves at most once: O(|s| + |t|) time, O(alphabet) space. The usual bug is treating t as a set; t = "AA" needs two As in the window.

At most K distinct: Longest Subarray with K Distinct Elements and Fruit Into Baskets

Find the longest subarray with at most k distinct values. The window keeps a count map; when it holds more than k keys, shrink from the left, deleting keys whose count reaches zero.

from collections import defaultdict

def longest_k_distinct(nums, k):
    count = defaultdict(int)
    left = best = 0
    for right, x in enumerate(nums):
        count[x] += 1
        while len(count) > k:
            y = nums[left]
            count[y] -= 1
            if count[y] == 0:
                del count[y]
            left += 1
        best = max(best, right - left + 1)
    return best

Fruit Into Baskets (each tree yields one fruit type; two baskets, each holding one type; collect the longest contiguous run) is exactly this with k = 2:

def total_fruit(fruits):
    return longest_k_distinct(fruits, 2)

total_fruit([3,3,3,1,2,1,1,2,3,3,4]) is 5 (the run 1,2,1,1,2).

A related counting trick: the number of subarrays with exactly k distinct values is at_most(k) − at_most(k − 1), where at_most(k) sums right − left + 1 over all positions of right. “Exactly” is not monotone in window size, but “at most” is.

Longest Repeating Character Replacement

Given a string and a budget k, replace at most k characters to make the longest possible run of one letter. A window is valid when length − (count of its most frequent letter) <= k.

def character_replacement(s, k):
    count = defaultdict(int)
    left = max_freq = 0
    for right, ch in enumerate(s):
        count[ch] += 1
        max_freq = max(max_freq, count[ch])
        if right - left + 1 - max_freq > k:
            count[s[left]] -= 1
            left += 1
    return len(s) - left

This version has two features that look like bugs and are not.

1. max_freq is never decreased when the window shrinks, so it can be stale (too high). The answer only improves when a window of a new, larger size is valid, which requires some letter to reach a frequency above the old max_freq. A stale value can make an invalid window look valid only at a size already achieved, so it never inflates the answer.
2. The if shrinks by at most one, so the window never gets smaller: it either grows by one or slides by one. Its final size is the largest valid size encountered, which is why the answer is len(s) − left.

character_replacement("AABABBA", 1) is 4. If the more transparent version is preferred, recompute max(count.values()) (26 letters, so O(26) per step) and shrink with a while.

Choosing a window shape

Prefix and suffix sums

A prefix sum array P has P[0] = 0 and P[i] = nums[0] + ... + nums[i − 1]. The sum of any range nums[l..r] (inclusive) is then P[r + 1] − P[l]: O(n) preprocessing, O(1) per query.

def prefix_sums(nums):
    p = [0]
    for x in nums:
        p.append(p[-1] + x)
    return p

itertools.accumulate(nums, initial=0) produces the same list. The leading zero removes an entire class of off-by-one special cases for ranges starting at index 0.

nums:  [ 3,  1,  4,  1,  5]
P:   [0, 3,  4,  8,  9, 14]
sum(nums[1..3]) = P[4] - P[1] = 9 - 3 = 6   (1 + 4 + 1)

Prefix sums work for any operation with an inverse (addition, XOR, multiplication when no zeros are involved). Range minimum has no inverse, so it needs a sparse table or segment tree (see Tries and range structures). If the array is also being updated, a Fenwick tree gives O(log n) for both updates and queries.

Suffix products: Product of Array Except Self

Return, for every i, the product of all elements except nums[i], without division. The answer at i is (product of everything to the left) times (product of everything to the right): a prefix product and a suffix product. Writing the prefix pass into the output and folding in the suffix on a second, backward pass uses O(1) extra space:

def product_except_self(nums):
    n = len(nums)
    out = [1] * n
    left = 1
    for i in range(n):
        out[i] = left
        left *= nums[i]
    right = 1
    for i in range(n - 1, -1, -1):
        out[i] *= right
        right *= nums[i]
    return out

product_except_self([1, 2, 3, 4]) is [24, 12, 8, 6]. The division approach fails on zeros, which is why the problem forbids it.

Subarray Sum Equals K

Count subarrays summing to k, with negative numbers allowed. A sliding window fails because adding an element can make the sum go either way. Instead: a subarray nums[l..r] sums to k exactly when P[r + 1] − P[l] = k, that is, when some earlier prefix equals P[r + 1] − k. Keep a hash map from prefix value to how many times it has occurred:

def subarray_sum_equals_k(nums, k):
    seen = defaultdict(int)
    seen[0] = 1                    # the empty prefix
    running = count = 0
    for x in nums:
        running += x
        count += seen[running - k]
        seen[running] += 1
    return count

nums = [1, 2, 3, -3, 3], k = 3
x    running  look up running-3   seen before    count
1    1        -2                  {0:1}          0
2    3         0 -> 1             {0:1,1:1}      1   [1,2]
3    6         3 -> 1             {..,3:1}       2   [3]
-3   3         0 -> 1             {..,6:1}       3   [1,2,3,-3]
3    6         3 -> 2             {..,3:2}       5   [3,-3,3], [3]

O(n) time and O(n) space. The seen[0] = 1 seed accounts for subarrays that start at index 0; leaving it out is the standard bug. Variations: longest subarray with sum k (store the first index of each prefix instead of a count), subarray sum divisible by k (key on running % k), contiguous array with equal 0s and 1s (map 0 to −1, look for sum 0).

2D prefix sums

For a matrix, let P[r][c] be the sum of the rectangle from (0, 0) to (r − 1, c − 1). Inclusion-exclusion builds it and answers any rectangle query in O(1):

P[r+1][c+1] = grid[r][c] + P[r][c+1] + P[r+1][c] - P[r][c]

sum(r1..r2, c1..c2) = P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]

     c1      c2
   +---+-------+
   | D |   B   |
r1 +---+-------+
   |   |       |
   | C |   A   |      A = total - (B+D) - (C+D) + D
r2 +---+-------+

class Prefix2D:
    def __init__(self, grid):
        rows, cols = len(grid), len(grid[0])
        P = [[0] * (cols + 1) for _ in range(rows + 1)]
        for r in range(rows):
            for c in range(cols):
                P[r + 1][c + 1] = grid[r][c] + P[r][c + 1] + P[r + 1][c] - P[r][c]
        self.P = P

    def sum(self, r1, c1, r2, c2):
        P = self.P
        return P[r2 + 1][c2 + 1] - P[r1][c2 + 1] - P[r2 + 1][c1] + P[r1][c1]

Preprocessing is O(rows × cols); each query is O(1). This is Range Sum Query 2D - Immutable, and the same table counts set pixels in any rectangle of a bitmap (integral images in computer vision use exactly this construction).

Difference arrays

The inverse of a prefix sum. If many updates of the form “add delta to every element in [lo, hi]” arrive before any reads, apply each one in O(1) by marking only its endpoints, then recover the final array with one prefix-sum pass:

from itertools import accumulate

def range_add(n, updates):
    diff = [0] * (n + 1)
    for lo, hi, delta in updates:
        diff[lo] += delta
        diff[hi + 1] -= delta
    return list(accumulate(diff[:n]))

n = 6, updates: +2 on [1,3], +3 on [2,5], -1 on [0,1]

+2 on [1,3]:  diff[1] += 2, diff[4] -= 2
+3 on [2,5]:  diff[2] += 3, diff[6] -= 3
-1 on [0,1]:  diff[0] -= 1, diff[2] += 1

index:          0   1   2   3   4   5   6
diff:          -1   2   4   0  -2   0  -3
running sum:   -1   1   5   5   3   3        (slot 6 is discarded)

>>> range_add(6, [(1, 3, 2), (2, 5, 3), (0, 1, -1)])
[-1, 1, 5, 5, 3, 3]

m updates on n elements cost O(n + m) instead of O(nm). Uses: Corporate Flight Bookings, Car Pooling (is capacity ever exceeded?), counting how many intervals cover each point, and the 2D version for rectangle increments (mark four corners, then 2D prefix sum). The limitation is that reads are only cheap after all updates are applied. Interleaved updates and reads need a Fenwick tree or a segment tree with lazy propagation.

Kadane’s algorithm: maximum subarray

Maximum Subarray asks for the largest sum of a non-empty contiguous subarray. Brute force over all pairs is $O(n^2)$ (with running sums) and divide and conquer gives $O(n \log n)$. Kadane’s algorithm is O(n) and O(1) space. Jon Bentley’s Programming Pearls column popularized it and credits Jay Kadane with the linear solution.

The idea and why it is correct

Let $E_i$ be the best sum of a subarray that ends exactly at index $i$. Such a subarray is either the single element $a_i$, or some subarray ending at $i - 1$ extended by $a_i$. In the second case the best choice of that earlier piece is the one achieving $E_{i-1}$, because swapping in any better-summing piece ending at $i-1$ would improve the total. So:

$E_i = \max(a_i,\; E_{i-1} + a_i)$

Every subarray ends somewhere, so the answer is $\max_i E_i$. Equivalently: carry the running sum forward while it is positive, because a positive prefix can only help whatever follows it, and restart when it goes negative, because a negative prefix can only hurt. This is dynamic programming with the table collapsed to one variable (see Dynamic programming).

def max_subarray(nums):
    best = cur = nums[0]
    for x in nums[1:]:
        cur = max(x, cur + x)
        best = max(best, cur)
    return best

Tracking where the best run starts and ends:

def max_subarray_with_bounds(nums):
    best, best_lo, best_hi = nums[0], 0, 0
    cur, cur_lo = nums[0], 0
    for i in range(1, len(nums)):
        if cur < 0:
            cur, cur_lo = nums[i], i       # restart
        else:
            cur += nums[i]                 # extend
        if cur > best:
            best, best_lo, best_hi = cur, cur_lo, i
    return best, best_lo, best_hi

nums: -2   1  -3   4  -1   2   1  -5   4
cur:  -2   1  -2   4   3   5   6   1   5
best: -2   1   1   4   4   5   6   6   6
-> (6, 3, 6): nums[3..6] = [4, -1, 2, 1]

Pitfalls:

• All-negative input. Initializing best = 0 returns 0, the empty subarray, which is wrong when the problem requires a non-empty subarray. Initializing from nums[0] returns the largest element.
• Maximum Sum Circular Subarray. A wrapping subarray is the total minus a non-wrapping minimum subarray, so run Kadane for both max and min. If every element is negative, total − min would select the empty complement, so return the plain maximum in that case. For [5, -3, 5] the answer is 10.
• Maximum Product Subarray needs both the largest and smallest product ending at each index, since a negative number swaps them.
• The 2D version (maximum-sum rectangle) fixes a pair of rows, collapses the columns between them into a 1D array, and runs Kadane: $O(\text{rows}^2 \cdot \text{cols})$.

Dutch National Flag

Partition an array of three kinds of values (0, 1, 2) in one pass and O(1) space. Edsger Dijkstra posed it with the three colors of the Dutch flag. Sort Colors is the standard statement.

Three pointers maintain four regions:

[ 0 0 0 | 1 1 1 | ? ? ? ? | 2 2 2 ]
  0..low-1  low..mid-1  mid..high  high+1..n-1

def sort_colors(nums):
    low, mid, high = 0, 0, len(nums) - 1
    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1                       # do NOT advance mid

After swapping a 2 to the back, mid stays put because the element that came from high has not been examined yet. After swapping a 0 to the front, mid can advance because the element that came from low is known to be a 1 (or low == mid). Each iteration shrinks the unknown region by one, so at most n iterations.

The algorithm is not stable. It is also exactly the three-way partition used by quicksort to handle many equal keys (see Sorting), with “less than / equal to / greater than the pivot” in place of 0, 1 and 2. Counting sort (count the 0s, 1s and 2s, then overwrite) also works in two passes.

Boyer-Moore majority vote

Find the element appearing more than n/2 times, in O(n) time and O(1) space. Robert Boyer and J Strother Moore devised it around 1980.

Keep a candidate and a counter. A matching element increments the counter; a different one decrements it; at zero, the next element becomes the candidate.

def majority(nums):
    candidate, count = None, 0
    for x in nums:
        if count == 0:
            candidate = x
        count += 1 if x == candidate else -1
    return candidate

Why it works: each decrement pairs one occurrence of the candidate with one occurrence of something else and cancels both. A majority element has more occurrences than all other elements combined, so it cannot be fully cancelled and must be the survivor.

nums:      2  2  1  1  1  2  2
candidate: 2  2  2  2  1  1  2
count:     1  2  1  0  1  0  1
-> 2

The algorithm only guarantees the right answer if a majority exists. On [1, 2, 3] it returns 3. When existence is not promised, a second pass counting the candidate is required.

The n/3 variant

Majority Element II asks for every element appearing more than n/3 times. At most two such elements can exist, so keep two candidates and two counters. An element matching neither candidate, when both counters are positive, cancels one occurrence of each: three distinct elements removed at a time. Anything above n/3 survives.

def majority_n3(nums):
    c1, c2, n1, n2 = None, None, 0, 0
    for x in nums:
        if x == c1:
            n1 += 1
        elif x == c2:
            n2 += 1
        elif n1 == 0:
            c1, n1 = x, 1
        elif n2 == 0:
            c2, n2 = x, 1
        else:
            n1 -= 1
            n2 -= 1
    return [c for c in (c1, c2)
            if c is not None and nums.count(c) > len(nums) // 3]

The match checks must come before the zero checks; otherwise the same value can occupy both candidate slots. The verification pass is mandatory here, because the survivors are only candidates. The general form, with k − 1 counters finding everything above n/k, is the Misra-Gries summary used in streaming “heavy hitters” estimation.

Missing number problems

A family of problems about an array that should contain a known set of values but has one or two missing or duplicated.

Missing Number (n distinct values from 0..n, one missing). Either subtract the actual sum from the expected sum $n(n+1)/2$, or XOR all indices and values together, since every present value cancels with its index and only the missing one remains. Python integers do not overflow, so the sum version is safe; in fixed-width languages XOR avoids the overflow concern (see Bits and maths).

def missing_number(nums):
    n = len(nums)
    return n * (n + 1) // 2 - sum(nums)

def missing_number_xor(nums):
    x = len(nums)
    for i, v in enumerate(nums):
        x ^= i ^ v
    return x

Set Mismatch (values 1..n, one duplicated and one missing). Two equations in two unknowns: the sum difference gives dup − miss, the sum-of-squares difference gives dup² − miss², and dividing yields dup + miss.

def find_duplicate_and_missing(nums):
    n = len(nums)
    s = sum(nums) - n * (n + 1) // 2                                  # dup - miss
    sq = sum(x * x for x in nums) - n * (n + 1) * (2 * n + 1) // 6    # dup^2 - miss^2
    total = sq // s                                                   # dup + miss
    dup = (s + total) // 2
    return dup, dup - s

First Missing Positive (unsorted, any integers, find the smallest missing positive in O(n) time and O(1) extra space) uses cyclic sort: the answer is in 1..n+1, so place each value v in 1..n at index v − 1 by swapping, then scan for the first index whose value is wrong.

def first_missing_positive(nums):
    n = len(nums)
    for i in range(n):
        while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
            j = nums[i] - 1
            nums[i], nums[j] = nums[j], nums[i]
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1
    return n + 1

The inner while looks quadratic but each swap puts one value in its final position, so there are at most n swaps in total. The condition nums[nums[i] - 1] != nums[i] (rather than nums[i] != i + 1) is what stops an infinite loop on duplicates. first_missing_positive([3, 4, -1, 1]) is 2. The same in-place marking (swapping or negating) solves Find All Numbers Disappeared in an Array and Find All Duplicates in an Array, at the cost of modifying the input.

Array rotation

Rotate an array right by k in place. Repeating a one-step rotation k times is O(nk); copying into a new array is O(n) time but O(n) space. The reversal trick is O(n) time and O(1) space: reverse the whole array, then reverse the first k elements and the remaining n − k separately.

rotate [1 2 3 4 5 6 7] right by 3
reverse all:        7 6 5 4 3 2 1
reverse first 3:    5 6 7 | 4 3 2 1
reverse last 4:     5 6 7 | 1 2 3 4

It works because reversal of a concatenation reverses the order of the pieces and reverses each piece: $(AB)^R = B^R A^R$. Writing the array as $A B$ with $B$ the last $k$ elements, the first reversal gives $B^R A^R$, and reversing each piece back gives $B A$.

def rotate_right(nums, k):
    n = len(nums)
    if n == 0:
        return
    k %= n

    def reverse(lo, hi):
        while lo < hi:
            nums[lo], nums[hi] = nums[hi], nums[lo]
            lo += 1
            hi -= 1

    reverse(0, n - 1)
    reverse(0, k - 1)
    reverse(k, n - 1)

k %= n handles k > n, and the empty-array guard avoids a division by zero. In Python, nums[:] = nums[-k:] + nums[:-k] (after k %= n) is shorter and fast, but allocates two temporary lists. collections.deque.rotate does it in O(k). A related application: Search in Rotated Sorted Array is a binary search problem covered in Searching.

Matrix traversal

Spiral order

Maintain four boundaries (top, bottom, left, right) and peel off one ring at a time: across the top row, down the right column, back along the bottom row, up the left column, then shrink each boundary.

def spiral(matrix):
    out = []
    if not matrix:
        return out
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1
    while top <= bottom and left <= right:
        for c in range(left, right + 1):
            out.append(matrix[top][c])
        top += 1
        for r in range(top, bottom + 1):
            out.append(matrix[r][right])
        right -= 1
        if top <= bottom:
            for c in range(right, left - 1, -1):
                out.append(matrix[bottom][c])
            bottom -= 1
        if left <= right:
            for r in range(bottom, top - 1, -1):
                out.append(matrix[r][left])
            left += 1
    return out

 1  2  3  4
 5  6  7  8      spiral: 1 2 3 4 8 12 11 10 9 5 6 7
 9 10 11 12

The two if checks are the whole difficulty: on a single remaining row or column, the bottom and left passes would otherwise revisit cells already emitted. Testing with 1 × n, n × 1 and non-square shapes catches this.

Diagonals and zigzag

Every cell on an anti-diagonal has the same r + c; every cell on a main diagonal has the same r − c. Grouping by that key is the general technique. For anti-diagonal d, rows run from max(0, d − cols + 1) while r < rows and d − r >= 0:

def diagonals(matrix):
    rows, cols = len(matrix), len(matrix[0])
    out = []
    for d in range(rows + cols - 1):
        r = max(0, d - cols + 1)
        diag = []
        while r < rows and d - r >= 0:
            diag.append(matrix[r][d - r])
            r += 1
        out.append(diag)
    return out

def zigzag(matrix):
    out = []
    for d, diag in enumerate(diagonals(matrix)):
        out.extend(diag if d % 2 else reversed(diag))
    return out

For the 3 × 4 matrix above, diagonals returns [[1], [2, 5], [3, 6, 9], [4, 7, 10], [8, 11], [12]] and zigzag (Diagonal Traverse) returns [1, 2, 5, 9, 6, 3, 4, 7, 10, 11, 8, 12], reversing the even-numbered diagonals so the path alternates direction.

Rotate 90 degrees in place

Rotating clockwise maps (r, c) to (c, n − 1 − r). That is a transpose ((r, c) -> (c, r)) followed by reversing each row ((c, r) -> (c, n − 1 − r)):

def rotate_90(matrix):
    n = len(matrix)
    for i in range(n):
        for j in range(i + 1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    for row in matrix:
        row.reverse()

1 2 3     transpose   1 4 7    reverse rows   7 4 1
4 5 6     -------->   2 5 8    ----------->   8 5 2
7 8 9                 3 6 9                   9 6 3

O(n²) time, O(1) extra space, square matrices only (a non-square rotation changes the shape, so it cannot be in place). Counterclockwise is transpose then reverse the row order, or reverse each row then transpose. Out of place, [list(row) for row in zip(*matrix[::-1])] does the clockwise rotation in one line. Set Matrix Zeroes and Game of Life are other in-place matrix problems; both use spare state in the matrix itself (the first row and column as markers, or extra bits per cell) to avoid O(rows × cols) extra memory.

Intervals

Interval problems take a list of [start, end] pairs. Nearly all of them begin by sorting, after which overlapping intervals are adjacent and a single pass suffices. Be precise about whether endpoints are inclusive: [1, 2] and [2, 3] overlap if endpoints are closed (meetings sharing a minute), and do not if they are half-open (a meeting ending at 2 and one starting at 2).

Merge Intervals

Sort by start. Walk through, extending the last output interval when the next one starts before it ends, and starting a new one otherwise.

def merge_intervals(intervals):
    out = []
    for start, end in sorted(intervals):
        if out and start <= out[-1][1]:
            out[-1][1] = max(out[-1][1], end)
        else:
            out.append([start, end])
    return out

sorted: [1,3] [2,6] [8,10] [15,18]
[1,3]               out [[1,3]]
[2,6]   2 <= 3      out [[1,6]]
[8,10]  8 >  6      out [[1,6],[8,10]]
[15,18] 15 > 10     out [[1,6],[8,10],[15,18]]

The max is essential: [1, 10] followed by [2, 3] must stay [1, 10]. O(n log n) for the sort, O(n) for the pass.

Insert Interval

When the existing intervals are already sorted and disjoint, inserting one more needs no sort: copy those entirely before it, merge those that overlap it, copy the rest. O(n).

def insert_interval(intervals, new):
    out = []
    start, end = new
    i, n = 0, len(intervals)
    while i < n and intervals[i][1] < start:
        out.append(intervals[i])
        i += 1
    while i < n and intervals[i][0] <= end:
        start = min(start, intervals[i][0])
        end = max(end, intervals[i][1])
        i += 1
    out.append([start, end])
    out.extend(intervals[i:])
    return out

insert_interval([[1,2],[3,5],[6,7],[8,10],[12,16]], [4,8]) is [[1, 2], [3, 10], [12, 16]].

Interval scheduling

Choose the most non-overlapping intervals (equivalently, Non-overlapping Intervals: remove the fewest to make the rest disjoint). Sort by end time and greedily take each interval that starts after the last one taken ended.

def max_non_overlapping(intervals):
    count, last_end = 0, float("-inf")
    for start, end in sorted(intervals, key=lambda iv: iv[1]):
        if start >= last_end:
            count += 1
            last_end = end
    return count

The exchange argument: an optimal solution can always be modified to use the interval that ends first, since swapping it in for the optimal solution’s first interval frees at least as much room for the rest. Sorting by start time is the common mistake: one long interval that starts early would block many short ones. The proof is given in full in Greedy algorithms.

Meeting Rooms II (minimum rooms so no two overlapping meetings share one) is the maximum number of intervals covering any single point. Either sort the meetings by start and keep a min-heap of end times of rooms in use (see Heaps), or sort all starts and ends separately and sweep:

import heapq

def min_meeting_rooms(intervals):
    rooms = []                      # end times of occupied rooms
    for start, end in sorted(intervals):
        if rooms and rooms[0] <= start:
            heapq.heapreplace(rooms, end)   # reuse the room that frees up first
        else:
            heapq.heappush(rooms, end)
    return len(rooms)

min_meeting_rooms([(0, 30), (5, 10), (15, 20)]) is 2. A difference array over time also answers it when times are small integers.

When intervals arrive dynamically and queries ask “which stored intervals overlap this one?”, an interval tree or a segment tree is the right structure; PostgreSQL’s range types with GiST indexes serve the same purpose in a database.

Array rearrangement

Rearrangement problems permute an array to satisfy a positional rule. The techniques are the ones already covered: two pointers, cyclic placement, and reversal.

Rearrange Array Elements by Sign (equal numbers of positives and negatives, alternate them, preserve relative order). Preserving order in O(n) time is easiest with O(n) space:

def alternate_signs(nums):
    pos = [x for x in nums if x > 0]
    neg = [x for x in nums if x < 0]
    out = [0] * len(nums)
    out[0::2] = pos
    out[1::2] = neg
    return out

Doing it in place and stable is substantially harder (it needs rotations and is O(n²) or O(n log n)); if stability is not required, a two-pointer partition followed by swapping alternate positions is O(n) and in place.

Next Permutation rearranges into the next lexicographic ordering in place: find the rightmost i with nums[i] < nums[i + 1] (everything after it is non-increasing, so it is already the last permutation of that suffix), swap nums[i] with the rightmost element larger than it, then reverse the suffix to make it the smallest ordering.

def next_permutation(nums):
    i = len(nums) - 2
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1
    if i >= 0:
        j = len(nums) - 1
        while nums[j] <= nums[i]:
            j -= 1
        nums[i], nums[j] = nums[j], nums[i]
    nums[i + 1:] = reversed(nums[i + 1:])

[1, 3, 5, 4, 2]
pivot: i=1 (3 < 5; suffix 5 4 2 is non-increasing)
swap with rightmost > 3: that is 4  -> [1, 4, 5, 3, 2]
reverse suffix after i:              -> [1, 4, 2, 3, 5]

When i reaches −1 the array is the last permutation and reversing the whole thing wraps to the first. The algorithm handles duplicates correctly because of the >= and <= comparisons. Other members of the family: Wiggle Sort (a[0] <= a[1] >= a[2] <= ..., one pass of local swaps), placing each value at its index (cyclic sort, as in First Missing Positive), and moving all elements of one class to one side (the read/write pointer loop).

Flood fill

Flood Fill changes the color of a connected region of a grid, starting from one cell: every cell reachable through same-colored horizontal and vertical neighbors gets the new color. It is a graph traversal in which cells are vertices and adjacent same-colored cells are edges, so it is depth-first or breadth-first search; both are covered fully in Graph traversal.

def flood_fill(image, sr, sc, color):
    old = image[sr][sc]
    if old == color:
        return image                     # otherwise the loop never terminates
    rows, cols = len(image), len(image[0])
    stack = [(sr, sc)]
    image[sr][sc] = color
    while stack:
        r, c = stack.pop()
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < rows and 0 <= nc < cols and image[nr][nc] == old:
                image[nr][nc] = color
                stack.append((nr, nc))
    return image

O(rows × cols) time and up to that much stack space. Recoloring a cell when it is pushed (not when it is popped) doubles as the visited set. The old == color check is the classic pitfall: without it, recolored cells still match old and are pushed forever. A recursive version is shorter but hits Python’s default recursion limit of 1,000 on a region larger than about that many cells along one path, which an explicit stack avoids. Number of Islands, Surrounded Regions and Max Area of Island are the same traversal with different bookkeeping.

Summary