DSA Notes · chapter 10 · Java Live Code

A prefix array turns a range into a subtraction. A HashMap of prefix frequencies turns “subarray sum equals K” into a lookup. Store the first index of a prefix when you want the longest zero-sum slice. Nice subarrays in chapter 07 count odds with a window; that is not this numeric prefix map, even though both can be phrased as exact-K.

10 · prefix sum

Range, then exact K, then the first-index map

Build pref[0] = 0 and pref[i] = a[0] + … + a[i−1] so sum(l..r) = pref[r+1] − pref[l]. Use long keys when n · 1e9 can overflow an int. A sliding window on the raw values is legal only when every value is non-negative and the predicate is monotone.

Range sum→ Sum equals K→ Longest sum 0

Range sum from a prefix array

Recognize it from

Many queries “sum of a[l..r] inclusive” on a static array. Immutable after build. If the array mutates between queries, you need a Fenwick / segment tree — not this card.

What it actually does

The simple method re-adds the slice on every query so you see the O(n) cost. The interview method spends O(n) once building pref, then answers in O(1). Indexing: pref[i] is the sum of the first i elements, so the inclusive range [l, r] is pref[r + 1] − pref[l]. Empty array and l > r are the usual Live Code guards.

Simple — read this first

public int rangeSum(int[] a, int l, int r) {
    int s = 0;
    for (int i = l; i <= r; i++) {
        // every query rescans — fine for one query, painful for q of them
        s += a[i];
    }
    return s;
}

Interview — type this

class NumArray {
    private final long[] pref;
    NumArray(int[] a) {
        pref = new long[a.length + 1]; // pref[0]=0 so sum(0..r) needs no branch
        for (int i = 0; i < a.length; i++) {
            pref[i + 1] = pref[i] + a[i];
        }
    }
    int sumRange(int l, int r) {
        // pref[r+1] is sum of a[0..r]; pref[l] is sum of a[0..l-1]
        return (int) (pref[r + 1] - pref[l]);
    }
}

Example 1 — simple

Input a = [1, 2, 3], query indices 1..2 inclusive.

index 0 1 2 a 1 2 3 query 1..2 → 2+3

Loop l=1 to r=2, and the prefix that would replace it
i	add a[i]	running
1	2	2
2	3	5

Answer 5. Prefix form: pref = [0, 1, 3, 6], pref[3] − pref[1] = 6 − 1 = 5.

Example 2 — every step

Build pref[] for a = [2, 1, 3, 4], then three queries. Every prefix write, then every query.

a 2 1 3 4 i 0 1 2 3

Build — pref[i+1] = pref[i] + a[i]
i	a[i]	pref[i]	pref[i+1]	pref so far
—	—	—	pref[0]=0	[0]
0	2	0	2	[0, 2]
1	1	2	3	[0, 2, 3]
2	3	3	6	[0, 2, 3, 6]
3	4	6	10	[0, 2, 3, 6, 10]

Three queries — each is one subtraction
query [l,r]	meaning	pref[r+1] − pref[l]	answer
[0, 0]	just 2	pref[1] − pref[0] = 2 − 0	2
[1, 2]	1+3	pref[3] − pref[1] = 6 − 2	4
[0, 3]	whole array	pref[4] − pref[0] = 10 − 0	10

Answers 2, 4, 10.

TC build O(n) TC query O(1) SC O(n)

Why pref[0] = 0 A range that starts at index 0 is pref[r+1] − pref[0]. Without the leading zero you special-case l == 0 on every query. long on the prefix avoids silent int overflow when they throw 1e9 values at you.

Common mistakes

Writing pref[r] − pref[l] and dropping a[r] or double-dropping a[l] depending on whether pref is inclusive.
1-based vs 0-based mix: say out loud which you built.
Rebuilding the prefix inside each query — that is the simple loop in disguise.

Notebook problems for this topic

Problem	Pattern	Links
Exact sum / subarray sum K clues	Range is subtraction; exact K is the map in the next card	clue · clue

Subarray sum equals K — map of prefix frequencies

Recognize it from

Count (or existence) of contiguous subarrays whose values sum to K. Negatives and zeros allowed. If they ask for the longest such subarray, store first index instead of frequency (next card, and the TUF maximum-size sibling). Nice subarrays count exactly K odds with a window — different resource, see the note below.

What it actually does

If pref[r] − pref[l] = K then pref[l] = pref[r] − K. While you walk r, the map stores how many earlier prefixes equal that need. Seed freq[0] = 1 so a prefix that itself equals K counts as a subarray starting at index 0.

Update the map after you query it, so you do not pair an index with itself unless K is 0 and that is intended. Simple nested loops make the O(n²) cost visible; interview is one pass.

Simple — read this first

public int subarraySum(int[] a, int k) {
    int ans = 0;
    for (int l = 0; l < a.length; l++) {
        int s = 0;
        for (int r = l; r < a.length; r++) {
            s += a[r];
            if (s == k) ans++;
        }
    }
    return ans;
}

Interview — type this

public int subarraySum(int[] a, int k) {
    Map<Long, Integer> freq = new HashMap<>();
    freq.put(0L, 1);                 // empty prefix: subarrays that start at 0
    long pref = 0;
    int ans = 0;
    for (int x : a) {
        pref += x;
        ans += freq.getOrDefault(pref - k, 0);
        freq.put(pref, freq.getOrDefault(pref, 0) + 1);
    }
    return ans;
}

Example 1 — simple

Input a = [1, 1, 1], k = 2.

index 0 1 2 a 1 1 1 k = 2

Nested running sum — every [l,r]
l	r	sum	== 2?
0	0	1	no
0	1	2	yes
0	2	3	no
1	1	1	no
1	2	2	yes
2	2	1	no

Answer 2 — [1,1] at 0..1 and at 1..2.

Example 2 — every step

Input a = [1, 2, 3, −2, 5], k = 3. Every prefix, including the freq[0] = 1 seed.

index 0 1 2 3 4 a 1 2 3 −2 5 k = 3

Query freq[pref − k] before inserting pref
i	x	pref	need = pref−3	freq[need]	ans	freq after put
—	—	0	—	—	0	{0:1}
0	1	1	−2	0	0	{0:1, 1:1}
1	2	3	0	1	1	{0:1, 1:1, 3:1}
2	3	6	3	1	2	{0:1, 1:1, 3:1, 6:1}
3	−2	4	1	1	3	{…, 4:1}
4	5	9	6	1	4	{…, 9:1}

Answer 4: [1,2], [3], [2,3,−2], [−2,5]. The hit at i=1 is exactly why freq[0]=1 exists — prefix 3 minus K is the empty prefix.

TC brute O(n²) TC map O(n) average SC O(n)

Why a frequency map, not a window Negatives mean a longer window can have a smaller sum, so left may not move monotonically. The map does not assume sign. All-positive + “sum ≥ K shortest” can still be a window — ask about signs. Nice subarrays (ch.07 / ch.05) use atMost on a 0/1 odd-count, not this prefix of the raw values.

Common mistakes

Forgetting freq[0] = 1, so subarrays that start at index 0 never count.
Putting pref into the map before the lookup, which double-counts when K = 0.
Using int prefixes when n · 1e9 overflows.

Notebook problems for this topic

Problem	Pattern	Links
Subarray sum = K / exact sum	Prefix frequency map	clue · clue
Maximum size subarray sum equals k	Same prefix, store first index for length	cheat card
Nice subarrays (odds, not this prefix)	Window atMost(K) − atMost(K−1) on odd bits	Java in ch.05 · cheat card

Longest subarray with sum 0 — first-occurrence index

Recognize it from

Longest contiguous slice whose values sum to 0 (negatives allowed). Same engine as sum = K with K = 0, but the map stores the first index of each prefix so j − i is maximised. Count of zero-sum subarrays would store frequencies instead.

What it actually does

pref[j] − pref[i] = 0 means the slice (i .. j] sums to 0. If you keep the leftmost index where each prefix appeared, a later repeat of that prefix gives the longest slice ending here. Seed first[0] = −1 so a prefix that is itself 0 (sum from the start) has length j − (−1) = j + 1.

Do not overwrite an earlier index when the same prefix appears again — that would shorten the answer. The simple nested loop is the check; the interview map is what you type.

Simple — read this first

public int longestZeroSum(int[] a) {
    int best = 0;
    for (int l = 0; l < a.length; l++) {
        int s = 0;
        for (int r = l; r < a.length; r++) {
            s += a[r];
            if (s == 0) best = Math.max(best, r - l + 1);
        }
    }
    return best;
}

Interview — type this

public int longestZeroSum(int[] a) {
    Map<Long, Integer> first = new HashMap<>();
    first.put(0L, -1);               // prefix 0 lives before index 0
    long pref = 0;
    int best = 0;
    for (int i = 0; i < a.length; i++) {
        pref += a[i];
        if (first.containsKey(pref)) {
            best = Math.max(best, i - first.get(pref));
        } else {
            // keep the earliest index; a later one would only shorten
            first.put(pref, i);
        }
    }
    return best;
}

Example 1 — simple

Input a = [1, −1]. The whole array sums to 0.

index 0 1 a 1 −1

Nested sums, and the prefix view
l	r	sum	length if 0
0	0	1	—
0	1	0	2
1	1	−1	—

Answer 2. Prefix: after index 0, pref=1 stored at 0; after index 1, pref=0, first[0]=−1, length 1 − (−1) = 2.

Example 2 — every step

Input a = [1, 2, −3, 3]. First time prefix hits 0 vs a later repeat of prefix 3.

index 0 1 2 3 a 1 2 −3 3

first-occurrence map — do not overwrite prefix 3 at i=3
i	x	pref	first.get(pref)	length	best	first after
—	—	0	−1 (seed)	—	0	{0: −1}
0	1	1	absent → put 0	—	0	{0:−1, 1:0}
1	2	3	absent → put 1	—	0	{…, 3:1}
2	−3	0	−1 (seed, not i=2)	2−(−1)=3	3	unchanged; keep −1
3	3	3	1 (first, not overwritten)	3−1=2	3	unchanged

Answer 3 — [1, 2, −3] from the prefix-0 hit. The later slice [−3, 3] also sums to 0 (length 2) because prefix 3 repeats; keeping the first index of 3 is what gives 2, and the earlier prefix-0 walk is what gives 3. If you overwrote first[0] = 2 when prefix returned to 0, a later return to 0 would measure from 2 instead of from the start.

TC brute O(n²) TC map O(n) average SC O(n)

Why first index, not a count Length wants the leftmost partner of this prefix. Count of zero-sum subarrays would add freq[pref] instead, like the previous card with K = 0. TUF maximum-size subarray sum equals k is this map with need = pref − k.

Common mistakes

Overwriting the first index when the prefix repeats.
Seeding first[0] = 0 instead of −1, which undercounts a zero-sum prefix by one (or misses it if you also skip equals).
Using a shrinking window — negatives break the monotone budget.

Notebook problems for this topic

Problem	Pattern	Links
Longest subarray sum = 0	Prefix → first index	cheat card
Maximum size subarray sum equals k	First-index map, need = pref − k	cheat card

Range, then exact K, then the first-index map

Range sum from a prefix array

Recognize it from

What it actually does

Example 1 — simple

Example 2 — every step

Notebook problems for this topic

Subarray sum equals K — map of prefix frequencies

Recognize it from

What it actually does

Example 1 — simple

Example 2 — every step

Notebook problems for this topic

Longest subarray with sum 0 — first-occurrence index

Recognize it from

What it actually does

Example 1 — simple

Example 2 — every step

Notebook problems for this topic

See also on this chapter