Prefix Sum pattern: LeetCode problems and interview guide

The Prefix Sum pattern is one of the array techniques for solving LeetCode problems involving subarray sums, range queries, cumulative values, and counting subarrays.

The basic idea is simple: instead of calculating the sum of the same elements repeatedly, we calculate cumulative sums once and reuse them.

This can reduce repeated range-sum operations from O(n) to O(1) and often turns an O(n2) solution into an O(n) solution.

In this guide, I will cover how Prefix Sum pattern works, how to recognize Prefix Sum problems, the most important variations of the pattern, and the LeetCode problems you should practice before a coding interview.

What is Prefix Sum pattern?

Let's start from the beginning and consider the question: What is the Prefix Sum pattern?

Suppose we have the following array:
int nums = [2, 4, 1, 3, 5]
If we need the sum of elements from index 1 to index 3, we could calculate:
4 + 1 + 3 = 8

This is fine for one query. But if we have hundreds or thousands of range queries, repeatedly iterating over the array becomes inefficient. Prefix Sum pattern solves this by preprocessing the array.

We create:

int nums = [2, 4, 1, 3, 5]

prefix = [0, 2, 6, 7, 10, 15]

Here:

prefix[0] = 0
prefix[1] = 2
prefix[2] = 2 + 4 = 6
prefix[3] = 2 + 4 + 1 = 7
prefix[4] = 2 + 4 + 1 + 3 = 10
prefix[5] = 2 + 4 + 1 + 3 + 5 = 15

In other words, prefix[i] stores the sum of the first i elements.

How to build a Prefix Sum array

Let's consider common C++ implementation:

vector<long long> prefix(nums.size() + 1);

for (int i = 0; i < nums.size(); i++)
{
    prefix[i + 1] = prefix[i] + nums[i];
}

Notice that the prefix array contains one extra element:

nums.size() = n
prefix.size() = n + 1

The first element is:

prefix[0] = 0;

This initial zero is not part of the original array. It makes range calculations easier and eliminates the need to handle ranges starting at index 0 separately.

Prefix Sum formula

Once the prefix array has been constructed, the sum of the range [left, right] can be calculated using:
prefix[right + 1] - prefix[left]

For example:

nums = [2, 4, 1, 3, 5]

We want left = 1 and right = 3. Here the elements are [4, 1, 3].

Using Prefix Sum pattern: prefix[4] - prefix[1] = 10 - 2 = 8.

How to recognize the Prefix Sum pattern

Key point is: how to recognize the Prefix Sum Pattern during coding interview?

You should think about Prefix Sum pattern when a problem asks about continuous ranges of an array and repeatedly uses information accumulated from previous elements.

Common signals include:

• Find the sum of a subarray.
• Answer multiple range sum queries.
• Find the number of subarrays with sum K.
• Find a subarray whose sum is divisible by K.
• Compare the sum on the left and right sides of an index.
• Find subarrays containing an equal number of certain values.
• Calculate cumulative frequencies or counts over ranges.

Prefix Sum complexity

Consider it step by step:

• Building the prefix array requires:

  • Time: O(n)
  • Space: O(n)

• After preprocessing, each range sum query takes:

  • Time: O(1)

• Therefore, for q range queries:

  • Without Prefix Sum: O(n * q)
  • With Prefix Sum: O(n + q)

This is why Prefix Sum puttern is useful when the problem contains many range queries.

Important Prefix Sum LeetCode problems

To prepare for a coding interview, you can use these LeetCode problems to practice the Prefix Sum pattern:

303. Range Sum Query - Immutable
304. Range Sum Query 2D - Immutable
525. Contiguous Array
523. Continuous Subarray Sum
560. Subarray Sum Equals K
974. Subarray Sums Divisible by K
1314. Matrix Block Sum