Om's Brain

3. Prefix Sum

16 min read

Introduction

Often these problems ask for either count or length (min/max) of a subarray based on some mathematical condition — subarray sum, divisibility, mod, vowel counting etc.

At first glance you’ll be tempted to use Sliding Window, but quickly realize it’s not possible — either elements are -ve or some other conditions break it.

For these problems, we use Prefix Sum.

4 Sections

  • Section 1 — Standard prefix sum problems
  • Section 2 — Divisibility and modulo
  • Section 3 — Prefix sum + XOR
  • Section 4 — 2D Prefix Sum

TC: O(n) | SC: O(n) for almost all problems.

💡 Basic Idea

Intro problem: 560. Subarray Sum Equals K

  • psum_i = current running subarray sum
  • If in the past we found psum_j stored in hashmap such that:
psum_i - psum_j = K

→ array from [j...i] has sum = K — that’s what we want!

So after accumulating psum_i, look for psum_j in map:

psum_j = psum_i - K

📋 Template

1. Maintain prefix_sum = 0  (this is psum_i)
2. Setup unordered_map
3. Variable to store answer = 0
4. Initialize map[0]:
      a) COUNT  → map[0] = 1    (if psum_i - K = 0, entire subarray is answer)
      b) LENGTH → map[0] = -1   (length = i - map[0] = i - (-1) = i+1)
5. Iterate array, accumulate pSum
6. Check if pSum - K exists in map → add to answer
7. Update map:
      COUNT  → countMap[pSum]++
      LENGTH → lenMap[pSum] = i   (store first occurrence only)

Remember

  • COUNT → map[0] = 1 , always map[sum]++
  • LENGTH → map[0] = -1, store first occurrence only (if not exists)
  • Warm-up: 1480. Running Sum of 1d Array

Section 1 — Standard Prefix Sum

Warmup problems: 303. Range Sum Query | 560. Subarray Sum Equals K | 1310. XOR Queries of a Subarray

560. Subarray Sum Equals K

Just follow the template step by step.

int subarraySum(vector<int>& nums, int k) {
    unordered_map<int, int> countMap;
    int pSum = 0, ans = 0;
    countMap[0] = 1;
    for (int i = 0; i < nums.size(); ++i) {
        pSum += nums[i];
        if (countMap.count(pSum - k))
            ans += countMap[pSum - k];
        countMap[pSum]++;
    }
    return ans;
}
// TC - O(n) | SC - O(n)

2559. Count Vowel Strings in Ranges

Mark each string index as 1 if it starts AND ends with a vowel, else 0. Then build prefix sum → answer each query in O(1).

vector<int> vowelStrings(vector<string>& words, vector<vector<int>>& queries) {
    int n = words.size();
    vector<int> arr(n, 0);
    string vowels = "aeiou";
    for (int i = 0; i < n; ++i) {
        int l = words[i].size() - 1;
        if (vowels.find(words[i][0]) != string::npos &&
            vowels.find(words[i][l]) != string::npos)
            arr[i] = 1;
    }
    vector<int> psum(1 + n, 0);
    for (int i = 0; i < n; ++i)
        psum[i + 1] = arr[i] + psum[i];
 
    vector<int> ans(queries.size());
    for (int i = 0; i < queries.size(); ++i)
        ans[i] = psum[queries[i][1] + 1] - psum[queries[i][0]];
    return ans;
}
// TC - O(n) | SC - O(n)

325. Maximum Size Subarray Sum Equals k

Same as 560 but asking longest subarray size instead of count.

  • Init lenMap[0] = -1
  • Only update index if pSum doesn’t exist in map (earlier index = longer length)
int maxSubArrayLen(vector<int>& nums, int k) {
    unordered_map<int, int> lenMap;
    int pSum = 0, ans = 0;
    lenMap[0] = -1;
    for (int i = 0; i < nums.size(); ++i) {
        pSum += nums[i];
        if (lenMap.count(pSum - k))
            ans = max(ans, i - lenMap[pSum - k]);
        if (lenMap.find(pSum) == lenMap.end())  // update only if not exists
            lenMap[pSum] = i;
    }
    return ans;
}
// TC - O(n) | SC - O(n)

1248. Count Number of Nice Subarrays

Same as 560 but only interested in odd numbers. Convert array: odd → 1, even → 0, then proceed exactly like 560.

930. Binary Subarrays With Sum

Exactly same as 1248.

2364. Count Number of Bad Pairs

Total pairs = n*(n-1)/2 Remove pairs that satisfy the rule: i - nums[i] == j - nums[j]

long long countBadPairs(vector<int>& nums) {
    long long n = nums.size();
    long long ans = (n * (n - 1)) >> 1;
    unordered_map<int, long long> m;
    for (int i = 0; i < n; ++i) {
        int diff = i - nums[i];
        ans -= m[diff];
        ++m[diff];
    }
    return ans;
}
// TC - O(n) | SC - O(n)

1658. Minimum Operations to Reduce X to Zero

Remove from left or right → leftover is a subarray. Minimize operations = maximize leftover subarray size.

[1,1,4,2,3], x = 5
total sum = 10, target subarray sum = total - x = 10 - 5 = 5
Find largest subarray with sum = 5

int minOperations(vector<int>& nums, int x) {
    int target = -x;
    for (int i : nums) target += i;
    int n = nums.size();
    if (target == 0) return n;
 
    int ans = INT_MIN, left = 0;
    unsigned long long sum = 0;
    for (int right = 0; right < n; ++right) {
        sum += nums[right];
        while (sum >= (unsigned long long)target) {
            if (sum == (unsigned long long)target)
                ans = max(ans, right - left + 1);
            sum -= nums[left++];
        }
    }
    return ans == INT_MIN ? -1 : n - ans;
}
// TC - O(n) | SC - O(1)

Section 2 — Prefix Sum & Division / Modulo

For divisibility problems (subarray divisible by K):

psum_i - psum_j = q * K
→ take modulo on both sides:
psum_i % K == psum_j % K

So track remainders in the map: countMap[psum % K]++

Negative Remainder Fix

C++ gives -5 % 2 = -1 but math says it should be 1. Fix: rem = ((sum % K) + K) % K For +ve remainders this doesn’t hurt either.

974. Subarray Sums Divisible by K

At each iteration look for (psum + i) % K and fix negative remainder with +K.

int subarraysDivByK(vector<int>& A, int K) {
    int ans = 0, sum = 0;
    unordered_map<int, int> countMap;
    countMap[0] = 1;
    for (int i : A) {
        sum = (((sum + i) % K) + K) % K;  // fix negative remainder
        if (countMap.count(sum))
            ans += countMap[sum];
        countMap[sum]++;
    }
    return ans;
}
// TC - O(n) | SC - O(K)

1497. Check If Array Pairs Are Divisible by k

Pair remainder r with (k - r) % k. If all remainders find a partner → return true.

bool canArrange(vector<int>& arr, int k) {
    unordered_map<int, int> rem_map;
    for (int i : arr) {
        int r = ((i % k) + k) % k;
        if (rem_map[(k - r) % k] > 0)
            --rem_map[(k - r) % k];
        else
            ++rem_map[r];
    }
    int sum = 0;
    for (auto& i : rem_map) sum += i.second;
    return sum == 0;  // all remainders found their partner
}
// TC - O(n) | SC - O(k)

1590. Make Sum Divisible by P

Find smallest subarray with sum = totalSum % p. Removing it makes the rest divisible by p.

Unlike 325 (longest), here we want smallest → overwrite existing entries in map

int minSubarray(vector<int>& nums, int p) {
    long long sum = accumulate(nums.begin(), nums.end(), 0LL);
    int k = sum % p;
    if (k == 0) return 0;
 
    unordered_map<int, int> lenMap;
    lenMap[0] = -1;
    int psum = 0, n = nums.size(), ans = n;
    for (int i = 0; i < n; ++i) {
        psum = (psum + nums[i]) % p;
        auto it = lenMap.find((psum - k + p) % p);
        if (it != lenMap.end())
            ans = min(ans, i - it->second);
        lenMap[psum] = i;  // overwrite — want smallest, so latest index is better
    }
    return ans == n ? -1 : ans;
}
// TC - O(n) | SC - O(n)

523. Continuous Subarray Sum

Subarray is a multiple of K + length at least 2. Multiple of K → remainder = 0.

bool checkSubarraySum(vector<int>& nums, int k) {
    unordered_map<int, int> m;  // {remainder → index}
    int sum = 0;
    m[0] = -1;
    for (int i = 0; i < nums.size(); ++i) {
        sum += nums[i];
        sum %= k;
        if (m.count(sum)) {
            if (i - m[sum] > 1)  // imp: length must be > 1
                return true;
        } else
            m[sum] = i;
    }
    return false;
}
// TC - O(n) | SC - O(k)

2575. Find the Divisibility Array of a String

Can’t keep accumulating — overflows even long long.

ith number  = (psum * 10 + ith_digit) % m
→ do modulo at each step to keep psum in range!

vector<int> divisibilityArray(string word, int m) {
    int n = word.size();
    vector<int> ans(n, 0);
    long long psum = 0;
    for (int i = 0; i < n; ++i) {
        psum = psum * 10 + (word[i] - '0');
        psum %= m;
        if (psum == 0) ans[i] = 1;
    }
    return ans;
}
// TC - O(n) | SC - O(1)

2845. Count of Interesting Subarrays

Mix of two ideas:

  1. Convert to binary array (same as 930/1248)
  2. Apply divisibility rule
long long countInterestingSubarrays(vector<int>& nums, int modulo, int k) {
    int n = nums.size();
    // Step 1: convert → 1 if nums[i] % modulo == k, else 0
    for (int i = 0; i < n; ++i)
        nums[i] = (nums[i] % modulo) == k;
 
    // Step 2: count with modulo trick
    long long cnt = 0, ans = 0;
    unordered_map<long long, long long> countMap;
    countMap[0] = 1;
    for (int i = 0; i < n; ++i) {
        cnt += nums[i];
        cnt %= modulo;
        if (countMap.count((cnt - k + modulo) % modulo))
            ans += countMap[(cnt - k + modulo) % modulo];
        countMap[cnt]++;
    }
    return ans;
}
// TC - O(n) | SC - O(n)

Section 3 — Prefix Sum & XOR

Quick Identifier

Problem asks about even/odd occurrence of something in a subarray → try XOR bitmask.

We use XOR property: same value XOR’d twice = 0. Track a mask where each bit represents odd/even count of a character.

Same mask at two indices → everything between them cancelled → all even occurrences.

mask ^= (1 << char_index)   // toggle bit for each character seen

Template:

mask[0] = -1   (length problems)
mask[0] = 1    (count problems — rare)

1442. Count Triplets That Can Form Two Arrays of Equal XOR

If xor[i..k] = 0, then any j in between works → count pairs.

1915. Number of Wonderful Substrings

Input: string with chars a..j. Substrings with at most 1 odd character.

At first tempted to use Sliding Window, but dry run abb:

  • After 1st b: two odd chars → invalid, move left
  • After 2nd b: suddenly abb is valid (a is odd, b is even) → left pointer can become valid again, sliding window breaks.

Approach: Bitmask XOR for chars a..j (10 bits)

Even occurrence → same mask seen before → add to count. Atmost 1-odd → try flipping each of the 10 bits → check if that mask exists.

1542. Find Longest Awesome Substring

Same as 1915 but with digits 0..9. Palindrome property: all even OR at most 1 odd (middle char).

int longestAwesome(string s) {
    unordered_map<int, int> lenMap;
    lenMap[0] = -1;
    int mask = 0, ans = 1;
    for (int i = 0; i < s.size(); ++i) {
        mask ^= (1 << (s[i] - '0'));
        if (lenMap.count(mask))
            ans = max(ans, i - lenMap[mask]);         // all even
        for (int j = 0; j < 10; ++j) {               // exactly 1 odd
            if (lenMap.count(mask ^ (1 << j)))
                ans = max(ans, i - lenMap[mask ^ (1 << j)]);
        }
        if (!lenMap.count(mask)) lenMap[mask] = i;   // store first occurrence
    }
    return ans;
}
// TC - O(10n) = O(n) | SC - O(2^10) = O(1)

1371. Find the Longest Substring Containing Vowels in Even Counts

Easier — no odd case needed, only find longest → record earlier occurrence.

int findTheLongestSubstring(string s) {
    unordered_map<int, int> lenMap;
    lenMap[0] = -1;
    int mask = 0, ans = 0;
    unordered_map<char, int> toIdx = {{'a',0},{'e',1},{'i',2},{'o',3},{'u',4}};
    for (int i = 0; i < s.size(); ++i) {
        char c = s[i];
        if (toIdx.count(c))
            mask ^= (1 << toIdx[c]);
        if (lenMap.count(mask))
            ans = max(ans, i - lenMap[mask]);
        else
            lenMap[mask] = i;
    }
    return ans;
}
// TC - O(n) | SC - O(2^5) = O(1)

Section 4 — 2D Prefix Sum

Used for operations on sub-matrices (sum, min, max in range).

Two operations:

  1. Compute psum at cell (i, j)
  2. Get sum between (r1, c1) and (r2, c2)

Build psum

psum[i][j] = psum[i-1][j] + psum[i][j-1] - psum[i-1][j-1]  +  arr[i][j]

[i-1][j-1] gets added twice (once from left, once from top) → subtract once.

Using 1-indexed psum (size m+1 x n+1):

// Build
for (int i = 0; i < m; ++i)
    for (int j = 0; j < n; ++j)
        psum[i+1][j+1] = psum[i+1][j] + psum[i][j+1] - psum[i][j] + arr[i][j];

Remember

psum size is always (m+1) x (n+1) — one extra row and column

Get psum of submatrix (r1,c1) → (r2,c2)

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

Since we stored psum(0,0) as psum(1,1) → shift all coordinates +1:

// Query (0-indexed input)
auto getSum = [&](int r1, int c1, int r2, int c2) {
    return psum[r2+1][c2+1] - psum[r1][c2+1] - psum[r2+1][c1] + psum[r1][c1];
};

304. Range Sum Query 2D - Immutable

Apply the 2D template directly.

class NumMatrix {
    vector<vector<int>> psum;
public:
    NumMatrix(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        psum.assign(m+1, vector<int>(n+1, 0));
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                psum[i+1][j+1] = psum[i+1][j] + psum[i][j+1] - psum[i][j] + grid[i][j];
    }
    int sumRegion(int r1, int c1, int r2, int c2) {
        return psum[r2+1][c2+1] - psum[r1][c2+1] - psum[r2+1][c1] + psum[r1][c1];
    }
};
// Build TC - O(m*n) | Query TC - O(1) | SC - O(m*n)

1314. Matrix Block Sum

At each cell form a valid rectangle of size 2k (k on left, right, up, down). Compute psum of input → for each cell clamp bounds → query in standard 2D way.

vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
    int m = mat.size(), n = mat[0].size();
    vector<vector<int>> psum(m+1, vector<int>(n+1, 0));
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
            psum[i+1][j+1] = psum[i+1][j] + psum[i][j+1] - psum[i][j] + mat[i][j];
 
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j) {
            int r1 = max(i-k, 0), c1 = max(j-k, 0);
            int r2 = min(i+k+1, m), c2 = min(j+k+1, n);
            mat[i][j] = psum[r2][c2] - psum[r2][c1] - psum[r1][c2] + psum[r1][c1];
        }
    return mat;
}
// TC - O(m*n) | SC - O(m*n)

2132. Stamping the Grid

Empty cells = 0. Return true if every empty cell is covered by some stamp.

Step 1: At each cell, check if stamp-size rectangle is all empty (2D psum = 0) → if yes, stamp it. Step 2: Use 2D Differential Array to mark stamps efficiently. Step 3: Build 2D psum of stamps → check every empty cell is covered.

2D Differential Array trick

To mark rectangle (r1,c1) → (r2,c2):

diff[r1][c1]++;
diff[r1][c2+1]--;
diff[r2+1][c1]--;
diff[r2+1][c2+1]++;

Then 2D psum of diff tells how many stamps cover each cell.

1D first

Array [0,0,0,0,0,0], update range [1,4]: Diff = [0,1,0,0,0,-1,0] → psum of diff = [0,1,1,1,1,0,0] ✓ Size of diff = original + 1 (need to mark last+1)

2D Example

Update (0,0) → (1,1) in a 3x3 matrix:

diff[0][0]++ , diff[0][2]--, diff[2][0]--, diff[2][2]++

Before:          After diff:
[0, 0, 0]        [1,  0, -1]
[0, 0, 0]   →   [0,  0,  0]
[0, 0, 0]        [-1, 0,  1]

After 2D psum:
[1, 1, 0]
[1, 1, 0]
[0, 0, 0]  ✓

bool possibleToStamp(vector<vector<int>>& grid, int h, int w) {
    int m = grid.size(), n = grid[0].size();
    vector<vector<int>> psum1(1+m, vector<int>(1+n, 0));
 
    // Compute 2D psum of grid
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
            psum1[i+1][j+1] = psum1[i+1][j] + psum1[i][j+1] - psum1[i][j] + grid[i][j];
 
    auto get = [&](int r1, int c1, int r2, int c2) {
        r1++; c1++; r2++; c2++;
        return psum1[r2][c2] - psum1[r2][c1-1] - psum1[r1-1][c2] + psum1[r1-1][c1-1];
    };
 
    // stamp: size +2 (+1 for diff, +1 for psum)
    vector<vector<int>> stamp(m+2, vector<int>(n+2, 0));
    for (int i = 0; i+h-1 < m; ++i)
        for (int j = 0; j+w-1 < n; ++j)
            if (get(i, j, i+h-1, j+w-1) == 0) {  // all empty → can stamp
                stamp[i+1][j+1]++;
                stamp[i+1][j+w+1]--;
                stamp[i+h+1][j+1]--;
                stamp[i+h+1][j+w+1]++;
            }
 
    // 2D psum of stamp diff array
    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j)
            stamp[i][j] += stamp[i-1][j] + stamp[i][j-1] - stamp[i-1][j-1];
 
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
            if (grid[i][j] == 0 && stamp[i+1][j+1] == 0)
                return false;  // empty cell not covered by any stamp
    return true;
}
// TC - O(m*n) | SC - O(m*n)

221. Maximal Square

At each '1' cell, assume it’s the bottom-right corner. psum[i][j] = 1 + min(left, up, diagonal corner) → if all 3 are ≥ 1, we can form a square.

int maximalSquare(vector<vector<char>>& matrix) {
    int m = matrix.size(), n = matrix[0].size();
    vector<vector<int>> psum(1+m, vector<int>(1+n, 0));
    int ans = 0;
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
            if (matrix[i][j] == '1') {
                psum[i+1][j+1] = 1 + min({psum[i+1][j], psum[i][j+1], psum[i][j]});
                ans = max(ans, psum[i+1][j+1]);
            }
    return ans * ans;
}
// TC - O(m*n) | SC - O(m*n)

2201. Count Artifacts That Can Be Extracted

Calculate rectangle size of each artifact via top-left + bottom-right coords. If psum of that rectangle == artifact_size → all blocks excavated → collect it.

int digArtifacts(int n, vector<vector<int>>& artifacts, vector<vector<int>>& dig) {
    vector<vector<int>> grid(n, vector<int>(n, 0));
    for (auto& d : dig) grid[d[0]][d[1]] = 1;
 
    vector<vector<int>> psum(1+n, vector<int>(1+n, 0));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            psum[i+1][j+1] = psum[i+1][j] + psum[i][j+1] - psum[i][j] + grid[i][j];
 
    int ans = 0;
    for (auto& a : artifacts) {
        int artifact_size = (a[3]-a[1]+1) * (a[2]-a[0]+1);
        int r1 = a[0]+1, c1 = a[1]+1, r2 = a[2]+1, c2 = a[3]+1;
        int ex = psum[r2][c2] - psum[r1-1][c2] - psum[r2][c1-1] + psum[r1-1][c1-1];
        if (artifact_size == ex) ++ans;
    }
    return ans;
}
// TC - O(n^2 + artifacts) | SC - O(n^2)

3148. Maximum Difference Score in a Grid

Move only right or down. Score = sum of (new - old) at each step.

(c5-c4) + (c4-c3) + (c3-c2) + (c2-c1) = c5 - c1

Intermediate terms cancel! → Score = current_cell - minimum_cell_seen_before. Find minimum in the top-left region using prefix minimum.

int maxScore(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    vector<vector<int>> pmin(1+m, vector<int>(1+n, INT_MAX));
    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j)
            pmin[i][j] = min({grid[i-1][j-1], pmin[i][j-1], pmin[i-1][j]});
 
    int ans = INT_MIN;
    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j) {
            if (i == 1 && j == 1) continue;
            ans = max(ans, grid[i-1][j-1] - min(pmin[i][j-1], pmin[i-1][j]));
        }
    return ans;
}
// TC - O(m*n) | SC - O(m*n)

1 item under this folder.