Pattern #7

Prefix Sum

Important interview questions, thinking patterns, range formulas, and rules for solving prefix sum problems in Go.

Must Solve

15 core questions — solve these first.

1.Running Sum of 1d Array
Cumulative sumeasy
2.Find Pivot Index
Total sum - left sumeasy
3.Range Sum Query - Immutable
prefix[R] - prefix[L-1]easy
4.Subarray Sum Equals K
Prefix Sum + Hash Mapmedium
5.Continuous Subarray Sum
Prefix % K mapmedium
6.Contiguous Array
Replace 0 with -1 + Prefixmedium
7.Product of Array Except Self
Prefix & Suffix productmedium
8.Minimum Size Subarray Sum
Prefix + Binary Search / Windowmedium
9.Maximum Size Subarray Sum Equals K
Prefix + Earliest Index Mapmedium
10.Number of Subarrays with Sum K
Prefix freq mapmedium
11.Binary Subarrays With Sum
Prefix sum / AtMost(K)medium
12.Count Number of Nice Subarrays
Odd count prefix mapmedium
13.Subarray Sums Divisible by K
Prefix % K remainder mapmedium
14.Corporate Flight Bookings
Difference Arraymedium
15.Range Addition
Difference Arraymedium

Also Important

7 more questions worth practicing.

16.Left and Right Sum Differences
Prefix / Suffix diffeasy
17.Find the Highest Altitude
Running sum maxeasy
18.Sum of Absolute Differences in a Sorted Array
Prefix sum mathmedium
19.Matrix Block Sum
2D Prefix Summedium
20.Range Sum Query 2D - Immutable
2D Prefix Sum formulamedium
21.Number of Submatrices That Sum to Target
2D Prefix + 1D Maphard
22.Maximum Population Year
Difference Array / Line Sweepeasy

How to Think

Need sum from index L to R many times?Prefix Sum
Need sum of continuous subarray?prefix[r] - prefix[l-1]
Need subarray sum = K?Prefix Sum + Hash Map
Need many range updates?Difference Array
Need 2D rectangle sum?2D Prefix Sum

Go Thinking & Reference

Standard 0-Indexed Prefix Sum

// Build prefix array
prefix := make([]int, len(nums))
prefix[0] = nums[0]
for i := 1; i < len(nums); i++ {
    prefix[i] = prefix[i-1] + nums[i]
}

// Range sum L..R query in O(1)
sum := prefix[r]
if l > 0 {
    sum -= prefix[l-1]
}

👉 Build: O(n) | Query: O(1) | Space: O(n)

1-Indexed Prefix Sum (Avoids L == 0 check)

prefix := make([]int, len(nums)+1)
for i := 0; i < len(nums); i++ {
    prefix[i+1] = prefix[i] + nums[i]
}

// Range sum L..R query in O(1)
sum := prefix[r+1] - prefix[l]

👉 Avoids L == 0 conditional logic

Main Idea & Formulas

Array:  [2, 4, 1, 3, 5]
Prefix: [2, 6, 7, 10, 15]

prefix[i] = sum from 0 to i

Need sum from index 1 to 3 (values: 4 + 1 + 3 = 8):

prefix[3] - prefix[0]  =>  10 - 2 = 8

Visual Memory Rule

Array
[ a   b    c    d   e ]

Prefix
[ a  a+b  a+b+c ... ]

Range L..R  →  prefix[R] - prefix[L-1]
If L == 0   →  answer = prefix[R]

💡 Golden Rule: "Store the work you already did, so you don't calculate the same sum again."

Interview Rules

1. Many range sums? → Prefix Sum
2. Continuous subarray? → Think Prefix
3. Subarray sum = K? → Prefix + Hash Map
4. Need fast repeated queries? → Precompute once
5. Need rectangle sum? → 2D Prefix Sum
6. Need many range updates? → Difference Array
7. Build once → O(n)
8. Range query → O(1)

Small Rules

Rule 1: Build prefix once O(n), then range sum O(1).
Rule 2: Without prefix each query is O(n). With prefix each query is O(1).
Rule 3: Subarray sum = K: If cur - old = K, check if cur - K exists in Hash Map.
Rule 4: Works especially well when same array has many range queries.
Rule 5: Prefix does not mean only sum! Works for counts, XOR, frequency, products.

Production Thinking

Analytics (Daily Orders Range) → Prefix totals for fast dashboard range queries

Metrics (Requests Between Timestamps) → Precalculated cumulative sums

Finance (Revenue Jan 10..25) → Cumulative totals answer O(1)

Logs / Events (Error Counts in 30 min) → prefix[end] - prefix[start-1]

Remember This

Running total       → Prefix Sum
Range L..R          → prefix[R] - prefix[L-1]
Subarray = K        → Prefix + Hash Map
Many queries        → Precompute
2D rectangle        → 2D Prefix Sum
Many range updates  → Difference Array

💡 Golden Rule: "Store the work you already did, so you don't calculate the same sum again."