Arrays & Hashing

Prefix Sums

Precompute running totals so any range sum is a subtraction.

Medium, about 75 minutes to practise.

1Understand

The idea

Precompute running totals once: prefix[i] is the sum of the first i elements. Then the sum of any range [l, r) is prefix[r], prefix[l], an O(1) subtraction. Combined with a hash map of prefix values already seen, it counts subarrays with a given sum in a single pass, even with negative numbers.

Intuition

A prefix array turns every range-sum question into a subtraction: after building prefix once, sum of [l, r) is prefix[r], prefix[l]. Put a leading 0 so empty prefixes and ranges that start at index 0 work cleanly.

When values can be negative, sliding windows lose monotonicity, but prefix + hash map still counts subarrays with sum k: each running total asks how often running, k has appeared.

The same idea extends to products (careful with zeros), parity, modulo classes, and 2-D grids (inclusion of rectangles).

What you will be able to do

  • Build a prefix array with a leading 0
  • Combine prefix sums with a hash map

When to use it

  • Sum of a subarray or range, many times
  • Count subarrays with sum equal to k
  • Values can be negative (so a window will not work)

2See it

Walkthrough

Range sum in O(1) after a prefix

nums = [2, 1, 3, 4], prefix[i] = sum of first i elements; range [1, 4) = prefix[4], prefix[1].

1 / 6

i
2
1
3
4
0123

Original array. We want sum(nums[1] + nums[2] + nums[3]) = 1+3+4 without rescanning.

# query sum of indices [1, 4)

Live template

Line 1 active

1count = {0: 1}; running = 0
2for x in nums:
3 running += x
4 answer += count.get(running - k, 0)
5 count[running] = count.get(running, 0) + 1

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

Build is O(n); each range query afterward is O(1). The hash-map variant is O(n) time and O(n) space. Prefer a plain prefix array when you answer many static range sums; prefer the map when counting subarrays. Use a Fenwick/segment tree when the array also mutates.

Read the walkthrough as text

Subarray sum equals k. nums = [1, 2, 3], k = 3.

  1. count = {0: 1}, running = 0, answer = 0.
  2. See 1: running 1. Need 1, 3 = −2, absent. Store count of 1.
  3. See 2: running 3. Need 0, present once → answer = 1 (subarray [1,2]). Store 3.
  4. See 3: running 6. Need 3, present once → answer = 2 (also [3]).

In code:

  • count = {0: 1}; running = 0; answer = 0
  • for x in nums:
  • running += x
  • answer += count.get(running - k, 0)
  • count[running] = count.get(running, 0) + 1

3Recognise it

Kinds of problems (7)

Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.

  • Range sum queries

    Example. Many queries: sum of nums[l..r] inclusive.

    How. Build prefix with leading 0; each query is prefix[r+1], prefix[l].

  • Subarray sum equals k (prefix + hash map)

    Example. Count subarrays whose sum is k (negatives allowed).

    How. Map prefix sum → frequency; at each running sum s, add count[s, k] before updating s.

  • Product of array except self

    Example. Output[i] = product of all nums except nums[i], no division.

    How. Prefix products left→right, then a suffix pass right→left multiplying into the answer.

  • 2-D prefix sums

    Example. Sum of subrectangle in a matrix, many queries.

    How. 2-D prefix: add row above and column left; rectangle sum is four corner prefixes.

  • Prefix parity / modulo classes

    Example. Count subarrays with even sum (mod 2).

    How. Track running parity; pairs with same prefix parity give even-length segments between them.

  • Difference array for range updates (sweep line)

    Example. Apply many “add v to [l, r]” updates, then read final array.

    How. diff[l] += v, diff[r+1] -= v; prefix-sum diff once to recover values.

  • Prefix and suffix aggregates (max to the right, penalties)

    Example. Best sight or trap rain water precomputes max on each side.

    How. One pass builds prefix max; reverse pass builds suffix max; answer uses both at each index.

Common mistakes

Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.

  • Missing base prefix

    Why it happens. The hash map starts empty, so prefixes that start at index 0 are under-counted.

    How it fails. Subarray sum k=0 from index 0 alone: without count[0]=1 you never count the prefix itself.

    Fix. Seed `count = {0: 1}` (or prefix array with leading 0) before the loop.

  • Window on negatives

    Why it happens. A variable-size sum window assumes adding always helps validity.

    How it fails. nums = [1, -1, 0], k=0: shrinking a window cannot recover a positive sum, you miss subarrays.

    Fix. Use prefix + hash map for subarray sums when negatives appear; reserve sliding window for nonnegative sums.

  • Range off by one

    Why it happens. Inclusive vs exclusive range endpoints get swapped in prefix[j], prefix[i].

    How it fails. Sum of nums[0..2] uses prefix[2]−prefix[0] but you wanted index 0 included, off by one at the left.

    Fix. Define prefix[i] as sum of first i elements (exclusive end); range [l,r] is prefix[r+1]−prefix[l].

4Check yourself

Concept check

A short quiz on this lesson before you practise. Optional, and it does not gate coding.

Ready to practise?

Mastery comes from solving. The lesson is optional context.

All lessons