#Prefix sums and difference arrays

Recognition in one line: the problem asks about sums (or counts) over ranges or subarrays, and the brute force recomputes the same overlapping sums repeatedly.

The cheapest big win in the whole toolkit — usually four lines that remove a factor of n.

#1 · Recognition cues

The unifying idea: any range aggregate f(i..j) where f has an inverse can be answered as F(j) − F(i−1) after one pass. Sums qualify. XOR qualifies (it is its own inverse). Minimum does not — which is why range-minimum queries need a sparse table or segment tree instead, and knowing that boundary is worth stating.

#2 · The basic structure

nums    = [ 2,  4,  1,  7,  3]
prefix  = [0, 2,  6,  7, 14, 17]        prefix[i] = sum of first i elements
           ^  ^
           |  the leading 0 is what removes every edge case

sum(i..j) inclusive = prefix[j+1] - prefix[i]

sum(1..3) = prefix[4] - prefix[1] = 14 - 2 = 12   (4 + 1 + 7)  ✓

def build_prefix(nums):
    # Length n+1 with a leading 0. Without it, every query needs an
    # "if i == 0" special case -- which is where the bugs live.
    prefix = [0] * (len(nums) + 1)
    for i, x in enumerate(nums):
        prefix[i + 1] = prefix[i] + x
    return prefix

def range_sum(prefix, i, j):              # inclusive both ends
    return prefix[j + 1] - prefix[i]

int[] prefix = new int[nums.length + 1];
for (int i = 0; i < nums.length; i++) {
    prefix[i + 1] = prefix[i] + nums[i];
}
// sum of nums[i..j] inclusive
int sum = prefix[j + 1] - prefix[i];

The leading zero is not cosmetic. With it, every query is one expression. Without it, i == 0 is a special case you will forget under pressure. Use the n+1 form always.

Cost: O(n) once, then O(1) per query. Worth it from the second query onward.

#3 · The hash-map variant — the interview version

This is the one that actually gets asked, and it is a genuinely different idea from the array above.

Problem (LC 560): count subarrays summing to exactly k.

A subarray (i..j) sums to k
  <=>  prefix[j+1] - prefix[i] == k
  <=>  prefix[i] == prefix[j+1] - k

So while scanning, at each position ask:
  "how many earlier prefixes equal (current_prefix - k)?"

That is a hash-map lookup. One pass. O(n).

def subarray_sum(nums, k):
    from collections import defaultdict
    counts = defaultdict(int)
    counts[0] = 1                 # the empty prefix -- REQUIRED, see below
    running = 0
    total = 0

    for x in nums:
        running += x
        # Every earlier prefix equal to (running - k) marks the start of
        # a subarray ending here that sums to k.
        total += counts[running - k]
        counts[running] += 1      # record AFTER counting, or a zero-length
                                  # subarray would match itself
    return total

public int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> counts = new HashMap<>();
    counts.put(0, 1);                    // empty prefix
    int running = 0, total = 0;
    for (int x : nums) {
        running += x;
        total += counts.getOrDefault(running - k, 0);
        counts.merge(running, 1, Integer::sum);
    }
    return total;
}

Two details that are the whole difficulty:

Why sliding window does not work here, and the interviewer may ask: sliding window requires that growing the window monotonically increases the sum. With negative numbers it does not, so there is no valid shrink condition. Prefix sums plus a hash map handle negatives; sliding window does not. State that distinction — it is the reason this pattern exists alongside sliding window.

#4 · The difference array — the inverse

Use when: many range updates, then read the final array.

"Add 5 to indices 2..5" many times, then print the array.

Naive: O(range) per update.
Difference array: O(1) per update, O(n) once at the end.

diff[i] = nums[i] - nums[i-1]

To add v to [l..r]:      diff[l] += v;  diff[r+1] -= v
                                        ^ the -= is what stops the
                                          addition after r

Rebuild with a prefix sum over diff.

def range_updates(n, updates):
    diff = [0] * (n + 1)              # n+1 so r+1 is always in range
    for l, r, v in updates:
        diff[l] += v
        diff[r + 1] -= v              # cancel beyond r

    result = []
    running = 0
    for i in range(n):
        running += diff[i]
        result.append(running)
    return result

LC 1109 (Corporate Flight Bookings) and LC 370 (Range Addition) are this verbatim. It also underlies the sweep-line solution to interval problems — +1 at a start, −1 at an end is exactly a difference array.

#5 · 2D prefix sums

For rectangle queries on a grid (LC 304).

P[i][j] = sum of the rectangle from (0,0) to (i-1, j-1)

Build:
  P[i+1][j+1] = grid[i][j] + P[i][j+1] + P[i+1][j] - P[i][j]
                                                     ^ added twice, remove once

Query (r1,c1) to (r2,c2) inclusive -- INCLUSION-EXCLUSION:

  P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]

      +-----------+
      |  A  |  B  |      want D
      |-----+-----|      = total - (A+B) - (A+C) + A
      |  C  |  D  |
      +-----------+      A is subtracted twice, so add it back once

Both the build and the query are inclusion-exclusion, and the + P[i][j] term is the part people drop. Draw the rectangle if you are unsure — it is faster than re-deriving.

#6 · The ladder

#Foundational

#Medium

#Hard

If you only do four: 560, 238, 974, 1109.

#7 · Worked example — LC 974, divisible by k

Problem: count subarrays whose sum is divisible by k.

The insight, which generalises: (prefix[j] − prefix[i]) % k == 0 exactly when prefix[j] % k == prefix[i] % k. So group prefixes by remainder and count pairs — the same shape as LC 560, with the key changed from the value to the value mod k.

nums = [4,5,0,-2,-3,1], k = 5
prefix:      4, 9, 9, 7, 4, 5
prefix % 5:  4, 4, 4, 2, 4, 0

remainder 4 appears 4 times -> C(4,2) = 6 pairs
remainder 0 appears 1 time, plus the empty prefix -> C(2,2) = 1
total = 7

def subarrays_div_by_k(nums, k):
    counts = {0: 1}                # empty prefix
    running = 0
    total = 0
    for x in nums:
        running += x
        # Python's % already returns non-negative for positive k.
        # In Java, ((running % k) + k) % k is REQUIRED -- otherwise -3 % 5
        # is -3, not 2, and the grouping silently breaks.
        r = running % k
        total += counts.get(r, 0)
        counts[r] = counts.get(r, 0) + 1
    return total

The negative-modulo difference between Python and Java is a real bug source and worth mentioning aloud: Python's % returns a non-negative result for a positive divisor; Java's % keeps the sign of the dividend. In Java you must normalise with ((x % k) + k) % k.

#8 · Failure modes

#9 · Interview questions

#Stop condition

You know this pattern when you can:

1. build the n+1 prefix array and explain the leading zero,
2. derive the hash-map variant from prefix[i] == running − k,
3. say why counts[0] = 1 is required and what breaks without it,
4. explain why sliding window fails with negative numbers,
5. write the difference array and say it is the inverse operation, and
6. name the invertibility requirement that excludes range minimum.