leetExpert

Module 12 · Prefix Sum

Practice

Practice~2 min

How to practice this module

Prefix-sum drills reward precomputing ranges: decide what the prefix means, then every subarray query becomes a difference. Range queries first, then the prefix + hash pair, then 2D inclusion–exclusion; Kadane is the capstone that reuses the running-total idea as a 1-D DP. Done when all five show Solved in the hub.

Problems

Prefix Sum — work them in order; difficulty ascends.

0/5

solved

  1. 1Range Sum Query — ImmutableEasy1D prefix arrayWatch for: pref[i] is the sum of the first i elements; range [l, r] is pref[r+1] - pref[l] — get the off-by-one right once
  2. 2Subarray Sum Equals KMediumPrefix + hash mapWatch for: Seed the map with prefix 0 -> count 1; a subarray ending at i sums to k iff prefix[i] - k was already seen
  3. 3Contiguous ArrayMediumPrefix of a transformed arrayWatch for: Map 0 -> -1 so a zero balance means equal counts; store the FIRST occurrence of each prefix to maximise length
  4. 4Range Sum Query 2D — ImmutableMedium2D inclusion-exclusionWatch for: Grid prefix with +1 padding; a rectangle is four terms — the padded origin is where off-by-one lives
  5. 5Maximum Subarray (Kadane's Algorithm)MediumRunning maximum (1-D DP)Watch for: The running sum resets to 0 when negative — decide "extend" vs "restart" at each element and track the all-time max

Cheatsheet

Prefix Sum — Precompute ranges so every subarray query is O(1).

Smell → pattern

  • Many range sum queriesPrefix array
  • Subarray sum equals kPrefix + hash
  • 2D rectangle sumsInclusion–exclusion table
  • Range add, then read onceDifference array

Patterns

1D prefix

Core

Smell: Sum of a[l..r] many times

pref[i] = sum of first i elements. Range [l, r] → pref[r+1] − pref[l]. Mind the off-by-one on length.

pref[i]

Prefix + hash

Safe

Smell: Count / find subarrays summing to k

Store first (or count of) each prefix value. Need pref − k already seen ⇒ a subarray ending here sums to k.

0123

Difference array

Reach

Smell: Many range updates, few reads

Range updates in O(1): +v at L, −v at R+1, then prefix to materialise. Dual of prefix sums.

pref[i]

Complexity targets

  • Build prefix

    Time
    O(n)
    Space
    O(n)
    Note
    Then O(1) queries

  • Subarray sum = k

    Time
    O(n)
    Space
    O(n)
    Note
    Hash of prefixes

Traps

  • Index alignment

    Decide whether pref[0]=0 (sum of first 0) or pref[0]=a[0]. Mixing conventions is the classic bug.

  • Forgetting the empty prefix

    Subarray-sum-to-k needs the 0-prefix seeded in the map (count 1). Without it, prefixes that themselves equal k are missed.