Prefix Sums and Hash Maps: The Coding Interview Combo You Should Master

Some of the most frequently asked coding interview questions look unrelated at first: "subarray sum equals K", "continuous subarray sum", "contiguous array with equal zeros and ones", "range sum query", and "count of subarrays divisible by K". They all fall to one idea: combine prefix sums with a hash map. Once you see this pattern, a whole family of medium-level problems becomes quick and reliable. What a prefix sum is A prefix sum array stores running totals: prefix[i] is the sum of the first i elements. The sum of any subarray from index l to r is prefix[r + 1] - prefix[l]. Building the array takes O(n), and each range query afterward is O(1). That alone solves "range sum query" problems where the array does not change. The key insight A subarray sums to K exactly when two prefix sums differ by K. So as you scan the array and keep a running total, you ask: "Have I seen a previous running total equal to current - K?" A hash map counting how many times each running total has occurred answers that in O(1). Subarray sum equals K count = 0 running = 0 seen = {0: 1} for x in nums: running += x count += seen.get(running - k, 0) seen[running] = seen.get(running, 0) + 1 The initial entry {0: 1} handles subarrays that start at index zero. Forgetting it is the most common bug, and interviewers often watch for whether you explain it. Why sliding window does not work here Candidates sometimes try two pointers. That only works when all numbers are non-negative, because then the window sum moves predictably. With negative numbers, prefix sums plus a hash map is the right tool. Saying this out loud shows you understand when each pattern applies. Variation: divisible by K For "count subarrays whose sum is divisible by K", store running % k instead of running. Two prefixes with the same remainder bound a subarray divisible by K. Watch out for negative remainders in languages like Java or C++, where you need ((running % k) + k) % k. Variation: longest subarray For "longest subarray with sum K" or "contiguous array" (equal zeros and ones, by mapping zeros to -1), store the first index where each running total appears instead of a count. When you see the same total again, the subarray between has sum zero, and its length is the current index minus the stored index. Only store the first occurrence so lengths stay maximal. Variation: 2D prefix sums For matrices, prefix[i][j] holds the sum of the rectangle from (0,0) to (i-1, j-1). A sub-rectangle sum uses inclusion-exclusion: total minus top minus left plus top-left corner. "Number of submatrices that sum to target" combines 2D prefix sums with the 1D hash map trick across column pairs. Complexity The one-pass hash map approach is O(n) time and O(n) space. Compare it to the brute force O(n^2) of checking every subarray, and state the improvement clearly. Edge cases - Empty array. - K equal to zero. - All negative numbers. - Very large sums, where overflow matters in fixed-width integer languages. How to present it Start with brute force in one sentence, observe that subarray sums are differences of prefix sums, then introduce the map. Dry-run on a short array such as [1, 2, 3] with K = 3, writing the running total and the map after each step. Interviewers value that trace more than speed. Practice list Subarray sum equals K, continuous subarray sum, contiguous array, subarray sums divisible by K, range sum query, and product of array except self (a prefix/suffix cousin). During live rounds, some candidates use Linkjob AI (https://linkjob.ai), which provides real-time help during job interviews and technical interviews, to stay structured under pressure. Master this combo and you will recognize it instantly the next time it appears.