Hash maps and sliding windows

A hash map finds a value by its key in O(1) time on average, so you don't have to go searching for something you've already seen. A sliding window tracks a stretch of a sequence and moves its ends forward so you don't recalculate every possible range. Put them together and a lot of O(n²) solutions turn into O(n).

The right edge moves forward once per loop. The left edge only ever moves forward too, so the whole thing stays linear. A hash map keeps track of whatever you need to know about what's in the window:

def longest_without_repeats(text):
    last_seen = {}
    start = 0
    best = 0
    for end, character in enumerate(text):
        if character in last_seen and last_seen[character] >= start:
            start = last_seen[character] + 1
        last_seen[character] = end
        best = max(best, end - start + 1)
    return best

When a character repeats, the left edge jumps past its last copy. The part people miss is checking that the copy is still inside the window.

• Look out for words like "contiguous," "substring" or "longest."
• Say what has to stay true about the window the whole time.
• Mention that hash map lookups are O(1) on average, since worst case is worse.

Two sum, then a window

First: given a list of numbers and a target, return the positions of two numbers that add up to it. Then: find the length of the shortest stretch of positive numbers whose sum is at least a target.

1. Two sum with nested loops is O(n²). Instead, walk the list once and keep a hash map from each value to its position.
2. At each number x, check if target - x is already in the map. If it is, you're done. If not, add x. One pass, O(n) time and O(n) space.
3. Check the map before adding x, or a number could pair with itself.
4. For the shortest stretch, a sliding window works because every number is positive. Growing the window always raises the sum, and shrinking always lowers it.
5. Move the right edge forward and add each number. While the sum is at least the target, record the length, then subtract the leftmost number and move the left edge forward.
6. Each edge only moves forward, so each number is added once and removed once. That's O(n).
7. With [2, 3, 1, 2, 4, 3] and a target of 7, the window shrinks to [4, 3], so the answer is 2.

Things interviewers tend to ask once you've brought this up.

What if the numbers can be negative?

The window stops working, since growing it can lower the sum. Use prefix sums: keep a map of running totals, and look for the total you'd need to subtract.

How do you count subarrays that sum to exactly k?

Prefix sums with a map from each running total to how many times you've seen it. At each step, add the count of (total - k).

Longest substring with at most two distinct characters?

A window with a map counting characters inside it. When there are more than two keys, shrink from the left until there are two again.

When is a hash map lookup not O(1)?

When lots of keys hash to the same spot, which can happen with bad hash functions or keys chosen on purpose to collide. On average it's O(1), and the worst case is O(n).

• Using a sliding window when there are negative numbers.
• Moving the left edge backward, which makes it O(n²) again.
• Not saying what's always true about the window.
• Adding to the map before checking it, so an element matches itself.
• Off-by-one errors when computing the window length (it's right - left + 1).

• Binary searchCut the search in half, even when you're searching for an answer.
• Heaps and priority queuesAlways have the smallest or largest item ready.
• Dynamic programmingSolve each subproblem once and reuse the answer.