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]

// 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

public class PrefixSum {
    public int[] buildPrefixSum(int[] arr) {
        int[] prefix = new int[arr.length + 1];
        for (int i = 0; i < arr.length; i++) {
            prefix[i + 1] = prefix[i] + arr[i];
        }
        return prefix;
    }
    
    public int rangeSum(int[] prefix, int i, int j) {
        // Sum of arr[i:j+1] in O(1)
        return prefix[j + 1] - prefix[i];
    }
}

// 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

class PrefixSum {
public:
    vector<int> buildPrefixSum(vector<int>& arr) {
        vector<int> prefix(arr.size() + 1, 0);
        for (int i = 0; i < arr.size(); i++) {
            prefix[i + 1] = prefix[i] + arr[i];
        }
        return prefix;
    }
    
    int rangeSum(vector<int>& prefix, int i, int 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]

class NumArray {
    // Range sum query - immutable array
    private int[] prefix;
    
    public NumArray(int[] nums) {
        prefix = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
    }
    
    public int sumRange(int left, int right) {
        return prefix[right + 1] - prefix[left];
    }
}

class NumArray {
    // Range sum query - immutable array
private:
    vector<int> prefix;
    
public:
    NumArray(vector<int>& nums) {
        prefix.resize(nums.size() + 1, 0);
        for (int i = 0; i < nums.size(); i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
    }
    
    int sumRange(int left, int right) {
        return prefix[right + 1] - 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

public int subarraySum(int[] nums, int k) {
    // Count subarrays with sum exactly k
    int count = 0;
    int prefixSum = 0;
    Map<Integer, Integer> prefixCount = new HashMap<>();
    prefixCount.put(0, 1); // sum to frequency
    
    for (int num : nums) {
        prefixSum += num;
        
        // If (prefixSum - k) exists, we found subarrays
        if (prefixCount.containsKey(prefixSum - k)) {
            count += prefixCount.get(prefixSum - k);
        }
        
        prefixCount.put(prefixSum, 
            prefixCount.getOrDefault(prefixSum, 0) + 1);
    }
    
    return count;
}

int subarraySum(vector<int>& nums, int k) {
    // Count subarrays with sum exactly k
    int count = 0;
    int prefixSum = 0;
    unordered_map<int, int> prefixCount;
    prefixCount[0] = 1; // sum to frequency
    
    for (int num : nums) {
        prefixSum += num;
        
        // If (prefixSum - k) exists, we found subarrays
        if (prefixCount.find(prefixSum - k) != prefixCount.end()) {
            count += prefixCount[prefixSum - k];
        }
        
        prefixCount[prefixSum]++;
    }
    
    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

public int[] productExceptSelf(int[] nums) {
    // Without division, O(1) extra space (excluding output)
    int n = nums.length;
    int[] result = new int[n];
    Arrays.fill(result, 1);
    
    // Left products
    int leftProduct = 1;
    for (int i = 0; i < n; i++) {
        result[i] = leftProduct;
        leftProduct *= nums[i];
    }
    
    // Right products
    int rightProduct = 1;
    for (int i = n - 1; i >= 0; i--) {
        result[i] *= rightProduct;
        rightProduct *= nums[i];
    }
    
    return result;
}

vector<int> productExceptSelf(vector<int>& nums) {
    // Without division, O(1) extra space (excluding output)
    int n = nums.size();
    vector<int> result(n, 1);
    
    // Left products
    int leftProduct = 1;
    for (int i = 0; i < n; i++) {
        result[i] = leftProduct;
        leftProduct *= nums[i];
    }
    
    // Right products
    int rightProduct = 1;
    for (int i = n - 1; i >= 0; i--) {
        result[i] *= rightProduct;
        rightProduct *= 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])

class NumMatrix {
    // 2D range sum query
    private int[][] prefix;
    
    public NumMatrix(int[][] matrix) {
        if (matrix.length == 0) return;
        
        int m = matrix.length, n = matrix[0].length;
        prefix = new int[m + 1][n + 1];
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                prefix[i+1][j+1] = matrix[i][j] 
                    + prefix[i][j+1] 
                    + prefix[i+1][j] 
                    - prefix[i][j];
            }
        }
    }
    
    public int sumRegion(int r1, int c1, int r2, int c2) {
        return prefix[r2+1][c2+1] 
            - prefix[r1][c2+1] 
            - prefix[r2+1][c1] 
            + prefix[r1][c1];
    }
}

class NumMatrix {
    // 2D range sum query
private:
    vector<vector<int>> prefix;
    
public:
    NumMatrix(vector<vector<int>>& matrix) {
        if (matrix.empty()) return;
        
        int m = matrix.size(), n = matrix[0].size();
        prefix.assign(m + 1, vector<int>(n + 1, 0));
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                prefix[i+1][j+1] = matrix[i][j] 
                    + prefix[i][j+1] 
                    + prefix[i+1][j] 
                    - prefix[i][j];
            }
        }
    }
    
    int sumRegion(int r1, int c1, int r2, int c2) {
        return prefix[r2+1][c2+1] 
            - prefix[r1][c2+1] 
            - prefix[r2+1][c1] 
            + prefix[r1][c1];
    }
};

Classic Problems

Problem	Technique	Key Insight
Range Sum Query	Basic prefix	prefix[j+1] - prefix[i]
Subarray Sum K	HashMap + Prefix	Count prefix_sum - k
Contiguous Array	Transform 0 to -1	Find equal 0s and 1s
2D Region Sum	2D prefix	Inclusion-exclusion
Product Except Self	Left/Right prefix	Multiply both directions

Interview Problems by Company

Easy
Medium

Problem	Company	Key Concept
Range Sum Query	All	Basic prefix sum
Running Sum	Amazon	Simple cumulative
Pivot Index	Meta	Left = Right sum

Problem	Company	Key Concept
Subarray Sum = K	Meta, Google	HashMap + prefix
Contiguous Array	Meta, Amazon	0 to -1 transform
Product Except Self	All FAANG	Left/right prefix
2D Range Sum	Google	2D prefix grid

Interview Tips

The Key Formula

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

HashMap + Prefix Pattern

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

2D Prefix Sum Formula

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

Day 1: Basic Prefix Sum

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

Day 2: HashMap + Prefix

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

Day 3: 2D Prefix Sum

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

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.

Overview

Array & String

Search & Sort

Data Structures

Graph & Tree

Advanced Techniques

What is Prefix Sum?

Pattern Recognition Checklist

Use Prefix Sum When

Don't Use When

When to Use

Range Sum Queries

Subarray Sum Problems

Equilibrium Index

2D Range Sum

Core Concept

Pattern Variations

1. Basic Range Sum

2. Subarray Sum Equals K

3. Product of Array Except Self

4. 2D Prefix Sum (Matrix Region Sum)

Classic Problems

Interview Problems by Company

Interview Tips

Practice Problems

Range Sum Query

Subarray Sum K

Contiguous Array

2D Range Sum

Practice Roadmap

​What is Prefix Sum?

​Pattern Recognition Checklist

Use Prefix Sum When

Don't Use When

​When to Use

Range Sum Queries

Subarray Sum Problems

Equilibrium Index

2D Range Sum

​Core Concept

​Pattern Variations

​1. Basic Range Sum

​2. Subarray Sum Equals K

​3. Product of Array Except Self

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

​Classic Problems

​Interview Problems by Company

​Interview Tips

​Practice Problems

Range Sum Query

Subarray Sum K

Contiguous Array

2D Range Sum

​Practice Roadmap

What is Prefix Sum?

Pattern Recognition Checklist

When to Use

Core Concept

Pattern Variations

1. Basic Range Sum

2. Subarray Sum Equals K

3. Product of Array Except Self

4. 2D Prefix Sum (Matrix Region Sum)

Classic Problems

Interview Problems by Company

Interview Tips

Practice Problems

Practice Roadmap