DSA Patterns #1: Prefix Sum

Concept

The prefix sum pattern is a technique that simplifies and speeds up calculations over a range of indices in an array. It involves creating a precomputed array of cumulative sums, allowing for constant time queries over the original array for tasks like range sums or detecting specific patterns.

In a cricket match, the scoreboard operator maintains the cumulative total of runs scored by the batting team after every over. If someone wants to know how many runs were scored between the 6th and 15th overs, the operator subtracts the total after the 5th over from the total after the 15th.

The scoreboard totals act as a “Prefix Sum,” simplifying the calculation of runs for any interval.

Pseudo Code

function buildPrefixSum(arr):
    let n = arr.length
    let prefixSum = new Array(n)
    prefixSum[0] = arr[0]  // Initialize the first value
    
    for i from 1 to n - 1:
        prefixSum[i] = prefixSum[i - 1] + arr[i]  // Accumulate the sum
    
    return prefixSum

The provided pseudo code is a building block. While it handles range sum queries directly, solving advanced problems requires integrating this preprocessing step into a larger framework.

How to adapt this template?

1. Build the Prefix Sum Array:

• Use this to compute cumulative sums for any type of problem.
• Complexity: O(n).

2. Apply Specific Problem Logic:

• Use the prefix sum array to perform constant-time range queries or detect patterns.
• For example:
• Range queries: Subtract prefix sums for two indices.
• Subarray counts: Use a hash map to track the frequency of prefix sums.
• Maximum/minimum subarray calculations: Use the prefix sum for intermediate steps.

3. Additional Logic for Advanced Problems:

• Problems with modular constraints, divisibility, or more complex conditions can integrate the prefix sum array as a preprocessing step.

How to identify?

Certain keywords or problem descriptions signal that the Prefix Sum pattern might be the right approach. Look out for the following clues:

1. Range-based Queries

• Keywords: Range sum, subarray sum, interval sum, between indices
• Problems asking to calculate the sum of elements between two indices repeatedly.
  Example: “Find the sum of elements from the index i to j efficiently.”

2. Cumulative or Running Total

• Keywords: Cumulative, running sum, progressive sum, prefix, suffix
• Tasks involving precomputing totals for efficiency or comparisons.
  Example: “Find the total number of items sold between day x and y.”

3. Subarray Sum Properties

• Keywords: Subarray with a given sum, count of subarrays, sum divisible by k
• Problems involving counting or finding subarrays based on their sum.
  Example: “Count the number of subarrays where the sum is equal to k.”

4. Equilibrium Points

• Keywords: Balanced sum, left equals right, split point, equilibrium index
• Finding indices where the sum of elements on the left equals the sum on the right.
  Example: “Find an index i where the sum of elements to the left equals the sum to the right.”

5. Modular Arithmetic with Sums

• Keywords: Divisible by k, remainder, modulus
• Tasks involving sums that meet modular conditions.
  Example: “Find all subarrays whose sum is divisible by k.”

6. Difference of Sums

• Keywords: Difference in range, change in total, net sum between ranges
• Situations where subtracting one cumulative value from another simplifies computation.
  Example: “Find the difference in sales between two periods.”

Example Problems

Here are some classic problems that can be solved using the Prefix Sum pattern:

• Range sum query - immutable. (Leetcode)
• Subarray sum equals k (Leetcode)