Algorithms & Coding Interviews · Arrays, Strings & Linear Structures

Prefix Sums

Prefix sums turn any range sum into one subtraction, and combined with a hash map they count subarrays with a given sum in O(n), even with negative numbers. Learn the 1D, hash-map and 2D variants plus difference arrays, with animated walkthroughs of three LeetCode problems.

🧮 Algorithms & Coding Interviews● Intermediate⏱ 9 min read▶ 3 interactive🛠️ 4 exercises

🎯 What you'll learn

Range sums in O(1) after O(n) preprocessing
Prefix + hash map: count, longest, divisible-by-k
2D prefix sums with inclusion–exclusion
Difference arrays for range updates

📚 Before you start

Part 1The Pattern

A prefix sum array stores running totals so that the sum of any range is one subtraction: sum(i..j) = prefix[j+1] − prefix[i]. Combined with a hash map of previously seen prefix sums, it answers "how many subarrays have sum k?" in O(n), and unlike sliding windows it works with negative numbers.

A prefix array where the sum of a range is the difference of two prefix values

1Recognition Cues

"sum of elements between i and j", many range queries on a static array
"number of subarrays with sum equal to k", "subarray sum divisible by k", "equal number of 0s and 1s"
"pivot/equilibrium index" (left sum equals right sum)
2D: "sum of a sub-rectangle", many rectangle queries on a matrix

2Templates

typescript

function buildPrefix(nums: number[]): number[] {
  const prefix = new Array(nums.length + 1).fill(0);
  for (let i = 0; i < nums.length; i++) prefix[i + 1] = prefix[i] + nums[i];
  return prefix;
}

function countSubarraysWithSum(nums: number[], k: number): number {
  const seen = new Map<number, number>([[0, 1]]);
  let running = 0, count = 0;
  for (const x of nums) {
    running += x;
    count += seen.get(running - k) ?? 0;
    seen.set(running, (seen.get(running) ?? 0) + 1);
  }
  return count;
}

python

def build_prefix(nums):
    prefix = [0] * (len(nums) + 1)          # prefix[i] = sum of nums[0:i]
    for i, x in enumerate(nums):
        prefix[i + 1] = prefix[i] + x
    return prefix                           # sum(i..j) = prefix[j+1] - prefix[i]

def count_subarrays_with_sum(nums, k):
    seen = {0: 1}                           # prefix sum -> how many times seen
    running = count = 0
    for x in nums:
        running += x
        count += seen.get(running - k, 0)   # earlier prefixes that leave sum k
        seen[running] = seen.get(running, 0) + 1
    return count

The seen = {0: 1} initialization represents the empty prefix, so subarrays starting at index 0 are counted.

3Why Prefix + Hash Map Works

If the running sum at index j is P[j], a subarray (i..j] sums to k exactly when P[i] = P[j] − k. So at each j, the number of valid subarrays ending at j is the number of earlier prefixes equal to P[j] − k, which a hash map counts in O(1).

Variants change what you store or look up:

Problem	Transform	Map stores
subarray sum = k	none	prefix → count
longest subarray with sum k	none	prefix → first index
equal 0s and 1s	map 0 → −1, find sum 0	prefix → first index
sum divisible by k	use `prefix % k` (normalize negatives)	remainder → count

42D Prefix Sums

For a matrix, P[r+1][c+1] = sum of the rectangle from (0,0) to (r,c):

text

P[r+1][c+1] = M[r][c] + P[r][c+1] + P[r+1][c] − P[r][c]
sum(r1..r2, c1..c2) = P[r2+1][c2+1] − P[r1][c2+1] − P[r2+1][c1] + P[r1][c1]

Building costs O(R·C); every rectangle query is then O(1). This is inclusion–exclusion: add the two overlapping strips, subtract the doubly counted corner.

The inverse trick: to add v to every element in [l, r] many times, write diff[l] += v and diff[r+1] −= v, then take one prefix sum at the end. Range updates become O(1) each (car pooling, corporate flight bookings).

⚠️ Common Pitfalls

Forgetting {0: 1} (or index −1 for "first index" variants), which misses subarrays starting at 0.
Updating the map before querying it, which counts the empty subarray when k = 0.
Negative remainders: in Python -1 % 5 == 4, but in JS/C# -1 % 5 == -1; normalize with ((x % k) + k) % k.
Integer overflow in C#/Java with large sums: use long.
Using a sliding window when numbers can be negative.

📋 Quick Reference

text

prefix[i+1] = prefix[i] + a[i];  sum(i..j) = prefix[j+1] - prefix[i]
count sum=k: seen={0:1}; run+=x; ans+=seen[run-k]; seen[run]++
2D: P[r+1][c+1] = M[r][c] + P[r][c+1] + P[r+1][c] - P[r][c]
diff array: diff[l]+=v; diff[r+1]-=v; prefix at the end

Part 2Interview Problems

Six problems: range queries, the prefix + hash map family (counting, longest, divisibility), and 2D prefix sums.

1Range Sum Query – Immutable (LeetCode 303)

🟢 Easy. Design NumArray(nums) with sumRange(left, right) returning the inclusive range sum. Many queries will be made.

text

nums = [-2,0,3,-5,2,-1]
sumRange(0,2) → 1 · sumRange(2,5) → -1 · sumRange(0,5) → -3

Approach. Precompute the prefix array once in the constructor; each query is one subtraction.

Complexity. O(n) build, O(1) per query, O(n) space.

typescript

class NumArray {
  private prefix: number[] = [0];
  constructor(nums: number[]) {
    for (const x of nums) this.prefix.push(this.prefix[this.prefix.length - 1] + x);
  }
  sumRange(left: number, right: number): number {
    return this.prefix[right + 1] - this.prefix[left];
  }
}

python

class NumArray:
    def __init__(self, nums):
        self.prefix = [0]
        for x in nums:
            self.prefix.append(self.prefix[-1] + x)

    def sum_range(self, left, right):
        return self.prefix[right + 1] - self.prefix[left]

2Find Pivot Index (LeetCode 724)

🟢 Easy. Return the leftmost index where the sum of elements to its left equals the sum to its right (−1 if none).

text

nums = [1,7,3,6,5,6] → 3   (1+7+3 = 5+6)

Approach. With total known, the right sum at i is total − leftSum − nums[i]. Walk once, maintaining leftSum.

Complexity. O(n) time, O(1) space.

typescript

function pivotIndex(nums: number[]): number {
  const total = nums.reduce((a, b) => a + b, 0);
  let left = 0;
  for (let i = 0; i < nums.length; i++) {
    if (left === total - left - nums[i]) return i;
    left += nums[i];
  }
  return -1;
}

python

def pivot_index(nums):
    total = sum(nums)
    left = 0
    for i, x in enumerate(nums):
        if left == total - left - x:
            return i
        left += x
    return -1

3Subarray Sum Equals K (LeetCode 560)

🟠 Medium. Return the number of contiguous subarrays whose sum equals k. Values may be negative.

text

nums = [1,1,1], k = 2 → 2

Approach. Running prefix sum + a map counting how often each prefix has occurred. At each position, add the count of running − k.

Complexity. O(n) time, O(n) space.

typescript

function subarraySum(nums: number[], k: number): number {
  const seen = new Map<number, number>([[0, 1]]);
  let running = 0, count = 0;
  for (const x of nums) {
    running += x;
    count += seen.get(running - k) ?? 0;
    seen.set(running, (seen.get(running) ?? 0) + 1);
  }
  return count;
}

python

def subarray_sum(nums, k):
    seen = {0: 1}
    running = count = 0
    for x in nums:
        running += x
        count += seen.get(running - k, 0)
        seen[running] = seen.get(running, 0) + 1
    return count

4Contiguous Array (LeetCode 525)

🟠 Medium. In a binary array, return the length of the longest contiguous subarray with an equal number of 0s and 1s.

text

nums = [0,1,0] → 2

Approach. Treat 0 as −1; then 'equal counts' means 'sum 0'. Store the first index where each prefix sum appears (with sum 0 at index −1). When a prefix repeats, the subarray between the two occurrences sums to 0.

Complexity. O(n) time, O(n) space.

typescript

function findMaxLength(nums: number[]): number {
  const first = new Map<number, number>([[0, -1]]);
  let running = 0, best = 0;
  for (let i = 0; i < nums.length; i++) {
    running += nums[i] === 1 ? 1 : -1;
    if (first.has(running)) best = Math.max(best, i - first.get(running)!);
    else first.set(running, i);
  }
  return best;
}

python

def find_max_length(nums):
    first = {0: -1}
    running = best = 0
    for i, x in enumerate(nums):
        running += 1 if x == 1 else -1
        if running in first:
            best = max(best, i - first[running])
        else:
            first[running] = i
    return best

5Subarray Sums Divisible by K (LeetCode 974)

🟠 Medium. Return the number of non-empty subarrays whose sum is divisible by k.

text

nums = [4,5,0,-2,-3,1], k = 5 → 7

Approach. Two prefixes with the same remainder mod k enclose a subarray divisible by k. Count remainders (normalized to be non-negative) and add the count of the current remainder at each step.

Complexity. O(n) time, O(k) space.

typescript

function subarraysDivByK(nums: number[], k: number): number {
  const counts = new Map<number, number>([[0, 1]]);
  let running = 0, total = 0;
  for (const x of nums) {
    running = (((running + x) % k) + k) % k;   // normalize negatives in JS
    total += counts.get(running) ?? 0;
    counts.set(running, (counts.get(running) ?? 0) + 1);
  }
  return total;
}

python

def subarrays_div_by_k(nums, k):
    counts = {0: 1}
    running = total = 0
    for x in nums:
        running = (running + x) % k          # Python % is already non-negative
        total += counts.get(running, 0)
        counts[running] = counts.get(running, 0) + 1
    return total

6Range Sum Query 2D – Immutable (LeetCode 304)

🟠 Medium. Design NumMatrix(matrix) with sumRegion(r1, c1, r2, c2) returning the sum of the sub-rectangle, in O(1) per query.

text

sumRegion(2,1,4,3) → 8 · sumRegion(1,1,2,2) → 11

Approach. Build a (R+1)×(C+1) prefix table with inclusion–exclusion, then answer each query with four lookups.

Complexity. O(R·C) build, O(1) per query.

typescript

class NumMatrix {
  private P: number[][];
  constructor(matrix: number[][]) {
    const R = matrix.length, C = matrix[0].length;
    this.P = Array.from({ length: R + 1 }, () => new Array(C + 1).fill(0));
    for (let r = 0; r < R; r++)
      for (let c = 0; c < C; c++)
        this.P[r + 1][c + 1] = matrix[r][c] + this.P[r][c + 1] + this.P[r + 1][c] - this.P[r][c];
  }
  sumRegion(r1: number, c1: number, r2: number, c2: number): number {
    const P = this.P;
    return P[r2 + 1][c2 + 1] - P[r1][c2 + 1] - P[r2 + 1][c1] + P[r1][c1];
  }
}

python

class NumMatrix:
    def __init__(self, matrix):
        R, C = len(matrix), len(matrix[0])
        self.P = [[0] * (C + 1) for _ in range(R + 1)]
        for r in range(R):
            for c in range(C):
                self.P[r + 1][c + 1] = matrix[r][c] + self.P[r][c + 1] + self.P[r + 1][c] - self.P[r][c]

    def sum_region(self, r1, c1, r2, c2):
        P = self.P
        return P[r2 + 1][c2 + 1] - P[r1][c2 + 1] - P[r2 + 1][c1] + P[r1][c1]

🧠 Key takeaways

sum(i..j) = prefix[j+1] − prefix[i]: O(n) build, O(1) per query.
Prefix + hash map counts subarrays with sum k in O(n) and handles negative numbers.
Store counts for 'how many', first index for 'longest'; use remainders for divisibility.
2D prefix uses inclusion–exclusion; difference arrays make range updates O(1).

🛠️ Practice exercises

Each exercise is a file in this topic folder. Code exercises are self-checking: run them and make the checks pass.

algo_prefix_sums_exercise_1.py

TS PY

algo_prefix_sums_exercise_2.py

TS PY

✅ Check yourself

Answer the questions — feedback is instant.

1. Why initialize seen = {0: 1}?

The empty prefix.

2. Longest subarray with sum k stores in the map…

Earliest start → longest.

3. In JS, (-7) % 5 equals…

Normalize with ((x % k) + k) % k.

4. 2D query cost after building the prefix table?

Four lookups.

Source: algo_prefix_sums_theory_1.md, algo_prefix_sums_theory_2.md · generated by tools/build_lessons.py

🎯 What you'll learn

📚 Before you start

1Recognition Cues

2Templates

3Why Prefix + Hash Map Works

42D Prefix Sums

5Related: Difference Arrays

⚠️ Common Pitfalls

📋 Quick Reference

1Range Sum Query – Immutable (LeetCode 303)

2Find Pivot Index (LeetCode 724)

3Subarray Sum Equals K (LeetCode 560)

4Contiguous Array (LeetCode 525)

5Subarray Sums Divisible by K (LeetCode 974)

6Range Sum Query 2D – Immutable (LeetCode 304)

🧠 Key takeaways

🛠️ Practice exercises

✅ Check yourself