Prefix Sum Pattern | CodeTutor

Prefix Sum

Easy

23 questions using this pattern

What is Prefix Sum?

Precompute cumulative sums to answer range sum queries in O(1) time. This transforms repeated O(n) range calculations into O(n) preprocessing plus O(1) per query, making it essential for problems involving subarray sums.

Think of it like this...

Imagine tracking your total running distance over a year. Instead of adding up daily distances each time someone asks "how far did you run from day 50 to day 75?", you keep a running total. The cumulative distance on day 75 minus day 49 instantly gives you the answer.

Another analogy: a bank account balance. To find how much you spent between two dates, you subtract the earlier balance from the later balance—no need to sum individual transactions.

Core Concept

A prefix sum array stores cumulative sums where prefix[i] = sum of all elements from index 0 to i-1. This enables O(1) range sum queries:

sum(i, j) = prefix[j+1] - prefix[i]

The key insight is that any range sum can be computed from two prefix sums. Instead of iterating through the range (O(n) per query), we do O(n) preprocessing once and answer unlimited queries in O(1) each.

This pattern extends to:

Prefix products: For multiplication-based problems
Prefix counts: For counting occurrences
2D prefix sums: For matrix region queries
Prefix sum + hash map: For "subarray sum equals K"

Prefix Sum - Range Query

Prefix Sum

def build_prefix(nums: list[int]) -> list[int]:

    prefix = [0]

    for num in nums:

        prefix.append(prefix[-1] + num)

    return prefix

def range_sum(prefix: list[int], i: int, j: int) -> int:

    return prefix[j + 1] - prefix[i]

Variables

No variables yet

Original Array

Problem

We have an array [3, 1, 4, 1, 5, 9] and need to efficiently answer range sum queries like "sum from index 1 to 4".

1/21

Visual Walkthrough

Building prefix sum array:

Array:      [3,  1,  4,  1,  5,  9]
Index:       0   1   2   3   4   5

prefix[0] = 0                      (empty prefix)
prefix[1] = 0 + 3 = 3              (sum of first 1 element)
prefix[2] = 3 + 1 = 4              (sum of first 2 elements)
prefix[3] = 4 + 4 = 8
prefix[4] = 8 + 1 = 9
prefix[5] = 9 + 5 = 14
prefix[6] = 14 + 9 = 23

Prefix:    [0,  3,  4,  8,  9, 14, 23]
Index:      0   1   2   3   4   5   6

Range sum query: sum(2, 4) = elements at indices 2, 3, 4

sum(2, 4) = prefix[5] - prefix[2]
          = 14 - 4
          = 10

Verification: arr[2] + arr[3] + arr[4] = 4 + 1 + 5 = 10 ✓

Subarray sum equals K using hash map:

Array: [1, 2, 3, -2, 5]  K = 4

As we iterate, track prefix sums and look for prefix_sum - K:

i=0: prefix=1, need 1-4=-3, not found
i=1: prefix=3, need 3-4=-1, not found
i=2: prefix=6, need 6-4=2, not found
i=3: prefix=4, need 4-4=0, found! (empty prefix)
      → subarray [0:4] sums to 4
i=4: prefix=9, need 9-4=5, not found

Wait, also: prefix at i=1 is 3, at i=4 is 9-4=5... let me recalculate
Actually arr[1:3] = 2+3-2=3, arr[2:4]=3-2+5=6... checking for K=4:
subarray [0:4] → 1+2+3-2=4 ✓

Code Template

Use this skeleton as a starting point for problems using this pattern:

python

def build_prefix_sum(arr: list[int]) -> list[int]:
    """Build prefix sum array. prefix[i] = sum of arr[0:i]."""
    prefix = [0] * (len(arr) + 1)
    for i in range(len(arr)):
        prefix[i + 1] = prefix[i] + arr[i]
    return prefix


def range_sum(prefix: list[int], i: int, j: int) -> int:
    """Sum of elements from index i to j (inclusive)."""
    return prefix[j + 1] - prefix[i]


def subarray_sum_equals_k(nums: list[int], k: int) -> int:
    """Count subarrays with sum equal to k."""
    count = 0
    prefix_sum = 0
    # Map: prefix_sum -> count of occurrences
    sum_count = {0: 1}  # Empty prefix has sum 0

    for num in nums:
        prefix_sum += num

        # If (prefix_sum - k) exists, those prefixes form valid subarrays
        if prefix_sum - k in sum_count:
            count += sum_count[prefix_sum - k]

        # Record current prefix sum
        sum_count[prefix_sum] = sum_count.get(prefix_sum, 0) + 1

    return count


def product_except_self(nums: list[int]) -> list[int]:
    """Product of array except self without division."""
    n = len(nums)
    result = [1] * n

    # Prefix products (left to right)
    prefix = 1
    for i in range(n):
        result[i] = prefix
        prefix *= nums[i]

    # Suffix products (right to left)
    suffix = 1
    for i in range(n - 1, -1, -1):
        result[i] *= suffix
        suffix *= nums[i]

    return result


def matrix_region_sum(matrix: list[list[int]],
                      row1: int, col1: int,
                      row2: int, col2: int) -> int:
    """2D prefix sum for matrix region queries."""
    # Build 2D prefix sum
    m, n = len(matrix), len(matrix[0])
    prefix = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            prefix[i][j] = (matrix[i-1][j-1]
                            + prefix[i-1][j]
                            + prefix[i][j-1]
                            - prefix[i-1][j-1])

    # Query region sum using inclusion-exclusion
    return (prefix[row2+1][col2+1]
            - prefix[row1][col2+1]
            - prefix[row2+1][col1]
            + prefix[row1][col1])

Recognition Signals

Look for these keywords and patterns in problem descriptions:

range sumsubarray sumcumulativesum equals kcount subarraysproduct except selfmatrix region sumrunning totalcontinuous subarray

When to Use

Range sum queries
Subarray sum equals target
Count subarrays with given sum
Product of array except self
2D matrix region sums

Common Mistakes

Off-by-one in prefix array indexing

Confusion about whether prefix[i] includes arr[i] or not leads to incorrect range sums.

Fix:

Convention: prefix[i] = sum of first i elements = arr[0:i]. So prefix[0] = 0 (empty), and range sum is prefix[j+1] - prefix[i].

Forgetting the empty prefix for "sum equals K"

Not initializing the hash map with {0: 1} misses subarrays starting from index 0.

Fix:

Always initialize: sum_count = {0: 1}. This handles the case where the subarray from the beginning has sum K.

Integer overflow with large sums

Pattern Variations

Basic prefix sum

Precompute cumulative sums for O(1) range queries. Foundation for other variations.

Examples: Range Sum Query - Immutable, Running Sum of 1d Array

Prefix sum with hash map

Track prefix sums in a hash map to find subarrays summing to a target. Key insight: prefix[j] - prefix[i] = target means subarray [i,j] works.

Examples: Subarray Sum Equals K, Contiguous Array

Prefix product

Same idea but with multiplication. Watch for zeros and consider using left/right products separately.

Examples: Product of Array Except Self

2D prefix sum

Extend to matrices for O(1) region sum queries. Uses inclusion-exclusion principle.

Examples: Range Sum Query 2D, Matrix Block Sum

Difference array

Inverse of prefix sum. Store differences to support O(1) range updates. Prefix sum of difference array gives original.

Examples: Range Addition, Corporate Flight Bookings

Learning Path

1Warmup0/9

Start here to build foundational understanding.

Average Value of Even Numbers That Are Divisible by ThreeOptimal

#2455Easy

Binary Prefix Divisible By 5Optimal

#1018Easy

Calculate Money in Leetcode BankOptimal

#1716Easy

Cells with Odd Values in a MatrixOptimal

#1252Easy

Check if All Characters Have Equal Number of OccurrencesOptimal

#1941Easy

Check if All the Integers in a Range Are CoveredOptimal

#1893Easy

Check if Number Has Equal Digit Count and Digit ValueOptimal

#2283Easy

Check if the Sentence Is PangramOptimal

#1832Easy

Missing NumberOptimal

#268Easy

2Core Practice0/12

Master the pattern with these representative problems.

All Divisions With the Highest Score of a Binary ArrayOptimal

#2155Medium

Binary Subarrays With Sum

#930Medium

Brick WallOptimal

#554Medium

Can You Eat Your Favorite Candy on Your Favorite Day?Optimal

#1744Medium

Car PoolingOptimal

#1094Medium

Change Minimum Characters to Satisfy One of Three ConditionsOptimal

#1737Medium

Check If Array Pairs Are Divisible by kOptimal

#1497Medium

Continuous Subarray SumOptimal

#523Medium

Minimum Size Subarray Sum

#209Medium

Product of Array Except SelfOptimal

#238Medium

Stone Game IIOptimal

#1140Medium

Subarray Sum Equals KOptimal

#560Medium

3Challenge0/2

Test your mastery with complex variations.

Build Array Where You Can Find The Maximum Exactly K ComparisonsOptimal

#1420Hard

Maximum Fruits Harvested After at Most K Steps

#2106Hard

Related Patterns

Explore similar techniques:

Two Pointers

Use two pointers to traverse data from different positions, often moving toward or away from each other. This technique transforms O(n²) brute force into O(n) by eliminating redundant comparisons.

Sliding Window

Maintain a window of elements that slides through the data, tracking a constraint or computing aggregates. This transforms O(n*k) brute force into O(n) by incrementally updating the window instead of recalculating from scratch.