What is the Prefix Sum pattern?

The Prefix Sum pattern is a systematic approach to solving a class of coding interview problems. By recognizing the Prefix Sum structure, you can solve problems in optimal time complexity using proven techniques.

When should I use the Prefix Sum pattern?

Use the Prefix Sum pattern when the problem structure matches its recognition signals — typically when brute force would be O(n²) or worse, and the pattern reduces complexity to O(n) preprocessing, O(1) per query.

What is the time complexity of Prefix Sum?

The Prefix Sum pattern typically runs in O(n) preprocessing, O(1) per query time and uses O(n) space. The exact complexity depends on the specific sub-variant being applied.

Is Prefix Sum important for coding interviews?

Yes — the Prefix Sum pattern is frequently tested at FAANG companies and competitive engineering interviews. Mastering this pattern gives you a reliable framework to solve many problem variations quickly.

How do I practice the Prefix Sum pattern?

Start by studying the pattern's mental model and recognition signals on DSAPatterns, then practice the curated LeetCode problems below in order from Easy to Hard. Aim for pattern recognition before memorizing solutions.

← back to patterns

pattern / EASY

Prefix Sum.

Precompute cumulative sums for range queries

complexity

time

O(n) preprocessing, O(1) per query

space

O(n)

practice questions

browse and solve all 5 pattern questions →

02' — visual

interactive

Sliding window — k = 3

Maximum sum subarray

Window

[0, 2]

Sum

Step

0 / 3

03'

mental
model.

Build an array prefix[] where prefix[i] = sum of all elements from index 0 to i. Then any range sum [l, r] = prefix[r] - prefix[l-1].

Prefix Sum technique precomputes cumulative sums to answer range sum queries in O(1) time. Often combined with a HashMap for subarray sum problems.

when to use ✓

01Range sum queries on static array
02Subarray sum equals K
03Number of subarrays with sum divisible by K
042D range sum queries

when not ✗

01Array has frequent updates (use BIT or segment tree)
02When element-wise operations are needed

04'

recognition signals

Multiple range sum queries

Find subarray with given sum

Subarray sum equals K

Range updates or queries

1D prefix sum2D prefix sum (matrix)Prefix XORPrefix product

05'

templates

</>Beginner Template

1# Beginner: Fixed-size sliding window
2def max_sum_k(nums, k):
3    n = len(nums)
4    if n < k:
5        return 0
6    window_sum = sum(nums[:k])
7    max_sum = window_sum
8    for i in range(k, n):
9        window_sum += nums[i] - nums[i - k]
10        max_sum = max(max_sum, window_sum)
11    return max_sum