Skip to main content
Prefix Sum Pattern

​
What is Prefix Sum?

Prefix Sum (cumulative sum) is a preprocessing technique that stores running totals, enabling O(1) range sum queries after O(n) preprocessing.
Quick Recognition: Problems involving range sums, subarray sums with target, or cumulative calculations. Keywords: “sum of range”, “subarray sum equals k”, “cumulative”.

​
Pattern Recognition Checklist

Use Prefix Sum When

  • Multiple range sum queries
  • Finding subarray with specific sum
  • Equilibrium/pivot index problems
  • 2D matrix region sums
  • Running totals with modifications

Don't Use When

  • Single range query (just iterate)
  • Array values change frequently (use Segment Tree)
  • Need min/max in range (use Segment Tree)
  • Need product (use prefix product)

​
When to Use

Range Sum Queries

Sum of elements in any range

Subarray Sum Problems

Find subarrays with specific sum

Equilibrium Index

Where left sum equals right sum

2D Range Sum

Sum in rectangular region

​
Core Concept

# Original array:  [1, 2, 3, 4, 5]
# Prefix sum:      [0, 1, 3, 6, 10, 15]
#                   ^ Extra 0 at start for easier indexing

# Sum of range [i, j] = prefix[j+1] - prefix[i]
# Example: sum[1:3] = prefix[4] - prefix[1] = 10 - 1 = 9

def build_prefix_sum(arr):
    prefix = [0]
    for num in arr:
        prefix.append(prefix[-1] + num)
    return prefix

def range_sum(prefix, i, j):
    """Sum of arr[i:j+1] in O(1)"""
    return prefix[j + 1] - prefix[i]

​
Pattern Variations

​
1. Basic Range Sum

class NumArray:
    """Range sum query - immutable array"""
    
    def __init__(self, nums):
        self.prefix = [0]
        for num in nums:
            self.prefix.append(self.prefix[-1] + num)
    
    def sumRange(self, left, right):
        return self.prefix[right + 1] - self.prefix[left]

​
2. Subarray Sum Equals K

def subarray_sum(nums, k):
    """Count subarrays with sum exactly k"""
    count = 0
    prefix_sum = 0
    prefix_count = {0: 1}  # sum to frequency
    
    for num in nums:
        prefix_sum += num
        
        # If (prefix_sum - k) exists, we found subarrays
        if prefix_sum - k in prefix_count:
            count += prefix_count[prefix_sum - k]
        
        prefix_count[prefix_sum] = prefix_count.get(prefix_sum, 0) + 1
    
    return count

​
3. Product of Array Except Self

def product_except_self(nums):
    """Without division, O(1) extra space (excluding output)"""
    n = len(nums)
    result = [1] * n
    
    # Left products
    left_product = 1
    for i in range(n):
        result[i] = left_product
        left_product *= nums[i]
    
    # Right products
    right_product = 1
    for i in range(n - 1, -1, -1):
        result[i] *= right_product
        right_product *= nums[i]
    
    return result

​
4. 2D Prefix Sum (Matrix Region Sum)

class NumMatrix:
    """2D range sum query"""
    
    def __init__(self, matrix):
        if not matrix:
            return
        
        m, n = len(matrix), len(matrix[0])
        self.prefix = [[0] * (n + 1) for _ in range(m + 1)]
        
        for i in range(m):
            for j in range(n):
                self.prefix[i+1][j+1] = (matrix[i][j] 
                    + self.prefix[i][j+1] 
                    + self.prefix[i+1][j] 
                    - self.prefix[i][j])
    
    def sumRegion(self, r1, c1, r2, c2):
        return (self.prefix[r2+1][c2+1] 
            - self.prefix[r1][c2+1] 
            - self.prefix[r2+1][c1] 
            + self.prefix[r1][c1])

​
Classic Problems

ProblemTechniqueKey Insight
Range Sum QueryBasic prefixprefix[j+1] - prefix[i]
Subarray Sum KHashMap + PrefixCount prefix_sum - k
Contiguous ArrayTransform 0 to -1Find equal 0s and 1s
2D Region Sum2D prefixInclusion-exclusion
Product Except SelfLeft/Right prefixMultiply both directions

​
Interview Problems by Company

ProblemCompanyKey Concept
Range Sum QueryAllBasic prefix sum
Running SumAmazonSimple cumulative
Pivot IndexMetaLeft = Right sum

​
Interview Tips

Range sum [i, j] = prefix[j+1] - prefix[i]Why j+1? Because prefix[k] = sum of first k elements (0 to k-1).So prefix[j+1] = sum of elements 0 to j And prefix[i] = sum of elements 0 to i-1Difference = sum of elements i to j
For “count subarrays with sum = k”:
def subarray_sum_k(nums, k):
    prefix_count = {0: 1}  # Empty subarray has sum 0
    prefix_sum = 0
    count = 0
    
    for num in nums:
        prefix_sum += num
        # If (prefix_sum - k) exists, we found subarrays
        count += prefix_count.get(prefix_sum - k, 0)
        prefix_count[prefix_sum] = prefix_count.get(prefix_sum, 0) + 1
    
    return count
Build: prefix[i+1][j+1] = matrix[i][j] + prefix[i][j+1] + prefix[i+1][j] - prefix[i][j]Query: sum(r1,c1 to r2,c2) = prefix[r2+1][c2+1] - prefix[r1][c2+1] - prefix[r2+1][c1] + prefix[r1][c1]

​
Practice Problems

Range Sum Query

Basic prefix sum

Subarray Sum K

HashMap with prefix

Contiguous Array

Transform and prefix

2D Range Sum

2D prefix sum

​
Practice Roadmap

1

Day 1: Basic Prefix Sum

  • Solve: Range Sum Query, Running Sum
  • Focus: Building and querying prefix array
2

Day 2: HashMap + Prefix

  • Solve: Subarray Sum = K, Contiguous Array
  • Focus: Tracking prefix counts
3

Day 3: 2D Prefix Sum

  • Solve: 2D Range Sum Query
  • Focus: Inclusion-exclusion principle
4

Day 4: Variations

  • Solve: Product Except Self, Maximum Subarray
  • Focus: Prefix products, Kadane’s
Interview Tip: When you see “sum of subarray” or “range sum query”, think Prefix Sum. Add HashMap when counting subarrays with specific sum.