L12 · Prefix Sums & Difference Arrays

Series: LeetCode — From Basics to Interview-Ready · Session 12 / 65 · Phase 1 · Core patterns

Watch first

What this pattern IS

Suppose you'll be asked many times: "what's the sum of elements from index i to j?" Computing each answer by looping is O(n) per query — fine once, terrible for thousands of queries.

A prefix sum array precomputes cumulative totals: pre[k] = nums[0] + nums[1] + ... + nums[k-1]. Then the sum of any range [i, j] is just pre[j+1] - pre[i] — one subtraction, O(1). You pay O(n) once to build pre, and every range query after is instant.

The deeper move: prefix sums also let you count subarrays with a target sum, even when the array has negative numbers — a case where sliding windows silently fail (adding an element might decrease the sum, so you can't decide when to shrink). Pair prefix sums with a hash map of "how many times each prefix value has appeared" and you count target-sum subarrays in one pass.

The mirror image is the difference array: to add a value to every element in a range many times, don't touch each element — mark just the two endpoints and reconstruct once at the end. Range update in O(1), symmetric to range query in O(1).

First principles

The templates

Template A — prefix array for O(1) range sums

def build_prefix(nums):
    pre = [0] * (len(nums) + 1)         # pre[0] = 0; extra slot simplifies the formula
    for i, x in enumerate(nums):
        pre[i + 1] = pre[i] + x         # running total
    return pre
 
def range_sum(pre, i, j):               # inclusive sum of nums[i..j]
    return pre[j + 1] - pre[i]

The +1 sizing and pre[0] = 0 sentinel remove all the off-by-one pain — the sum of an empty prefix is 0.

Template B — count subarrays summing to k (works with negatives)

from collections import defaultdict
 
def count_subarrays(nums, k):
    seen = defaultdict(int)
    seen[0] = 1                         # empty prefix: sum 0 seen once
    running = 0
    count = 0
    for x in nums:
        running += x                    # running = pre[j+1]
        count += seen[running - k]      # how many earlier prefixes = running - k
        seen[running] += 1              # record this prefix for future j
    return count

seen[0] = 1 is the sentinel that lets a subarray starting at index 0 be counted (its prefix-before is the empty prefix, sum 0).

Template C — difference array for O(1) range updates

def apply_range_updates(n, updates):
    """updates = list of (l, r, val): add val to every index in [l, r]."""
    diff = [0] * (n + 1)
    for l, r, val in updates:
        diff[l] += val                  # start adding here
        diff[r + 1] -= val              # stop adding after r
    # reconstruct the real array by a prefix sum of diff
    result = [0] * n
    running = 0
    for i in range(n):
        running += diff[i]
        result[i] = running
    return result

Each update is two writes regardless of the range's length; you pay O(n) once to reconstruct.

Mental model

Memory / mnemonic

Two paired equations, learned as inverses: "query subtracts, update marks."

• Query (prefix sum): range = pre[j+1] − pre[i]. Say "j-plus-one minus i." The +1/0 sentinel means empty = 0.
• Count (prefix + map): rearrange to "look up running MINUS k." The peg word is "complement" — same idea as Two Sum, but over running totals. And always "seed zero once" (seen[0] = 1).
• Update (difference array): "plus at l, minus at r+1, then prefix-sum." The mirror of the query.

The trigger cue that saves you: "window with negatives → go prefix." The moment you see negative numbers in a subarray-sum problem, drop the sliding window.

The trap

What interviewers actually ask

Prefix problems test whether you recognise when windows fail and reach for the map.

• Subarray Sum Equals K (560) · Medium · Meta, Amazon — probes: do you use prefix+hashmap (correct with negatives) rather than a window? Follow-up: count of subarrays vs the longest such subarray.
• Product of Array Except Self (238) · Medium · Amazon, Meta — probes: prefix and suffix products without division and in O(1) extra space. Follow-up: what if a zero is present, or division were allowed?
• Range Sum Query - Immutable (303) · Easy · Amazon — probes: precompute the prefix once; each query O(1). Follow-up: 2D version (304), or mutable (307, needs a Fenwick tree).
• Contiguous Array (525) · Medium · Meta, Amazon — probes: map 0→−1 so equal-0s-and-1s becomes a zero-sum subarray via prefix. Follow-up: longest such subarray by storing first-seen index.
• Find Pivot Index (724) · Easy · Amazon — probes: left prefix vs total; the index where left sum equals right sum. Follow-up: all such pivots.
• Corporate Flight Bookings (1109) · Medium · Amazon — probes: difference array for many range-add updates in O(1) each. Follow-up: reconstruct in one pass.

Universal probe: "your array has negatives — does your approach still hold?" If you switch to prefix+map without prompting, that's the signal.

Worked solutions

1. Subarray Sum Equals K (560)

Plain words: given an integer array (possibly with negatives) and integer k, count how many contiguous subarrays sum to exactly k.

Brute force: sum every subarray — O(n^2). Insight: a subarray nums[i..j] sums to k iff pre[j+1] − pre[i] = k, i.e. pre[i] = pre[j+1] − k. Keep a running prefix and a frequency map of prefixes seen so far; at each j, add the count of running − k.

from collections import defaultdict
 
def subarraySum(nums, k):
    seen = defaultdict(int)
    seen[0] = 1                      # empty prefix
    running = 0
    count = 0
    for x in nums:
        running += x
        count += seen[running - k]   # earlier prefixes that complete a sum-k subarray
        seen[running] += 1
    return count

Complexity: O(n) time, O(n) memory. Follow-up — "the LONGEST subarray summing to k" (LC325): store the FIRST index each prefix appeared, and track j − first_index[running − k].

def maxSubArrayLen(nums, k):
    first = {0: -1}                  # prefix 0 at virtual index -1
    running = best = 0
    for i, x in enumerate(nums):
        running += x
        if running - k in first:
            best = max(best, i - first[running - k])
        if running not in first:     # keep the EARLIEST index only
            first[running] = i
    return best

2. Product of Array Except Self (238)

Plain words: return an array where out[i] is the product of all elements except nums[i], without using division, in O(n).

Insight: out[i] = (product of everything to the left of i) × (product of everything to the right). Compute the left prefix products in one pass, then fold in the right suffix products in a second pass using a single running variable.

def productExceptSelf(nums):
    n = len(nums)
    out = [1] * n
    # pass 1: out[i] = product of elements strictly to the LEFT of i
    prefix = 1
    for i in range(n):
        out[i] = prefix
        prefix *= nums[i]
    # pass 2: multiply in the product of elements strictly to the RIGHT
    suffix = 1
    for i in range(n - 1, -1, -1):
        out[i] *= suffix
        suffix *= nums[i]
    return out

Complexity: O(n) time, O(1) extra (output array aside). Follow-up — "if division were allowed": total product ÷ nums[i], but you must special-case zeros (one zero → only that slot is nonzero; two zeros → all zero).

3. Contiguous Array (525)

Plain words: given a binary array, return the length of the longest contiguous subarray with an equal number of 0s and 1s.

Insight: map every 0 to −1. Then "equal 0s and 1s" becomes "subarray sums to 0", which is a prefix problem: two positions with the same prefix sum bound a zero-sum subarray. Track the first index each prefix value appears.

def findMaxLength(nums):
    first = {0: -1}                  # prefix 0 at virtual index -1
    running = best = 0
    for i, x in enumerate(nums):
        running += 1 if x == 1 else -1   # 0 -> -1
        if running in first:
            best = max(best, i - first[running])   # same prefix -> zero-sum between
        else:
            first[running] = i        # record earliest occurrence
    return best

Complexity: O(n) time, O(n) memory. Follow-up — "count such subarrays": sum over frequencies of each prefix value (choose-2 style), analogous to LC560 with k = 0.

Tradeoff

Where this shows up

Prefix sums are the backbone of image processing's summed-area table (integral image): precompute cumulative sums over 2D, then the sum over any rectangle is four array lookups — used in real-time face detection (Viola-Jones) to evaluate box features in constant time. Difference arrays power range-update workloads like applying many overlapping discounts or reservations to a schedule without touching every slot per update, then materialising the final state in a single pass.

Checkpoint

Quiz

Practice queue

+7d / +21d mark spaced-repetition anchors.

• Running Sum of 1d Array (1480) — Easy · build a prefix array.
• Find Pivot Index (724) — Easy · left prefix vs total.
• Range Sum Query - Immutable (303) — Easy · precompute + O(1) query.
• Subarray Sum Equals K (560) — Medium · prefix + hashmap · +7d anchor.
• Product of Array Except Self (238) — Medium · prefix + suffix, no division · +21d anchor.
• Contiguous Array (525) — Medium · 0 → −1 zero-sum prefix.
• Corporate Flight Bookings (1109) — Medium · difference array range updates.