Prefix Sums & Difference Arrays

Review boundary and corrected contracts

Prefix indices use pre[0]=0 and inclusive query [l,r] = pre[r+1]−pre[l]. Difference updates write a closing delta at r+1, hence n+1 storage. Products and counts use arbitrary-precision integers; unit-cost complexity excludes integer bit length.

The examples below teach the stated input contracts; fragments and deliberately incorrect counterexamples are exercises, not production implementations. Complexity counts elementary operations unless a bit-cost or allocation caveat is stated. Practice times are suggestions, not measured performance or hiring guarantees.

Learning objective: Own prefix sums for O(1) range queries, the prefix-count-hashmap for counting subarrays with negatives, and difference arrays for O(1) range updates.

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

Prerequisites. Basic Python lists and a hash map. L10–L11 (sliding windows) are useful contrast — this session exists partly to handle the cases where windows break (negatives, exact-sum counting).

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) arithmetic operations and O(n) storage to build pre, then each valid range query uses one subtraction; constant operation count does not mean zero elapsed time or constant bit cost for arbitrarily large integers.

The deeper move: prefix sums also let you count subarrays with a target sum, even when the array has negative numbers — a case where the usual positive-sum expand/shrink rule is unsound (adding an element might decrease the sum). This does not invalidate every kind of sliding window on negative values. 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).

Mile-markers on a highway

Real: Highway mile-markers count total distance from the start. The distance between exit i and exit j is just marker[j] − marker[i] — you don't re-drive the road. That's a prefix sum; the difference is the range answer.

pre[j+1] - pre[i] gives the sum of nums[i..j] with no re-summation.

First principles

Question: Why does a prefix array turn any range-sum query into a single O(1) subtraction?

Premise: Define pre[k] = sum of the first k elements (pre[0] = 0).

Because: A cumulative total from a fixed origin lets every position be expressed relative to the start.

Premise: The sum of nums[i..j] = (sum of first j+1) − (sum of first i).

Because: Subtracting the total up to i removes exactly the elements before i, leaving nums[i..j].

Premise: So range(i, j) = pre[j+1] − pre[i], computed in O(1).

Because: Both prefix values are already stored; the answer is one subtraction.

Premise: For COUNTING subarrays with sum k: nums[i..j] sums to k ⇔ pre[j+1] − pre[i] = k ⇔ pre[i] = pre[j+1] − k.

Because: Rearranging the range equation turns 'find a subarray' into 'find a prior prefix value'.

Premise: A running hash map of prefix-value frequencies answers 'how many earlier i satisfy pre[i] = pre[j+1] − k' in O(1).

Because: With suitable hashing, lookup takes expected constant work under bounded-cost keys; prefix equality needs no sign-based growth assumption.

Conclusion: Prefix sums turn range sums into subtraction and exact-sum counting into earlier-prefix lookup for either sign. The simple sum-threshold window proof, not the entire sliding-window family, is what requires sign restrictions.

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]

Contract: nums is an integer sequence; build_prefix([]) returns [0]. For the inclusive range helper, require 0 <= i <= j < len(pre)-1; it does not validate invalid or negative indices. Equivalently, a half-open [i,j) sum is pre[j]-pre[i], including an empty range when i=j. The extra zero prefix makes ranges starting at zero work without a special case, but callers must still distinguish the two indexing conventions.

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.get(running - k, 0)  # query without inserting a missing key
        seen[running] += 1              # record this prefix for future j
    return count

The map contains frequencies of earlier prefixes, including the empty prefix once. Querying before inserting the current prefix counts distinct nonempty ranges ending here and avoids a spurious empty range for k=0. Repeated prefix values require frequencies, not a set: [0,0] has three zero-sum nonempty ranges. .get() avoids inserting missing complement-query keys; only observed prefixes occupy the map.

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

def apply_range_updates(n, updates):
    """Starting from n zeros, apply inclusive (l,r,val) additions.
    n>=0 and every update requires 0<=l<=r<n; no validation is performed."""
    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

For u valid updates, construction plus reconstruction costs O(n+u) arithmetic operations and O(n) storage. Each update adds val to diff[l] and removes that contribution at diff[r+1]. Prefix accumulation is therefore increased exactly over [l,r]; the sentinel at n closes updates ending at n−1 without indexing past the buffer. For n=0, the update list must be empty. This function starts from zeros; to update existing values, add the reconstructed deltas to those values or first form their difference array. It is a batched representation: materializing after every update would lose the O(1)-per-update advantage.

Mental model

Name: Cumulative-from-origin

Picture: Every position carries the running total from the start. A range is a difference of two such totals. Counting target-sum subarrays = 'has a matching earlier total appeared?' — a lookup, not a scan.

• pre[k] = sum of first k; range(i,j) = pre[j+1] − pre[i].

• Counting sum-k subarrays: look up running − k in a prefix-frequency map; seed seen[0] = 1.

• Prefix equality works with negative values; ordinary positive-sum shrinking rules need a different justification.

• Difference array = inverse: mark two endpoints, prefix-sum once to apply range updates.

Trigger: 'sum of range i..j', 'how many subarrays sum to k', 'many range-add updates', or a window problem that has NEGATIVE numbers.

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.

A useful cue is "exact sums with arbitrary signs → investigate prefixes." Choose the subsequent structure according to the query: an equality-count map differs from the ordered/monotonic structure used for shortest ranges above a threshold. Negative values do not break a fixed-size rolling sum.

The trap

Myth: To count subarrays that sum to k you can slide a window, growing and shrinking on the running sum.

Truth: The ordinary sum-threshold expand/shrink proof needs nonnegative values and appropriate target semantics. Arbitrary-sign exact-sum counting is handled by prefix frequencies. Even with nonnegative values, counting all exact-sum windows needs care around zeros and multiplicity; one retained window is not one match.

Why: With negatives, adding an element can DECREASE the sum, so 'shrink while too big' logic is invalid — a valid window might lie beyond a dip you already skipped past.

Test: Try nums = [1, -1, 0], k = 0. The correct count is 3; a naive positive-only window returns the wrong number. The prefix+map method gets it right.

What reviewers actually ask

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

• Subarray Sum Equals K (560) · Medium · Practice selection. — 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 · Practice selection. — 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 · Practice selection. — probes: precompute the prefix once; each query O(1). Follow-up: 2D version (304), or mutable (307, where a Fenwick or segment tree can support efficient updates and queries).
• Contiguous Array (525) · Medium · Practice selection. — 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 · Practice selection. — probes: left prefix vs total; the index where left sum equals right sum. Follow-up: all such pivots.
• Corporate Flight Bookings (1109) · Medium · Practice selection. — probes: difference array for many range-add updates in O(1) each. Follow-up: reconstruct in one pass.

Self-check: state which algebraic relationship or monotonicity assumption makes each approach valid. Switching to a hash map by keyword is not a substitute for identifying the actual query.

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: extend a running sum from each start for O(n²) total additions; recomputing each subarray sum independently instead takes O(n³) total element visits. 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.get(running - k, 0)  # earlier prefixes; no query-side insertion
        seen[running] += 1
    return count

Complexity: expected O(n) time for bounded-cost suitable hashes, O(u) stored prefixes with u <= n+1. For the longest range summing to k, retain each prefix’s earliest index instead of its frequency. For a fixed ending index, an earlier equal prefix gives a longer range; never overwrite it with a later index.

Goal: Return the longest nonempty subarray length summing to k, or 0 if none exists. The earliest-prefix map also handles empty input.

Hint: Store first-seen index of each running prefix; only insert if the prefix is new.

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 in the unit-cost arithmetic model: O(n) multiplications and O(1) auxiliary accumulators, excluding the O(n) output array. With arbitrary-size integers, accumulator/result bit lengths and multiplication costs grow; constant accumulator count is not constant bytes. Empty input returns []; a singleton returns [1], the empty product. Zeros and negative values need no special branch in this no-division method. A division-based variant must handle zeros: one zero leaves only its position potentially nonzero (the product of all other values), while two or more zeros force every output to 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: expected O(n) time and O(n) map space in the bounded-cost model. The input must contain only 0 and 1; the else branch is not validation for arbitrary values. To count balanced ranges, include the empty prefix among all n+1 prefixes, then sum f(f−1)/2 over their value frequencies f. Every pair of equal-prefix positions defines one nonempty balanced range; the longest variant instead retains the earliest position.

Tradeoff

Decision: Answer subarray-sum / range-sum problems efficiently.

Name: Sliding window

Gain: O(1) space, single pass, very clean.

Cost: A simple sum-threshold shrink rule needs nonnegative values and a compatible target; fixed-size sums and other window properties have different contracts.

Pick: All-positive subarray problems (min/max length under a sum bound).

Name: Prefix sum + hashmap

Gain: Expected O(n) exact-sum counting for either sign under suitable hashes, without a monotone sum requirement.

Cost: O(n) memory for the prefix-frequency map.

Pick: The required equality can be expressed as an earlier-prefix lookup; not every task with negative values is a prefix-hash problem.

Name: Fenwick / segment tree

Gain: Supports UPDATES between queries (mutable array) in O(log n).

Cost: More code; O(log n) not O(1); overkill if the array is static.

Pick: When elements change and you still need range sums (LC307).

Verdict: Static range sums suit a prefix array; arbitrary-sign exact-sum counting suits prefix frequencies; batched range additions suit a difference array. Interleaved point updates/range sums can use a Fenwick or segment tree. Each choice follows the query/update contract, not a blanket rule about negative input.

Where this shows up

A two-dimensional summed-area table extends the same subtraction principle. Define P[r][c] as the sum over rows [0,r) and columns [0,c), with a zero border. The rectangle [r1,r2) × [c1,c2) has sum P[r2][c2] - P[r1][c2] - P[r2][c1] + P[r1][c1]: the top and left excluded regions were each removed, so their shared corner must be added back once. For rows [1,2,3] and [4,5,6], both rows and columns [1,3) sum to 21-0-5+0=16. This is four table accesses after preprocessing, not a complete image-recognition system.

Difference arrays similarly model batches of additive adjustments over a discretized schedule. If the real system requires capacity validation, overlapping transactions or queries between updates, those obligations are not solved by the endpoint markers alone.

Checkpoint

You can now…

• Build a prefix array and answer any range sum in O(1) with pre[j+1] − pre[i].

• Count target-sum subarrays with prefix + hashmap, correctly with negatives.

• Seed seen[0] = 1 and explain why that sentinel is necessary.

• Solve Product of Array Except Self with prefix and suffix passes, no division.

• Turn an equal-count problem into a zero-sum prefix problem (0 → −1).

• Apply many range-add updates in O(1) each with a difference array.

• Decide between windows, prefix+map, and Fenwick trees for a given constraint.

Quiz

Self-check (answer follows each question).

Recall check

Q: What is the O(1) formula for the inclusive sum of nums[i..j] using a prefix array?

A: pre[j+1] − pre[i], where pre[k] is the sum of the first k elements and pre[0] = 0.

Q: In Subarray Sum Equals K, what value do you look up in the frequency map at each step, and why?

A: running − k: a subarray ending here sums to k iff an earlier prefix equalled running − k.

Q: Why is seen[0] = 1 required before the loop?

A: It represents the empty prefix (sum 0), so subarrays that start at index 0 and sum to k are counted.

Q: Why do sliding windows fail for counting subarrays with a target sum when negatives are present?

A: Adding an element can decrease the sum, so validity isn't monotonic — the shrink-when-too-big rule is unsound.

Q: In a difference array, to add val to indices [l, r], which two entries do you modify?

A: diff[l] += val and diff[r+1] −= val; a prefix sum of diff then reconstructs the updated array.

Q: ★ Stretch: to find the LONGEST subarray summing to k (not the count), what changes in the hashmap, and why?

A: Store the FIRST index each prefix value appeared (don't overwrite), and compute i − first[running − k]. Earliest index maximises the length; overwriting would shrink candidate spans.

Stretch: true

Practice queue

+7d / +21d are optional elapsed-day review suggestions.

• 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.

Corrective source notes

• Python 3.14 collections — defaultdict get does not insert a missing key, unlike indexing; exact passage rechecked 2026-10-09. Counter equality is not a proof of these prefix identities.
• One- and two-dimensional range identities, earliest-prefix maximization and difference-array reconstruction are derived above. Integer operation counts intentionally exclude arbitrary-precision bit costs.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.