Prefix Sum LeetCode Pattern Guide

If you have ever written a nested loop to compute the sum of a subarray, you have solved a problem the hard way. The prefix sum pattern eliminates that inner loop entirely, turning range queries from O(n) per query to O(1). It is one of the most useful techniques in coding interviews, and yet many candidates overlook it because it seems too simple.

Prefix sum leetcode problems appear across difficulty levels — from easy problems like Running Sum of 1d Array (#1480) to medium classics like Subarray Sum Equals K (#560) and Continuous Subarray Sum (#523). The pattern is always the same: precompute cumulative sums, then use subtraction to answer any range query instantly.

This guide walks you through the core concept, the reusable template, the powerful hash map variant, five classic problems, common mistakes, and a practice strategy to lock the pattern into long-term memory.

A prefix sum array stores the cumulative sum of elements from the beginning of an array up to each index. Given an input array nums of length n, you build a prefix array of length n+1 where prefix[0] = 0 and prefix[i] = prefix[i-1] + nums[i-1]. This takes O(n) time and O(n) space.

Once you have the prefix sum array, the sum of any subarray nums[i..j] is simply prefix[j+1] - prefix[i]. No loop, no repeated addition — just a single subtraction in O(1) time. This is the core insight behind every prefix sum problem.

Think of it like a running odometer. If the odometer reads 150 miles at checkpoint A and 400 miles at checkpoint B, the distance between them is 400 - 150 = 250. You never need to re-drive the road to find out.

The prefix sum template has two phases. First, build the prefix array by iterating through the input and accumulating sums. Second, answer queries by subtracting two prefix values. The template is deceptively simple, but getting the index offsets right is where most people stumble.

For the basic version, create an array of size n+1, set prefix[0] = 0, and fill it with prefix[i] = prefix[i-1] + nums[i-1]. The extra element at index 0 is crucial — it handles the case where your subarray starts at the beginning of the array. Without it, you need special-case logic that invites bugs.

For the hash map variant — which solves "subarray sum equals K" style problems — you replace the prefix array with a hash map that counts how many times each prefix sum has occurred. As you iterate, you check whether (currentSum - target) exists in the map. If it does, you have found one or more subarrays that sum to the target.

Five LeetCode problems form the core of the prefix sum pattern. If you can solve all five confidently, you have the pattern locked in. Each one teaches a slightly different angle on the same underlying technique.

Range Sum Query - Immutable (#303) is the purest prefix sum problem. You precompute the prefix array once, then answer unlimited range sum queries in O(1) each. It is the perfect first problem to learn the pattern because there are no tricks — just build and query.

Subarray Sum Equals K (#560) is the most important prefix sum problem for interviews. It combines prefix sums with a hash map to find the count of subarrays that sum to a target value K in O(n) time. The brute force is O(n^2), so this is a clear win.

Continuous Subarray Sum (#523) adds a modular arithmetic twist — you need subarrays whose sum is a multiple of k. The trick is storing prefix sums modulo k in the hash map. If two prefix sums have the same remainder, the subarray between them sums to a multiple of k.

Product of Array Except Self (#238) is prefix sum in disguise. Instead of sums, you compute prefix products from the left and suffix products from the right. For each index, the answer is leftProduct[i] * rightProduct[i]. No division needed.

Find Pivot Index (#724) asks you to find an index where the sum to the left equals the sum to the right. With a prefix sum, you can check this condition for every index in O(1), making the overall solution O(n).

The prefix sum + hash map combination is the most powerful variant of this pattern, and it deserves special attention. While the basic prefix sum array answers range queries, the hash map version answers a fundamentally different question: how many subarrays have a sum equal to a target?

The idea is elegant. As you iterate through the array, you maintain a running cumulative sum. At each position, you ask: is there a previous prefix sum such that currentSum - previousSum = target? Rearranging, you check whether (currentSum - target) exists in the hash map. If the map says that prefix sum value has occurred 3 times before, then there are 3 subarrays ending at the current index that sum to the target.

The hash map must be initialized with {0: 1} before you start iterating. This accounts for subarrays that start at index 0. Forgetting this initialization is the single most common bug in prefix sum + hash map problems, and it causes incorrect counts that are maddeningly hard to debug.

This pattern runs in O(n) time and O(n) space. It is a massive improvement over the O(n^2) brute force of checking every subarray. Once you recognize a problem is asking about subarray sums equaling a target, reach for this combo immediately.

Prefix sum is conceptually simple, but the implementation has several traps that catch even experienced programmers. Here are the mistakes you are most likely to make and how to avoid them.

The number one mistake is forgetting to initialize prefix[0] = 0 in the array version, or forgetting to seed the hash map with {0: 1} in the hash map version. Without this, any subarray that starts from the very beginning of the array will be missed. Always set this up before your main loop.

Off-by-one errors are the second most common issue. Remember that prefix[i] represents the sum of the first i elements, not the sum including element i. When querying the sum of nums[left..right], the formula is prefix[right+1] - prefix[left], not prefix[right] - prefix[left-1]. Getting this wrong shifts your window by one position.

Another common mistake is confusing prefix sum with sliding window. They solve different problems. Sliding window works when you need a contiguous subarray of a specific length or when all values are positive and you can shrink the window. Prefix sum works for any subarray sum query, including negative numbers. If the array contains negative values, sliding window breaks — use prefix sum instead.

Start with Range Sum Query - Immutable (#303). It is the simplest prefix sum problem and teaches you the mechanics of building and querying the prefix array without any extra complications. Solve it until you can write the code from memory.

Next, move to Subarray Sum Equals K (#560). This is the most interview-relevant prefix sum problem and introduces the hash map variant. Take time to understand why the hash map must be initialized with {0: 1} — draw out a small example by hand if needed.

After those two, work through Find Pivot Index (#724), Product of Array Except Self (#238), and Continuous Subarray Sum (#523) in any order. Each one shows a different twist on the core pattern.

Once you can solve all five problems confidently, review them with YeetCode flashcards. The prefix sum pattern is simple enough that you might think you will remember it forever, but the index offset details and hash map initialization are exactly the kind of things that fade after a week. Spaced repetition keeps the pattern sharp so you can deploy it instantly in an interview.