Classic Array Tricks

Some array problems don't belong to a broad pattern. One specific trick solves each of them, and that trick is hard to invent under pressure but easy to remember once you've seen it. This note collects four of them. Each runs in $O(n)$ time (or $O(1)$ per operation) with $O(1)$ extra space.

How to spot them#

Since each trick solves a narrow kind of problem, the hard part is knowing when to use it. Each one has a recognizable prompt:

Boyer-Moore majority vote#

The first trick finds a majority value without counting every value. Think of it as cancellation. Pair each vote for the current candidate against a vote for something else and cross both out. A value that holds more than half the votes can't be fully canceled, so it is the one left standing.

1. Keep a candidate and a count.
2. If count is 0, adopt the current value as the new candidate.
3. Add 1 for a matching value, subtract 1 otherwise.

The vote only finds the value that survives. When the problem does not guarantee that a majority exists, make a second pass to check that the survivor appears often enough.

Dutch national flag#

The second trick sorts a three-valued array in a single pass, without counting. Three pointers split the array into four zones: [0, low) holds 0s, [low, mid) holds 1s, [mid, high] is unknown, and (high, n) holds 2s. Look at nums[mid] and shrink the unknown zone by one each step: a 0 swaps down to low, a 1 stays, and a 2 swaps up to high.

Template#

The vote and the flag both fit in a few lines of pseudocode. First the vote:

candidate = none, count = 0
for each x in items:
    if count == 0:
        candidate = x            # everything before has canceled out
    if x == candidate: count += 1
    else: count -= 1
return candidate                 # verify it if a majority is not promised

Then the three-zone partition:

low = mid = 0, high = n - 1
while mid <= high:
    if items[mid] is in the low group:
        swap items[low] and items[mid]
        low += 1, mid += 1       # what came from low is already known
    else if items[mid] is in the middle group:
        mid += 1
    else:
        swap items[mid] and items[high]
        high -= 1                # keep mid: the new value is unseen

Rotate by reversing#

The last two tricks are about moving elements in place instead of copying them. To rotate an array to the right by k, reverse the whole array, then reverse the first k elements, then reverse the rest.

Here's what each reversal does on a small example:

The first reversal moves the last k elements to the front, but backwards. The two partial reversals put each block back in order. The same "reverse fixes the orientation" idea rotates a matrix (see Math & Bits).

Delete in O(1): swap with the last#

A set with $O(1)$ get-random needs a list for random access and a hashmap from value to index for lookups. The catch is that deleting from the middle of a list is $O(n)$, so don't. Instead:

1. Look up the index i of the value to delete.
2. Move the last element into slot i, and update its index in the hashmap.
3. Pop the last slot and delete the value from the hashmap.

Order inside the list doesn't matter for get-random, which is what makes the swap legal.

Pitfalls#

These are the mistakes that most often cost a correct answer.

• Dutch flag: advancing mid after swapping with high. The value that arrived from the right hasn't been examined yet.
• Boyer-Moore without verification. Candidates always survive the vote, even when none of them is frequent enough. Count them again when the majority is not guaranteed.
• Rotation with k > n. Reduce k first, or the reversal bounds are wrong.
• Swap-delete on the last element itself. The swap is then a no-op, so the order of the map updates matters.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with the first three.

• 169. Majority Element
• 229. Majority Element II
• 75. Sort Colors
• 189. Rotate Array
• 380. Insert Delete GetRandom O(1)
• 48. Rotate Image

Hints#

Open a hint only after you have tried the problem for a while.

Key takeaways#

• Boyer-Moore: a majority survives pairwise cancellation; with two candidates, verify at the end.
• Dutch flag: four zones, three pointers; after swapping with high, re-examine mid.
• Rotation by k is three reversals.
• $O(1)$ delete from a list: move the last element into the hole and fix the index map.