Here's a problem that looks nothing like the range queries you just solved — until you squint.
You're given an array of integers (positive, negative, or zero) and a target k. The task: count how many contiguous subarrays sum to exactly k. This is LeetCode 560, one of the top-20 most-asked questions at FAANG companies, and for good reason — it separates people who understand prefix sums from people who merely memorized the formula.
The brute-force approach is the obvious one: try every possible start index, try every possible end index, sum the subarray between them. Two nested loops, each up to n, with a sum that costs up to n — that's O(n^2) at best (with a running sum optimization) and O(n^3) at worst. For n = 20,000, even the optimized version means 200 million operations.
But think about what you already know. You built a staircase — a prefix sum array — where each step records the cumulative height. If the staircase is at height 9 at position j, and it was at height 3 at some earlier position i, then the subarray from i to j sums to 9 - 3 = 6. You didn't add anything. You just measured a height difference.
So finding subarrays that sum to k is the same as finding pairs of staircase positions where the height difference is exactly k. The question becomes: at each new step, has the staircase ever been at a height that's exactly k below the current height?
What if the answer is hiding in the staircase itself? What if you didn't need to search at all — just remember?
Think about what question you'd need to answer at each step — and what kind of tool could answer it instantly.
If prefix[j] - prefix[i] = k, what does that tell us about the subarray from index i to j?
Build the staircase step by step. At each new height, something in your notebook might be relevant — can you figure out what to look for?
k = 5. Select a start and end — this is what brute force does for every possible pair.What you just did — scanning the staircase while consulting a running notebook of past heights — is the O(n) solution to LeetCode 560. Let's crystallize the three moving parts so you can reconstruct this from scratch under interview pressure.
Part 1: The staircase. You maintain a running prefix sum. As you walk through the array left to right, the “height” at position j is prefix[j] = arr[0] + arr[1] + ... + arr[j-1]. You don't need to store the entire prefix array — a single running variable is enough.
Part 2: The question. At each new height h, you ask: "Has the staircase ever been at height h - k?" If yes, then between that earlier position and the current one, the subarray sums to exactly k. This is the reframe that makes the problem tractable — you turned a range question (“does this subarray sum to k?”) into a point question (“have I seen this height before?”).
The notebook records every staircase height you've visited. When you arrive at a new height h, you look up h - k. Why does finding that value in the notebook mean you've found a valid subarray?
Part 3: The notebook. A hash map that records how many times each height has been visited. Why count instead of a boolean? Consider the array [1, -1, 0] with k = 0.
Walk through it step by step:
height = 0, notebook = {0: 1} (ground level counts as one visit).arr[0] = 1: height = 1. Look up 1 - 0 = 1 in the notebook. Not found. Record {0: 1, 1: 1}.arr[1] = -1: height = 0. Look up 0 - 0 = 0 in the notebook. Found with count 1 — that's one valid subarray ([1, -1]). Record {0: 2, 1: 1}.arr[2] = 0: height = 0. Look up 0 - 0 = 0 in the notebook. Found with count 2 — that's two more valid subarrays ([1, -1, 0] and [0]). Record {0: 3, 1: 1}.Total: 3 subarrays. And notice — without the count, you'd have missed the third one. The height 0 appeared three times, and each appearance creates a different valid subarray with every other appearance at the same height.
The {0: 1} initialization is the ground level — “before processing any element, the staircase was at height 0, and that happened once.” Without it, subarrays that start at the very beginning of the array (where prefix[i] = 0) get silently dropped. This is the single most common bug in prefix-sum + hashmap solutions, and it shows up in interviews constantly.
The deep connection worth internalizing: prefix sums turn a range question into a point question. And hash maps are the ultimate tool for answering point questions. When you see “count subarrays with property X” and the property involves a contiguous sum, reach for this combo: running prefix sum + hash map of seen values. It's O(n) time, O(n) space, and it handles negative numbers, zeros, and duplicate heights gracefully.
What would happen if the array contained only positive integers? You wouldn't need the hash map at all — a sliding window would work. The hash map is the price you pay for handling negatives. Keep that tradeoff in your back pocket.