Master DSA Pattern: Prefix Sum

The Prefix Sum pattern is a fundamental algorithmic technique used to perform fast range sum queries and evaluate contiguous subarray properties. By pre-computing cumulative sums from the beginning of an array up to each index, complex range calculations that would normally require $O(N)$ traversal can be answered in $O(1)$ constant time.

1. What is the Prefix Sum Pattern?

A Prefix Sum Array is a auxiliary data structure where each element at index i stores the total sum of all elements from the start of the original array up to index i.

Given an array $\text{arr}$ of size $N$, the prefix sum at index $i$ is mathematically defined as:

Conceptual Visual Breakdown

Original Array:
Index:     0    1    2    3    4    5
Value:   [ 1,   2,   3,   4,   5,   6 ]

Prefix Sum Array:
Index:     0    1    2    3    4    5
Value:   [ 1,   3,   6,  10,  15,  21 ]
           |    |    |    |    |    |
           1    1+2  1+2+3 ...      1+2+3+4+5+6

2. Core Mental Model & Range Sum Formula

Real-Life Analogy

Highway Mileage Markers: Imagine driving along a straight highway with mile markers measuring distance from the start point (City A).

• Mile marker at Exit 1 = 10 miles
• Mile marker at Exit 2 = 35 miles
• Mile marker at Exit 3 = 80 miles

To find the exact distance between Exit 1 and Exit 3, you do not need to re-measure the road segment by segment. You simply subtract the cumulative distance at Exit 1 from the cumulative distance at Exit 3:

Range Sum Derivation

To compute the sum of elements in a contiguous subarray from index $i$ to index $j$ (where $i \le j$):

• Without Prefix Sum: Loop from index $i$ to $j$ and accumulate the values $\rightarrow O(N)$ time per query.
• With Prefix Sum: Subtract the unwanted prefix before index $i$ from the total prefix up to index $j$ $\rightarrow O(1)$ time per query.

Visual Subtraction Flow

3. Standard Computation: Step-by-Step Evolution

Building a prefix sum array is a simple iterative process that runs in $O(N)$ time.

Naive Iterative Calculation vs. In-Place Dynamic Accumulation

Prefix Sum Building Implementation (Java)

public class PrefixSum {
    public static int[] buildPrefixSum(int[] nums) {
        int n = nums.length;
        int[] prefix = new int[n];
        
        // Base case: first element remains identical
        prefix[0] = nums[0];
        
        // Accumulate running sum sequentially
        for (int i = 1; i < n; i++) {
            prefix[i] = prefix[i - 1] + nums[i];
        }
        
        return prefix;
    }
}

4. How to Identify Prefix Sum Problems

Look for the following signals and keywords in problem descriptions:

1. Subarray Range Calculations: Questions asking for the sum, average, or evaluation of elements within contiguous boundaries $[i \dots j]$.
2. Repeated Query Scenarios: Requirements to process multiple range sum requests on a fixed initial array without modifying it.
3. Subarray Target Conditions: Finding contiguous subarrays that satisfy a specific sum $K$ or divisible conditions ($(\text{sum}) \pmod K == 0$).
4. Presence of Negative Numbers: When window bounds cannot be expanded/contracted monotonically (which breaks standard Two-Pointer or Sliding Window techniques), Prefix Sum combined with a HashMap is often required.

Complexity Comparison Matrix

5. Problem 1: Find Pivot Index (LeetCode 724 / 1991)

Problem Statement

Given an array of integers nums, calculate the pivot index of this array. The pivot index is the index where the sum of all the numbers strictly to the left of the index is equal to the sum of all the numbers strictly to the right of the index. If no such index exists, return -1. If there are multiple pivot indices, return the leftmost pivot index.

Structural Flow Analysis

Approach Evolution

1 . Naive Approach ($O(N^2)$ Time): Iterate through each index $i$. For each $i$, run two separate nested loops: one to sum elements from $0$ to $i-1$, and another to sum elements from $i+1$ to $N-1$. Compare the sums.

2. Optimized Prefix Sum Approach ($O(N)$ Time, $O(1)$ Space):
   • Pre-calculate the totalSum of the entire array in a single pass.
   • Maintain a running leftSum starting at 0.
   • At any index $i$, the right sum can be derived dynamically:

• Check if $\text{leftSum} == \text{rightSum}$. If yes, return current index $i$.
• Otherwise, update $\text{leftSum} += \text{nums}[i]$.

Walkthrough / Dry-Run (nums = [1, 7, 3, 6, 5, 6])

$\text{totalSum} = 1 + 7 + 3 + 6 + 5 + 6 = 28$

Optimized Java Implementation

class Solution {
    public int pivotIndex(int[] nums) {
        int totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }

        int leftSum = 0;
        for (int i = 0; i < nums.length; i++) {
            // Right sum calculated in O(1) space
            int rightSum = totalSum - leftSum - nums[i];

            if (leftSum == rightSum) {
                return i; // Leftmost pivot found
            }

            leftSum += nums[i];
        }

        return -1; // No valid pivot index
    }
}

• Time Complexity: $O(N)$ — Two sequential passes through the array.
• Space Complexity: $O(1)$ — Only auxiliary variables (totalSum, leftSum, rightSum) used.

6. Problem 2: Subarray Sum Equals K (LeetCode 560)

Problem Statement

Given an array of integers nums and an integer k, return the total number of contiguous subarrays whose sum equals k.

Mathematical Mechanics (Prefix Sum + HashMap)

We know that a contiguous subarray sum from index $i$ to $j$ is given by:

We want to find pairs $(i, j)$ such that:

As we traverse the array, maintaining the running currentSum ($\text{prefix}[j]$), we check if the value $(\text{currentSum} - K)$ has already occurred in our traversal history. A HashMap is used to store:

Critical Edge Case: We must initialize the map with map.put(0, 1). This accounts for valid subarrays starting right at index $0$ where $\text{currentSum} == K$, because $\text{currentSum} - K = 0$.

Walkthrough / Dry-Run (nums = [1, 1, 1], $k = 2$)

Initial State: map = {0: 1}, currentSum = 0, count = 0

Complete Java Implementation

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int subarraySum(int[] nums, int k) {
        // Map to store frequency of encountered prefix sums
        Map<Integer, Integer> map = new HashMap<>();
        
        // Base initialization: prefix sum 0 occurs once
        map.put(0, 1);
        
        int currentSum = 0;
        int count = 0;
        
        for (int num : nums) {
            currentSum += num;
            
            // Check if (currentSum - k) exists in history
            if (map.containsKey(currentSum - k)) {
                count += map.get(currentSum - k);
            }
            
            // Register current prefix sum in map
            map.put(currentSum, map.getOrDefault(currentSum, 0) + 1);
        }
        
        return count;
    }
}

• Time Complexity: $O(N)$ — Single pass traversing $N$ elements; hash table lookups take $O(1)$ on average.
• Space Complexity: $O(N)$ — In the worst case, all prefix sums are distinct, requiring $O(N)$ hashmap entries.

7. Problem 3: Continuous Subarray Sum (LeetCode 523)

Problem Statement

Given an integer array nums and an integer k, return true if nums has a good subarray, or false otherwise.

A good subarray is defined as a contiguous subarray where:

1. Its length is at least two ($\ge 2$).
2. The sum of its elements is a multiple of $k$ (i.e., $\text{subarraySum} \pmod k == 0$).

Mathematical Mechanics (Modulo Arithmetic)

A subarray sum from index $i + 1$ to $j$ is a multiple of $k$ if:

According to modular arithmetic properties, this simplifies directly to:

Core Insight: If we encounter the same remainder at two different indices $i$ and $j$, the sum of elements between $i + 1$ and $j$ MUST be a multiple of $k$.

To ensure the length condition ($\text{length} \ge 2$), we map:

Critical Edge Case: Initialize the hash map with map.put(0, -1). This covers scenarios where a valid prefix starting at index $0$ itself has a remainder of $0$ and a length of $j - (-1) = j + 1 \ge 2$.

Structural Execution Workflow

Walkthrough / Dry-Run (nums = [23, 2, 4, 6, 7], $k = 6$)

Initial State: map = {0: -1}, currentSum = 0

Complete Java Implementation

import java.util.HashMap;
import java.util.Map;

class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        // Map to store: Remainder -> First Seen Index
        Map<Integer, Integer> map = new HashMap<>();
        
        // Base case: remainder 0 at index -1 to handle valid subarrays starting at index 0
        map.put(0, -1);
        
        int currentSum = 0;
        
        for (int i = 0; i < nums.length; i++) {
            currentSum += nums[i];
            
            int remainder = currentSum % k;
            
            // Java modulus adjustment for potential negative numbers (if applicable)
            if (remainder < 0) {
                remainder += k;
            }
            
            if (map.containsKey(remainder)) {
                // Check if length of contiguous subarray is at least 2
                int prevIndex = map.get(remainder);
                if (i - prevIndex >= 2) {
                    return true;
                }
            } else {
                // Only store the FIRST occurrence of a remainder to maximize window length
                map.put(remainder, i);
            }
        }
        
        return false;
    }
}

• Time Complexity: $O(N)$ — Single iteration through nums.
• Space Complexity: $O(\min(N, K))$ — The hashmap stores at most $K$ distinct remainders or $N$ indices.

8. Pattern Variant Matrix

9. Real-World Pitfalls & Debugging Mindset

1. Off-By-One Range Subtractions

• Mistake: Calculating range sum from $i$ to $j$ as prefix[j] - prefix[i].
• Correction: The correct formula is prefix[j] - prefix[i - 1]. Subtracting prefix[i] mistakenly excludes nums[i] from your target range sum.

2. Misapplying Sliding Window to Arrays with Negative Numbers

• Mistake: Trying to use a standard two-pointer/sliding window for target sum problems when array elements contain negative values.
• Why it fails: Sliding window relies on monotonicity (adding elements strictly increases the sum; removing elements strictly decreases it). Negative numbers break this assumption.
• Correction: When negative values exist, always pivot to Prefix Sum + HashMap.

3. Overwriting First-Seen Remainder Indices

• Mistake: Updating the index of an existing remainder in the hashmap during continuous subarray problems.
• Correction: Only record the first time a remainder is seen (map.putIfAbsent logic). Overwriting it contracts the calculated length, potentially missing valid subarrays of length $\ge 2$.

4. Zero and Modulo Edge Cases

• Initialization Failure: Forgetting map.put(0, 1) in exact sum problems or map.put(0, -1) in remainder problems will cause valid subarrays that start at index $0$ to be missed.

10. Summary and Key Takeaways

1. Prefix Sum Purpose: Enables instant $O(1)$ contiguous range sum queries by pre-computing cumulative sums, trading space to reduce time complexity from $O(N^2)$ to $O(N)$.
2. Core Range Formula: The sum of contiguous elements in subarray $[i \dots j]$ is calculated as $\text{prefix}[j] - \text{prefix}[i - 1]$.
3. Space Optimization: Problems like Pivot Index can derive the right sum on the fly ($\text{totalSum} - \text{leftSum} - \text{nums}[i]$), achieving $O(1)$ auxiliary space.
4. HashMap Integration: Combining Prefix Sums with HashMaps converts target search problems ($\text{prefix}[j] - \text{prefix}[i-1] = K$) into instantaneous dynamic hash lookups ($\text{prefix}[j] - K$).
5. Base Case Map Handlers: Always initialize HashMaps with base cases (map.put(0, 1) or map.put(0, -1)) to handle valid target subarrays starting at index $0$.
6. Modulo Subarray Theorem: If $(\text{prefix}[j] \pmod K) == (\text{prefix}[i] \pmod K)$, the contiguous subarray between $i+1$ and $j$ has a sum that is a strict multiple of $K$.
7. First Encounter Retention: In remainder-based distance checks, preserve the earliest recorded index for any given remainder to maximize the potential subarray window length.
8. Pattern Selection Rule: Use Prefix Sum + HashMap over Sliding Window whenever the array includes negative numbers or modulo divisibility rules.