Hash maps, two pointers, sliding windows and prefix sums

What it is

Four patterns that between them account for more interview problems than every other pattern combined, and that share a single underlying move: replace a nested loop by carrying state across the outer loop. The brute force is always "for each position, scan the rest". Each pattern is a different answer to "what could I remember from the earlier positions that makes the inner scan unnecessary?"

Hash map / frequency counting remembers what has been seen, so a membership question costs $O(1)$ instead of a scan. Two pointers exploits sorted order so that a failed comparison rules out a whole region rather than one candidate. Sliding window maintains an aggregate over a contiguous range and updates it incrementally as the range moves. Prefix sums precompute cumulative totals so any range sum is one subtraction, and their dual, the difference array, does the reverse: it makes range updates cheap and pays once at the end.

Don't be confused: two pointers and sliding window are not the same pattern. They look identical (two indices moving through an array) and are often taught together, which hides the distinction that decides which one a problem wants. Two pointers usually moves its indices toward each other from the ends of a sorted array, and each step discards a candidate permanently. Sliding window moves both indices in the same direction over an array whose order is fixed by the problem, and it maintains an aggregate over the span between them. Sorting destroys a sliding window problem, because the contiguity it depends on is the input's order. If you catch yourself wanting to sort before a window problem, you have misread the problem.

The second distinction that matters: a fixed-size window and a variable-size window are different code. Fixed size adds the entering element and drops the leaving one in lockstep. Variable size advances the right edge greedily and advances the left edge only when an invariant breaks. Mixing them up produces code that passes the samples and fails on the edges.

The problem it solves

Concretely: "does any pair in this array sum to a target?" is $O(n^2)$ by nested loop. The hash map version is $O(n)$ because for each element you ask "have I already seen my partner" rather than "will I later find my partner", and the first question is answerable from state you already hold. That inversion, from a forward search to a backward lookup, is the entire trick and it generalises.

"What is the sum of elements 40,000 through 90,000?" costs 50,000 additions, and if the query repeats a million times the cost is unacceptable. One $O(n)$ pass building prefix sums makes every subsequent query a single subtraction. The mirror problem, "add 5 to every element between these two indices, a million times", costs $O(mn)$ done directly and $O(m + n)$ with a difference array.

Mechanics

"""Hash map counting, two pointers, sliding window, prefix sums, difference arrays.

Runnable: `python3 array_patterns.py`. These four patterns cover more interview
problems than any other group, and they share one idea: replace a nested loop by
carrying state across the outer loop.
"""

from collections import Counter, defaultdict


# --- Hash map / frequency counting -------------------------------------------
def two_sum(nums, target):
    """The canonical trade of time for space: instead of asking "is there a
    partner for nums[i] somewhere to my right", record what you have seen and
    ask "have I already seen my partner". One pass, O(n) time and space."""
    seen = {}
    for i, n in enumerate(nums):
        if target - n in seen:
            return (seen[target - n], i)
        seen[n] = i           # after the check, so nums[i] cannot pair with itself
    return None


def group_anagrams(words):
    """Frequency counting where the KEY is the interesting part. Sorting each
    word is O(k log k); a 26-slot count tuple is O(k) and is the better answer
    when words are long."""
    groups = defaultdict(list)
    for w in words:
        key = tuple(sorted(Counter(w).items()))
        groups[key].append(w)
    return [groups[k] for k in sorted(groups, key=lambda k: groups[k][0])]


# --- Two pointers ------------------------------------------------------------
def three_sum(nums):
    """Two pointers is what you get when sorting buys you a decision rule: with
    a sorted array, if the sum is too small only moving LEFT rightwards can help.
    That is what turns O(n^2) inner search into O(n)."""
    nums = sorted(nums)
    out = []
    for i in range(len(nums) - 2):
        if i and nums[i] == nums[i - 1]:
            continue                       # skip duplicate anchors
        lo, hi = i + 1, len(nums) - 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
                while lo < hi and nums[lo] == nums[lo - 1]:
                    lo += 1                # skip duplicate seconds
                hi -= 1
    return out


# --- Sliding window ----------------------------------------------------------
def longest_unique(s):
    """Variable-size window. The invariant: the window [lo, hi] always holds
    distinct characters. When hi breaks it, lo advances just far enough to
    restore it. Each index is visited at most twice, so O(n) not O(n^2)."""
    last = {}
    lo = best = 0
    best_span = (0, 0)
    for hi, ch in enumerate(s):
        if ch in last and last[ch] >= lo:
            lo = last[ch] + 1              # jump, do not step
        last[ch] = hi
        if hi - lo + 1 > best:
            best = hi - lo + 1
            best_span = (lo, hi + 1)
    return best, s[best_span[0]:best_span[1]]


def max_sum_window(nums, k):
    """Fixed-size window. Add the entering element, drop the leaving one. The
    error to avoid is recomputing the sum each step, which is O(nk)."""
    if len(nums) < k:
        return None
    cur = sum(nums[:k])
    best, at = cur, 0
    for i in range(k, len(nums)):
        cur += nums[i] - nums[i - k]
        if cur > best:
            best, at = cur, i - k + 1
    return best, at


# --- Prefix sums -------------------------------------------------------------
def build_prefix(nums):
    """prefix[i] is the sum of the first i elements, so prefix[0] == 0. That
    leading zero is not decoration: it is what makes range_sum need no special
    case for a range starting at index 0."""
    prefix = [0] * (len(nums) + 1)
    for i, n in enumerate(nums):
        prefix[i + 1] = prefix[i] + n
    return prefix


def range_sum(prefix, lo, hi):
    """Sum of nums[lo:hi], half open, in O(1) after O(n) preprocessing."""
    return prefix[hi] - prefix[lo]


def subarrays_summing_to(nums, target):
    """Prefix sums plus a hash map. If prefix[j] - prefix[i] == target then
    prefix[i] == prefix[j] - target, so count how many earlier prefixes had that
    value. Handles negative numbers, which the sliding window cannot."""
    counts = Counter({0: 1})               # the empty prefix, so a match at the start counts
    running = total = 0
    for n in nums:
        running += n
        total += counts[running - target]
        counts[running] += 1
    return total


# --- Difference array --------------------------------------------------------
def apply_range_updates(n, updates):
    """The dual of a prefix sum. To add v to every element of [lo, hi), record
    +v at lo and -v at hi, then take a running sum at the end. Turns m range
    updates from O(m*n) into O(m + n)."""
    diff = [0] * (n + 1)
    for lo, hi, v in updates:
        diff[lo] += v
        diff[hi] -= v
    out, running = [], 0
    for i in range(n):
        running += diff[i]
        out.append(running)
    return out


if __name__ == "__main__":
    nums = [2, 7, 11, 15, 3]
    print("two_sum([2,7,11,15,3], 18) ->", two_sum(nums, 18), "= indices of", 7, "and", 11)
    print("group_anagrams          ->", group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))

    print()
    print("three_sum               ->", three_sum([-1, 0, 1, 2, -1, -4]))
    n, sub = longest_unique("abcabcbb")
    print("longest_unique(abcabcbb)->", n, repr(sub))
    n, sub = longest_unique("pwwkew")
    print("longest_unique(pwwkew)  ->", n, repr(sub))
    print("max_sum_window(k=3)     ->", max_sum_window([2, 1, 5, 1, 3, 2], 3), "(sum, start index)")

    print()
    arr = [3, -1, 4, 1, 5, -9, 2, 6]
    pre = build_prefix(arr)
    print("array                   :", arr)
    print("prefix                  :", pre)
    print("range_sum(2, 6)         ->", range_sum(pre, 2, 6), "= sum of", arr[2:6])
    print("subarrays summing to 5  ->", subarrays_summing_to(arr, 5))

    print()
    ups = [(1, 4, 10), (2, 6, 5), (0, 3, -2)]
    print("n=7, updates            :", ups)
    print("difference array result :", apply_range_updates(7, ups))

Four details worth defending under questioning.

In two_sum, the insert happens after the check. Write seen[n] = i before the if and an element pairs with itself, so two_sum([3, 5], 6) wrongly returns (0, 0). The ordering is the correctness argument, not a style choice.

The prefix array has a leading zero and is length $n+1$. prefix[i] is the sum of the first $i$ elements, so prefix[0] = 0 denotes the empty prefix. This is what lets range_sum be prefix[hi] - prefix[lo] with no special case when lo == 0. Build it without the leading zero and you will write a branch, and that branch is where the off by one lives.

longest_unique jumps the left edge, it does not step it. On seeing a repeat, lo moves to last[ch] + 1 directly. A loop that increments lo one character at a time is still $O(n)$ amortised, so it is not wrong, but the guard last[ch] >= lo is essential in the jumping version: without it, a character last seen before the current window drags lo backwards and the window grows to include duplicates.

subarrays_summing_to seeds the counter with {0: 1}. That entry represents the empty prefix and is what allows a qualifying subarray that starts at index 0 to be counted. Drop it and you undercount by exactly the number of qualifying prefixes, which is the kind of bug that passes half the tests.

Worked example

two_sum([2,7,11,15,3], 18) -> (1, 2) = indices of 7 and 11
group_anagrams          -> [['bat'], ['eat', 'tea', 'ate'], ['tan', 'nat']]

three_sum               -> [(-1, -1, 2), (-1, 0, 1)]
longest_unique(abcabcbb)-> 3 'abc'
longest_unique(pwwkew)  -> 3 'wke'
max_sum_window(k=3)     -> (9, 2) (sum, start index)

array                   : [3, -1, 4, 1, 5, -9, 2, 6]
prefix                  : [0, 3, 2, 6, 7, 12, 3, 5, 11]
range_sum(2, 6)         -> 1 = sum of [4, 1, 5, -9]
subarrays summing to 5  -> 4

n=7, updates            : [(1, 4, 10), (2, 6, 5), (0, 3, -2)]
difference array result : [-2, 8, 13, 15, 5, 5, 0]

Trace the difference array, because it is the pattern most people have never actually implemented. Three updates land on a 7-element array: add 10 to [1,4), add 5 to [2,6), add -2 to [0,3). The difference array records only six numbers, two per update, and the final running sum produces [-2, 8, 13, 15, 5, 5, 0]. Check index 2 by hand: it is inside all three ranges, so it should be $10 + 5 - 2 = 13$, and it is. Index 4 is inside only the second range, so it should be 5, and it is. Index 6 is outside all three, so 0. The array is length $n+1$ because the closing marker for a range ending at $n$ has to go somewhere, and dropping that slot is the standard crash.

longest_unique("pwwkew") returning 'wke' rather than 'pww' or 'wke w' is the case that catches the missing last[ch] >= lo guard: by the time the window reaches the second w at index 5, the character w was last seen at index 2, which is inside the current window, so lo correctly jumps to 3.

subarrays_summing_to(arr, 5) returning 4 on [3, -1, 4, 1, 5, -9, 2, 6] is the case that justifies the hash map over a sliding window: the array contains -9, and a sliding window requires that extending the window never decreases the aggregate. Negative numbers break that monotonicity, so the window approach silently returns a wrong answer here while the prefix-sum approach is correct. Interviewers add a negative number for exactly this reason.

Production evidence

Summed-area tables are 2D prefix sums. The Viola-Jones face detector (2001) computes an "integral image" once per frame, after which the sum of any rectangle is four array lookups regardless of rectangle size. That is the only reason the cascade could evaluate thousands of rectangle features per window in real time on 2001 hardware. OpenCV exposes it directly as cv::integral.

Sliding windows in stream processing. Flink and Kafka Streams both implement windowed aggregations by maintaining incremental state and updating it as records enter and leave the window, rather than recomputing over the window's contents. The fixed-size add-and-drop in max_sum_window is the same arithmetic, and the same reason: recomputation is $O(nk)$ and does not survive contact with a real event rate.

Sliding window rate limiters. The "sliding window counter" algorithm used by API gateways and CDN edge configurations keeps per-interval counts and weights the partial overlap, precisely to avoid the boundary burst that a fixed-window counter allows (two full quotas within one window length, straddling the reset).

Frequency counting at a scale where the hash map does not fit. When the key space is too large to count exactly, the production move is a Count-Min Sketch, which trades exact counts for a bounded overestimate in fixed memory. Naming this in an interview is the sign that you have thought past the whiteboard version, and it connects directly to the heavy-hitters problem the top-K pattern solves.

Two pointers is the merge step. The merge in merge sort, and the merge join in every relational database's execution engine, is two pointers over sorted inputs. Postgres chooses a merge join when both sides are already sorted or cheaply sortable, exactly because the pointer walk is linear once the ordering is paid for.

The debate

When do you sort first? Sorting costs $O(n \log n)$ and buys you the two-pointer decision rule. It is worth it when the alternative is $O(n^2)$, which is why three_sum sorts. It is not worth it when a hash map already gives you $O(n)$, which is why two_sum does not. The trap is that sorting also destroys index information, so any problem asking for original indices needs either a hash map or an explicit index-carrying sort. My rule: reach for the hash map first, and sort only when you need an ordering property that hashing cannot give you, namely "everything to my left is smaller".

Sliding window versus prefix sums for subarray problems. Sliding window is $O(1)$ extra space and one pass; prefix sums are $O(n)$ space. That makes the window look strictly better, and for positive-only inputs it is. But the window's correctness rests on monotonicity: extending the window must move the aggregate in one direction. Sums of non-negative numbers are monotonic; sums with negatives are not, and neither is a product that can include zero. My position: if the problem statement does not guarantee non-negative values, use prefix sums with a hash map, and say why. The extra $O(n)$ space is cheap and the alternative is a wrong answer that looks right on the sample input. If the constraints do guarantee non-negativity, take the window and state the dependency out loud, because that sentence is the whole signal.

Difference arrays versus a segment tree or Fenwick tree. A difference array handles range updates in $O(1)$ each but only answers queries after an $O(n)$ finalisation, so it is the right structure when all updates come before all queries. Interleave them and it degenerates. A Fenwick tree handles both in $O(\log n)$ and is the correct answer when updates and queries are mixed. Reach for the difference array first because it is ten lines and the batch pattern is common; name the Fenwick tree as the escalation before the interviewer does.

Follow-up Q&A

What is the actual complexity of the variable-size sliding window, and why is the inner while not a problem? $O(n)$. The inner loop advances lo, lo never decreases, and it is bounded by $n$, so across the whole run the inner loop body executes at most $n$ times total. This is an amortised argument and stating it correctly is the point: a candidate who says "there's a nested loop so it's $O(n^2)$" has not understood the pattern, and one who says "it's $O(n)$" without the monotonicity argument has memorised it.

group_anagrams sorts the letters of each word. Can you do better? Yes, and it matters when words are long. Sorting a length-$k$ word is $O(k \log k)$; a fixed 26-slot count vector is $O(k)$, giving $O(nk)$ overall instead of $O(nk \log k)$. The code uses a sorted Counter because it generalises past a 26-letter alphabet, which matters for a multilingual corpus where the alphabet is Unicode-sized and a fixed array is not an option. Say the tradeoff rather than asserting one is better.

How do you extend prefix sums to two dimensions? prefix[i][j] is the sum of the rectangle from the origin to $(i,j)$. Build it with inclusion-exclusion, prefix[i][j] = grid[i][j] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1], and query the same way with four terms. The subtraction of the doubly counted corner is the whole idea, and it is the integral image above.

Prefix sums with floating point over a long array: any issue? Yes, and it is a real one. Error accumulates along the running sum, so a range sum near the end of a long array is a difference of two large, similarly sized numbers, which is catastrophic cancellation. Depending on the data this can lose most of your significant digits. Mitigations: use Kahan summation when building, keep the accumulator at higher precision than the data (float64 for float32 input), or use a Fenwick tree, whose partial sums are over $O(\log n)$ elements rather than $O(n)$ and so accumulate far less error. Integers do not have this problem, which is why the pattern is usually taught with them and why the issue surprises people in production.

When would you use a difference array in real code, not a puzzle? Any "apply many overlapping interval effects, then read the result once" shape. Booking and capacity systems (how many resources are in use at each minute given a list of reservations), scheduling, and gain or volume envelopes over a timeline. It is the same computation as the sweep line over intervals, which is why those two patterns keep appearing in the same problems.

The interviewer says the array does not fit in memory. Now what? Prefix sums and difference arrays both stream: they need one pass and $O(1)$ state per element beyond the output. The problem is the output array, not the algorithm. If range queries must be served over a dataset larger than memory, the answer is a persisted, blocked structure: store prefix sums per block, keep block boundaries in memory, and read the one block that contains each endpoint. That is roughly how columnar formats accelerate aggregate queries with per-block min, max and sum statistics in the footer.

Common misconceptions

"Hash map lookups are $O(1)$, so the whole thing is guaranteed $O(n)$." Average case. Worst case is $O(n)$ per lookup under collisions, and adversarial key sets can force it, which is why languages randomise hash seeds. It has been exploited: the 2011 hash collision denial of service affected PHP, Python, Ruby, Java and others by posting form fields chosen to collide. For an interview, say "expected $O(n)$" and you are right; the follow-up about adversarial input is a gift.

"Sliding window works for any subarray problem." Only when the aggregate is monotonic in the window's extent, as above. Negative numbers, or a "product less than K" problem where an element is zero, break it.

"Two pointers requires a sorted array." The most common form does, but not all. The fast-and-slow pointer pattern (cycle detection in a linked list, finding a midpoint) uses two pointers moving at different speeds over an unsorted structure. What two pointers actually requires is a decision rule that lets one comparison eliminate a region, and sortedness is the most common source of one, not the only one.

"Prefix sums are just an optimisation." They change what is expressible. range_sum at $O(1)$ is what makes an $O(n^2)$ algorithm out of an $O(n^3)$ one in problems like maximum submatrix sum, where the range query sits inside two loops. That is a complexity class change, not a constant factor.

Interview delivery note

The sentence that earns the most per word here is the one that names the invariant before you write the loop: "The window between lo and hi always contains distinct characters; hi advances every step and lo advances only to restore that, so each index moves at most twice and this is $O(n)$." State the invariant, state why it gives the bound, then write. Interviewers who have seen fifty candidates code this pattern are listening for whether you understand it or have memorised its shape, and the invariant is what distinguishes those.

The senior-to-staff separator: naming the input that would break your approach, and saying what you would switch to. "I am using a sliding window, which assumes the values are non-negative so extending the window never lowers the sum. If negatives are possible, this is wrong and I would switch to prefix sums with a hash map of counts, same $O(n)$ but $O(n)$ space." A senior candidate produces working code. A staff candidate produces working code plus the boundary of its correctness, and that boundary is what a team actually needs from whoever writes the shared utility.

The Staff & Team Lead Interview Reference