Limited time: AI code review, hints, mock interviews, whiteboard analysis, and all Pro features are unlocked. Enroll
⏱️ 25 min read

Prefix Sum and Hashing

The pattern: Precompute cumulative totals once, so any range query becomes a single subtraction.

Why this matters in interviews: Half the “count the subarrays that…” questions are a prefix sum plus a hash map, and they look nothing like each other until you see the shape. Once you recognise it, a problem that reads like O(n²) nested loops becomes one pass with a dictionary.

When to Recognize It

How It Works

A prefix sum array stores “total of everything up to here.” Build it once in O(n), then the sum of any range is the difference between two entries.

The only real decision is indexing, and it is worth getting right once rather than re-deriving it every time.

Use the length n + 1 convention with a leading zero. prefix[0] = 0, and prefix[i] holds the sum of the first i elements:

nums   =      3    1    4    1    5
prefix =  0   3    4    8    9   14
          ^
          prefix[0] = 0, the sum of nothing

sum of nums[l..r] inclusive  =  prefix[r + 1] - prefix[l]

sum(1..3) = prefix[4] - prefix[1] = 9 - 3 = 6   -> 1 + 4 + 1 ✓
sum(0..4) = prefix[5] - prefix[0] = 14 - 0 = 14 -> whole array ✓

The alternative is a length n array where prefix[i] includes nums[i]. It works, but then the range sum is prefix[r] - prefix[l-1] and l = 0 reads index -1. In Python that silently wraps to the last element and gives you a wrong answer with no error. In Java and C++ it throws. Either way you end up writing if (l == 0) return prefix[r], and that branch is the bug people ship. The leading zero removes the special case because prefix[l] with l = 0 is a real, meaningful entry.

flowchart LR
    N["nums array"]:::client
    P["prefix array<br/>length n plus 1"]:::data
    Q["range query l to r"]:::service
    A["one subtraction<br/>prefix r plus 1 minus prefix l"]:::service

    N -->|"one pass to build"| P
    Q --> P
    P --> A

    classDef client fill:#4c3a5e,stroke:#818cf8,color:#e2e8f0
    classDef service fill:#1a3a2a,stroke:#4ade80,color:#e2e8f0
    classDef data fill:#3b3520,stroke:#fbbf24,color:#e2e8f0

Code

def build_prefix(nums):
    """prefix[i] = sum of the first i elements. Length n + 1, prefix[0] = 0."""
    prefix = [0] * (len(nums) + 1)
    for i, value in enumerate(nums):
        prefix[i + 1] = prefix[i] + value
    return prefix


def range_sum(prefix, left, right):
    """Sum of nums[left..right], both ends inclusive."""
    return prefix[right + 1] - prefix[left]
long[] buildPrefix(int[] nums) {
    // long, not int: 10^5 elements of 10^9 overflows a 32-bit sum
    long[] prefix = new long[nums.length + 1];
    for (int i = 0; i < nums.length; i++) prefix[i + 1] = prefix[i] + nums[i];
    return prefix;
}

long rangeSum(long[] prefix, int left, int right) {
    return prefix[right + 1] - prefix[left];   // both ends inclusive
}
vector<long long> buildPrefix(const vector<int>& nums) {
    // long long, not int: the running total outgrows 32 bits fast
    vector<long long> prefix(nums.size() + 1, 0);
    for (size_t i = 0; i < nums.size(); i++) prefix[i + 1] = prefix[i] + nums[i];
    return prefix;
}

long long rangeSum(const vector<long long>& prefix, int left, int right) {
    return prefix[right + 1] - prefix[left];   // both ends inclusive
}
function buildPrefix(nums) {
    const prefix = new Array(nums.length + 1).fill(0);
    for (let i = 0; i < nums.length; i++) prefix[i + 1] = prefix[i] + nums[i];
    return prefix;
}

function rangeSum(prefix, left, right) {
    return prefix[right + 1] - prefix[left];   // both ends inclusive
}

1. Prefix Sum Plus Hash Map

This is the highest-value pattern on the page. If you learn one thing here, learn this.

The problem: count the subarrays whose sum is exactly K. Negative numbers allowed, so no sliding window.

The insight. A subarray nums[i..j] has sum running[j] - running[i-1]. You want that to equal K:

running[j] - running[i-1] = K      which rearranges to
running[i-1] = running[j] - K

So standing at position j with a running sum in hand, the number of subarrays ending at j with sum K is exactly the number of earlier positions whose running sum was running - K. Keep a map from running-sum value to how many times you have seen it, and that count is a single lookup.

Walk [1, 2, 3, -2, 5] with K = 3:

seen = {0: 1}   running = 0   count = 0

v=1   running=1   look up 1-3 = -2   not seen, +0   count=0   seen={0:1, 1:1}
v=2   running=3   look up 3-3 =  0   seen once, +1  count=1   seen={0:1, 1:1, 3:1}
v=3   running=6   look up 6-3 =  3   seen once, +1  count=2   seen={0:1, 1:1, 3:1, 6:1}
v=-2  running=4   look up 4-3 =  1   seen once, +1  count=3   seen={..., 4:1}
v=5   running=9   look up 9-3 =  6   seen once, +1  count=4   seen={..., 9:1}

count = 4

The four subarrays are [1,2], [3], [2,3,-2] and [-2,5]. Check them: 3, 3, 3, 3. Every one of them was found by a dictionary lookup rather than a scan, which is where the O(n²) went.

The {0: 1} seed is the detail most people get wrong. It stands for the empty prefix - the running sum before you have consumed anything. Without it, look at the v=2 step above: running is 3, you need a previous prefix of 0, and the only position with prefix 0 is the imaginary one before index 0. Drop the seed and [1,2] goes uncounted, along with every subarray that starts at index 0. The symptom is an answer that is off by exactly the number of valid prefixes of the array, which looks like a random off-by-one and sends people hunting in the wrong place. Seed the map.

Code

from collections import defaultdict

def count_subarrays_with_sum(nums, k):
    """Number of contiguous subarrays summing to exactly k. Negatives allowed."""
    seen = defaultdict(int)
    seen[0] = 1          # the empty prefix - without this you lose every
                         # subarray that starts at index 0
    running = 0
    count = 0
    for value in nums:
        running += value
        count += seen[running - k]   # how many earlier prefixes make up the gap
        seen[running] += 1           # record AFTER counting, never before
    return count
int countSubarraysWithSum(int[] nums, int k) {
    Map<Long, Integer> seen = new HashMap<>();
    seen.put(0L, 1);                 // the empty prefix
    long running = 0;                // long: the running total can overflow int
    int count = 0;
    for (int value : nums) {
        running += value;
        count += seen.getOrDefault(running - k, 0);
        seen.merge(running, 1, Integer::sum);   // record after counting
    }
    return count;
}
int countSubarraysWithSum(const vector<int>& nums, int k) {
    unordered_map<long long, int> seen;
    seen[0] = 1;                     // the empty prefix
    long long running = 0;           // long long: the total can overflow int
    int count = 0;
    for (int value : nums) {
        running += value;
        auto it = seen.find(running - k);
        if (it != seen.end()) count += it->second;
        seen[running]++;             // record after counting
    }
    return count;
}
function countSubarraysWithSum(nums, k) {
    const seen = new Map();
    seen.set(0, 1);                  // the empty prefix
    let running = 0, count = 0;
    for (const value of nums) {
        running += value;
        count += seen.get(running - k) || 0;
        seen.set(running, (seen.get(running) || 0) + 1);   // after counting
    }
    return count;
}

2. Subarray Sum Divisible by K

Same scaffold, different key. A subarray is divisible by K when its two end prefixes leave the same remainder mod K, because then their difference is a multiple of K. So bucket the running sums by remainder and count pairs within each bucket.

Walk [4, 5, 0, -2, -3, 1] with K = 5:

running :  4    9    9    7    4    5
mod 5   :  4    4    4    2    4    0

seen = {0: 1}
r=4  +0  count=0   seen={0:1, 4:1}
r=4  +1  count=1   seen={0:1, 4:2}
r=4  +2  count=3   seen={0:1, 4:3}
r=2  +0  count=3   seen={0:1, 4:3, 2:1}
r=4  +3  count=6   seen={0:1, 4:4, 2:1}
r=0  +1  count=7   -> the seeded 0 pays off again

Negative remainders are the trap. Python’s % already floors toward negative infinity, so -3 % 5 is 2 and you need no fix. Java, C++ and JavaScript all truncate toward zero, so -3 % 5 is -3, and -3 lands in a different bucket than 2 even though they are the same residue class. Normalise with ((x % k) + k) % k in those three. Skip it and the count comes out low on any input with negatives, which is exactly what the test cases check.

Code

def count_subarrays_divisible_by_k(nums, k):
    """Python's % already returns a non-negative remainder for positive k."""
    buckets = [0] * k        # an array beats a dict here, keys are 0..k-1
    buckets[0] = 1           # the empty prefix, remainder 0
    running = 0
    count = 0
    for value in nums:
        running = (running + value) % k
        count += buckets[running]    # every earlier prefix in this bucket pairs up
        buckets[running] += 1
    return count
int countSubarraysDivisibleByK(int[] nums, int k) {
    int[] buckets = new int[k];
    buckets[0] = 1;                  // the empty prefix, remainder 0
    int running = 0, count = 0;
    for (int value : nums) {
        // Java truncates toward zero, so -3 % 5 is -3. Shift it back into 0..k-1
        running = ((running + value) % k + k) % k;
        count += buckets[running];
        buckets[running]++;
    }
    return count;
}
int countSubarraysDivisibleByK(const vector<int>& nums, int k) {
    vector<int> buckets(k, 0);
    buckets[0] = 1;                  // the empty prefix, remainder 0
    int running = 0, count = 0;
    for (int value : nums) {
        // C++ % keeps the sign of the dividend, so normalise into 0..k-1
        running = ((running + value) % k + k) % k;
        count += buckets[running];
        buckets[running]++;
    }
    return count;
}
function countSubarraysDivisibleByK(nums, k) {
    const buckets = new Array(k).fill(0);
    buckets[0] = 1;                  // the empty prefix, remainder 0
    let running = 0, count = 0;
    for (const value of nums) {
        // JS % can return a negative result, so fold it back into 0..k-1
        running = (((running + value) % k) + k) % k;
        count += buckets[running];
        buckets[running]++;
    }
    return count;
}

3. Longest Subarray With Sum K

Counting wants frequencies. Measuring length wants positions, and specifically the earliest one - the further left the matching prefix sits, the longer the subarray. So the map stores running sum to first index, and you never overwrite an existing key.

Walk [1, -1, 5, -2, 3] with K = 3:

first = {0: -1}      a prefix sum of 0 exists at the virtual index -1

i=0  v=1   running=1   need -2   absent              first={0:-1, 1:0}
i=1  v=-1  running=0   need -3   absent   0 already in the map, do NOT overwrite
i=2  v=5   running=5   need  2   absent              first={0:-1, 1:0, 5:2}
i=3  v=-2  running=3   need  0   at -1  -> length 3 - (-1) = 4   best=4
i=4  v=3   running=6   need  3   at  3  -> length 4 - 3 = 1      best stays 4

best = 4, the subarray nums[0..3] = [1, -1, 5, -2]

The seed is {0: -1} here, not {0: 1}. Same idea - the empty prefix - but now it has to carry a position, and the position before index 0 is -1. That choice is what makes i - (-1) come out as i + 1, the correct length for a subarray starting at the front.

Overwriting is the bug. If you update first[running] every time, you keep the latest index for each sum and your answer is the shortest match instead of the longest. Guard the insert.

Equal Numbers of Two Values

A problem asking for “equal numbers of 0 and 1” is this problem wearing a hat. Map one value to +1 and the other to -1; a stretch with equal counts now sums to zero, so you are looking for the longest subarray with sum 0. Nothing else changes.

The general version is the same move: track count(a) - count(b) as you scan and use that difference as the map key. Two positions with the same difference bracket a subarray where a and b appear equally often. It works for “equal vowels and consonants,” for counting rather than measuring (reuse the frequency map from section 1 with k = 0), and for any two-way balance condition.

Code

def longest_subarray_with_sum(nums, k):
    """Length of the longest subarray summing to k, or 0 if there is none."""
    first_index = {0: -1}        # empty prefix sits at the virtual index -1
    running = 0
    best = 0
    for i, value in enumerate(nums):
        running += value
        if running - k in first_index:
            best = max(best, i - first_index[running - k])
        if running not in first_index:
            first_index[running] = i   # keep the EARLIEST index, never overwrite
    return best


def longest_balanced_binary(nums):
    """Longest stretch with equal 0s and 1s: map 0 to -1, then look for sum 0."""
    return longest_subarray_with_sum([1 if v == 1 else -1 for v in nums], 0)
int longestSubarrayWithSum(int[] nums, int k) {
    Map<Long, Integer> firstIndex = new HashMap<>();
    firstIndex.put(0L, -1);          // empty prefix at the virtual index -1
    long running = 0;
    int best = 0;
    for (int i = 0; i < nums.length; i++) {
        running += nums[i];
        Integer at = firstIndex.get(running - k);
        if (at != null) best = Math.max(best, i - at);
        firstIndex.putIfAbsent(running, i);   // earliest index wins
    }
    return best;
}

int longestBalancedBinary(int[] nums) {
    int[] mapped = new int[nums.length];
    for (int i = 0; i < nums.length; i++) mapped[i] = nums[i] == 1 ? 1 : -1;
    return longestSubarrayWithSum(mapped, 0);   // equal counts means sum zero
}
int longestSubarrayWithSum(const vector<int>& nums, int k) {
    unordered_map<long long, int> firstIndex;
    firstIndex[0] = -1;              // empty prefix at the virtual index -1
    long long running = 0;
    int best = 0;
    for (int i = 0; i < (int)nums.size(); i++) {
        running += nums[i];
        auto it = firstIndex.find(running - k);
        if (it != firstIndex.end()) best = max(best, i - it->second);
        // emplace is a no-op if the key exists, which keeps the earliest index
        firstIndex.emplace(running, i);
    }
    return best;
}

int longestBalancedBinary(const vector<int>& nums) {
    vector<int> mapped(nums.size());
    for (size_t i = 0; i < nums.size(); i++) mapped[i] = nums[i] == 1 ? 1 : -1;
    return longestSubarrayWithSum(mapped, 0);   // equal counts means sum zero
}
function longestSubarrayWithSum(nums, k) {
    const firstIndex = new Map([[0, -1]]);   // empty prefix at virtual index -1
    let running = 0, best = 0;
    for (let i = 0; i < nums.length; i++) {
        running += nums[i];
        if (firstIndex.has(running - k))
            best = Math.max(best, i - firstIndex.get(running - k));
        if (!firstIndex.has(running)) firstIndex.set(running, i);  // earliest wins
    }
    return best;
}

function longestBalancedBinary(nums) {
    const mapped = nums.map(v => (v === 1 ? 1 : -1));
    return longestSubarrayWithSum(mapped, 0);   // equal counts means sum zero
}

4. Two-Dimensional Prefix Sums

For a grid, P[i][j] holds the sum of the rectangle from the top-left corner down to (but not including) row i and column j. Same leading-zero trick as 1D, now on both axes, so P is (m+1) × (n+1).

Build it with inclusion-exclusion rather than guessing at it. To cover the rectangle ending at cell (i-1, j-1):

Querying works the same way in reverse. Start with everything up to the bottom-right corner, cut off the strip above and the strip to the left, then notice the top-left corner block got removed twice and add it back:

grid        P (4 x 4, leading row and column of zeros)
1 2 3        0   0   0   0
4 5 6        0   1   3   6
7 8 9        0   5  12  21
             0  12  27  45

P[2][2] = 12  -> the top-left 2x2 block, 1 + 2 + 4 + 5 ✓
P[3][3] = 45  -> the whole grid, 1 through 9 ✓

Query the bottom-right 2x2, rows 1-2 and columns 1-2, which is 5 + 6 + 8 + 9 = 28:
    P[3][3] - P[1][3] - P[3][1] + P[1][1]
  =   45    -    6    -   12    +    1     = 28 ✓

Build is O(m·n), every query after that is four array reads. That is the whole appeal: 10⁵ queries on a 1000 × 1000 grid cost the same per query as the first one.

Code

def build_prefix_2d(grid):
    """prefix[i][j] = sum of grid rows 0..i-1 and columns 0..j-1."""
    rows, cols = len(grid), len(grid[0])
    prefix = [[0] * (cols + 1) for _ in range(rows + 1)]
    for i in range(1, rows + 1):
        for j in range(1, cols + 1):
            prefix[i][j] = (grid[i - 1][j - 1]
                            + prefix[i - 1][j]      # the block above
                            + prefix[i][j - 1]      # the block to the left
                            - prefix[i - 1][j - 1]) # counted twice, remove once
    return prefix


def region_sum(prefix, r1, c1, r2, c2):
    """Sum of the rectangle with corners (r1, c1) and (r2, c2), inclusive."""
    return (prefix[r2 + 1][c2 + 1] - prefix[r1][c2 + 1]
            - prefix[r2 + 1][c1] + prefix[r1][c1])
long[][] buildPrefix2D(int[][] grid) {
    int rows = grid.length, cols = grid[0].length;
    long[][] prefix = new long[rows + 1][cols + 1];
    for (int i = 1; i <= rows; i++)
        for (int j = 1; j <= cols; j++)
            prefix[i][j] = grid[i - 1][j - 1]
                         + prefix[i - 1][j]          // block above
                         + prefix[i][j - 1]          // block to the left
                         - prefix[i - 1][j - 1];     // overlap, counted twice
    return prefix;
}

long regionSum(long[][] prefix, int r1, int c1, int r2, int c2) {
    return prefix[r2 + 1][c2 + 1] - prefix[r1][c2 + 1]
         - prefix[r2 + 1][c1] + prefix[r1][c1];
}
vector<vector<long long>> buildPrefix2D(const vector<vector<int>>& grid) {
    int rows = grid.size(), cols = grid[0].size();
    vector<vector<long long>> prefix(rows + 1, vector<long long>(cols + 1, 0));
    for (int i = 1; i <= rows; i++)
        for (int j = 1; j <= cols; j++)
            prefix[i][j] = grid[i - 1][j - 1]
                         + prefix[i - 1][j]          // block above
                         + prefix[i][j - 1]          // block to the left
                         - prefix[i - 1][j - 1];     // overlap, counted twice
    return prefix;
}

long long regionSum(const vector<vector<long long>>& prefix,
                    int r1, int c1, int r2, int c2) {
    return prefix[r2 + 1][c2 + 1] - prefix[r1][c2 + 1]
         - prefix[r2 + 1][c1] + prefix[r1][c1];
}
function buildPrefix2D(grid) {
    const rows = grid.length, cols = grid[0].length;
    const prefix = Array.from({ length: rows + 1 }, () => new Array(cols + 1).fill(0));
    for (let i = 1; i <= rows; i++)
        for (let j = 1; j <= cols; j++)
            prefix[i][j] = grid[i - 1][j - 1]
                         + prefix[i - 1][j]          // block above
                         + prefix[i][j - 1]          // block to the left
                         - prefix[i - 1][j - 1];     // overlap, counted twice
    return prefix;
}

function regionSum(prefix, r1, c1, r2, c2) {
    return prefix[r2 + 1][c2 + 1] - prefix[r1][c2 + 1]
         - prefix[r2 + 1][c1] + prefix[r1][c1];
}

5. Difference Arrays - Prefix Sums Run Backwards

Prefix sums answer “many range reads on a fixed array.” Flip the problem: many range writes, then one read of the whole thing. Add 3 to every element between index 1 and 3, add 2 between 0 and 1, and so on, then print the array. Applying each update element by element is O(n) per update and O(q·n) overall.

A difference array records only the edges of each update. diff[l] += v says “from here on, everything is v higher.” diff[r+1] -= v cancels it just past the end. Replay the whole thing at the finish with one prefix sum.

n = 5, array starts at all zeros, diff has length n + 1 = 6

update +3 on [1, 3]:  diff[1] += 3, diff[4] -= 3
    diff = [0, 3, 0, 0, -3, 0]
update +2 on [0, 1]:  diff[0] += 2, diff[2] -= 2
    diff = [2, 3, -2, 0, -3, 0]

prefix sum of diff, dropping the final slot:
    index:  0  1  2  3  4
    value:  2  5  3  3  0

check index 1: it sits in both ranges, 3 + 2 = 5 ✓
check index 4: in neither range, 0 ✓

O(1) per update, O(n) once at the end. The r+1 slot is why the array is length n + 1 - an update that runs to the last element writes its cancel marker one past the array, and you want somewhere harmless to put it rather than a bounds check.

The 2D version exists too: four corner marks per rectangle update (+v, -v, -v, +v), then a 2D prefix sum to materialise the grid. Same idea, same inclusion-exclusion as section 4.

Code

def apply_range_updates(n, updates):
    """updates = [(left, right, value)], all ranges inclusive. Returns the array."""
    diff = [0] * (n + 1)         # the extra slot absorbs right + 1 == n
    for left, right, value in updates:
        diff[left] += value         # everything from here on goes up by value
        diff[right + 1] -= value    # cancel it just past the range
    result = []
    running = 0
    for i in range(n):
        running += diff[i]
        result.append(running)
    return result
int[] applyRangeUpdates(int n, int[][] updates) {
    int[] diff = new int[n + 1];     // extra slot absorbs right + 1 == n
    for (int[] u : updates) {
        diff[u[0]] += u[2];         // u = {left, right, value}
        diff[u[1] + 1] -= u[2];     // cancel just past the range
    }
    int[] result = new int[n];
    int running = 0;
    for (int i = 0; i < n; i++) {
        running += diff[i];
        result[i] = running;
    }
    return result;
}
vector<int> applyRangeUpdates(int n, const vector<array<int,3>>& updates) {
    vector<int> diff(n + 1, 0);      // extra slot absorbs right + 1 == n
    for (const auto& u : updates) {
        diff[u[0]] += u[2];         // u = {left, right, value}
        diff[u[1] + 1] -= u[2];     // cancel just past the range
    }
    vector<int> result(n);
    int running = 0;
    for (int i = 0; i < n; i++) {
        running += diff[i];
        result[i] = running;
    }
    return result;
}
function applyRangeUpdates(n, updates) {
    const diff = new Array(n + 1).fill(0);   // extra slot absorbs right + 1 === n
    for (const [left, right, value] of updates) {
        diff[left] += value;                 // from here on, up by value
        diff[right + 1] -= value;            // cancel just past the range
    }
    const result = [];
    let running = 0;
    for (let i = 0; i < n; i++) {
        running += diff[i];
        result.push(running);
    }
    return result;
}

Complexity

Variant Build Per query Space
1D prefix sum O(n) O(1) O(n)
2D prefix sum O(m·n) O(1), four reads O(m·n)
Prefix sum + hash map O(n) one pass answered during the pass O(n)
Difference array O(1) per update O(n) to materialise once O(n)
Fenwick tree (the escalation) O(n log n) O(log n) read and write O(n)

The hash-map variant has no separate query phase - it answers the question while building, which is why it reads as a single loop. Worst-case space is O(n) because every running sum can be distinct.

Common Mistakes

Practice Problems

Key Takeaways

Free system design + DSA prep. If it helped you crack an interview, consider supporting.

SensAI SensAI
Beta
Listening...
Tap mic to stop voice mode

Shape what we build next

Every piece of feedback is read by the team and directly influences our roadmap.

What type of feedback?

Install SystemCraft

Add to your home screen for instant access, offline reading, and a distraction-free experience.

Offline reading Faster loads No browser tabs App-like feel

Unlock AI Features

One click to activate - no payment, no credit card. Just sign in and you're in.

AI code review and hints
SensAI chat assistant
AI mock interviews
Whiteboard analysis
100% free during early access