Om's Brain

3. Prefix Sum

20 min read

🔍 When Do You Reach For This?

You’re looking at a subarray problem. You try sliding window — but it breaks. Why?

Sliding window only works when moving the left pointer always makes the window “more valid”. The moment you have negative numbers, or the condition isn’t monotonic, sliding window fails.

That’s your signal. Switch to Prefix Sum.

These problems typically ask:

  • Count of subarrays with some property
  • Longest / shortest subarray with some property
  • Range sum queries in O(1)

💡 The Core Insight

Maintain a running sum as you scan. Before touching any element, sum = 0.

psum[-1] = 0          ← before the array (virtual index)
psum[ 0] = arr[0]
psum[ 1] = arr[0] + arr[1]
...

Key observation:

              ----------|--|----------|----
Indices:      0        j-1 j          i
Prefix Sum:    psum[j-1]            psum[i]

psum[j..i]  =  psum[i] - psum[j-1]

So if you want a subarray ending at i with sum = K:

psum[i] - psum[j-1] = K 
psum[j-1] = psum[i] - K

While scanning at index i, you ask: “Has psum[i] - K appeared in my past sums?”

If yes → there’s a subarray ending at i with sum = K.

Store past sums in a hashmap. Seed it with mp[0] = -1 — saying: “a sum of 0 was seen at virtual index −1, before the array began.”

This is the entire idea

Store past prefix sums in a hashmap, initialised with mp[0] = -1. At each index, check if psum - K exists in the map. Everything else is a variation of this.

📋 The Universal Template

int psum = 0;
unordered_map<int, int> mp;
mp[0] = ???;   // ← the only real decision
 
for (int i = 0; i < n; i++) {
    psum += arr[i];
 
    // Check: does (psum - K) exist?
    if (mp.count(psum - K)) {
        // use mp[psum - K]
    }
 
    // Update map
    mp[psum] = ???;
}

The Only Decision: Count vs Length

GoalMap TypeInitAnswer LogicUpdate
Count subarrays<psum,count>mp[0] = 1ans += mp[need]mp[psum]++ (always)
Longest subarray<psum,idx>mp[0] = -1ans = max(ans, i-j)mp[psum] = i (first occurrence only)
Shortest subarray<psum,idx>mp[0] = -1ans = min(ans, i-j)mp[psum] = i (overwrite every time)

Why mp[0] = 1 for count?

If psum - K = 0, the entire subarray from index 0 to i is the answer. Without mp[0] = 1, you’d miss it.

Why mp[0] = -1 for length?

If psum - K = 0, the subarray goes from index 0 to iis the answer. Length = i - (-1) = i + 1. ✓

Longest vs Shortest

  • Longest → store first occurrence (earlier index = longer range)
  • Shortest → overwrite every time (latest index = shorter range)

🧩 Pattern 1 — Sum = K (The Base Case)

Everything in this page is built on top of this.

Count subarrays with sum = K — LC 560 🔥 ⭐

// LC 560. Subarray Sum Equals K
int subarraySum(vector<int>& nums, int k) {
    unordered_map<int, int> mp;
    mp[0] = 1;
    int psum = 0, count = 0;
    for (int i = 0; i < nums.size(); i++) {
        psum += nums[i];
        count += mp[psum - k];   // add 0 if not found (safe with unordered_map default)
        mp[psum]++;
    }
    return count;
}
// TC - O(n) | SC - O(n)

Longest subarray with sum = K — LC 325

// LC 325. Maximum Size Subarray Sum Equals k
int maxSubArrayLen(vector<int>& nums, int k) {
    unordered_map<int, int> mp;
    mp[0] = -1;
    int psum = 0, maxLen = 0;
    for (int i = 0; i < nums.size(); i++) {
        psum += nums[i];
        if (mp.count(psum - k)) {
            int j = mp[psum - k];
            maxLen = max(maxLen, i - j); // i (right) - j (left)
        }
        if (!mp.count(psum))       // store FIRST occurrence only
            mp[psum] = i;
    }
    return maxLen;
}
// TC - O(n) | SC - O(n)
//
// -- dry run example --
// nums = [10, 5, 2, 7, 1, 9], k = 15
//
//                       j                               i
// Indices:      -1      0      1      2     3     4     5
// Elements:     |      10      5      2     7     1     9
// Prefix Sum:   0      10     15     17    24    25    34
//                       ^                         ^
//                       |--------- len = 4 -------|
//                       length = i - j = 4 - 0 = 4
//
// mp = {0: -1}
// i = 0: psum = 10, mp[10] = 0
// i = 1: psum = 15, psum-k = 0 exists -> j = -1 -> len = 1 - (-1) = 2 -> maxLen = 2, mp[15] = 1
// i = 2: psum = 17, mp[17] = 2
// i = 3: psum = 24, mp[24] = 3
// i = 4: psum = 25, psum-k = 10 exists -> j = 0 -> len = 4 - 0 = 4      -> maxLen = 4, mp[25] = 4
// i = 5: psum = 34, mp[34] = 5

Disguised Sum = K problems

🧩 Pattern 2 — Divisibility / Modulo

The Math

Want subarray [j..i] divisible by K:

              |--  s1  --| |--  s2  --|
             ---------------------------
Indices:      0        j-1 j          i
Prefix Sum:   psum[j-1]      psum[i]
 
So, s2 = psum[i] - psum[j-1]

We want the subarray to be divisible by :

So instead of storing the actual sums, we store their remainders. If the same remainder is seen at two indices, the subarray between them is divisible by .

The Negative Remainder Bug

C++ computes -5 % 3 = -2. But mathematically it’s 1. Always normalize: rem = ((psum % K) + K) % K This is safe for positive remainders too (no harm done).

Count subarrays divisible by K — LC 974 🔥

// LC 974. Subarray Sums Divisible by K
int subarraysDivByK(vector<int>& nums, int K) {
    unordered_map<int, int> mp;
    mp[0] = 1;
    int psum = 0, count = 0;
    for (int x : nums) {
        psum += x;
        int rem = ((psum % K) + K) % K;   // normalize negative remainder
        count += mp[rem];
        mp[rem]++;
    }
    return count;
}
// TC - O(n) | SC - O(K)

Subarray sum is multiple of K, length ≥ 2 — LC 523 ⭐

// LC 523. Continuous Subarray Sum
bool checkSubarraySum(vector<int>& nums, int k) {
    unordered_map<int, int> mp;
    mp[0] = -1;
    int psum = 0;
    for (int i = 0; i < nums.size(); i++) {
        psum = ((psum + nums[i]) % k + k) % k;
        if (mp.count(psum)) {
            if (i - mp[psum] > 1) return true;   // length must be ≥ 2
        } else
            mp[psum] = i;
    }
    return false;
}
// TC - O(n) | SC - O(k)

Smallest subarray to remove so rest is divisible by P — LC 1590 📍 💀

  • Find smallest subarray whose sum gives remainder k.
total = remaining + to_remove
remaining = total - to_remove
 
we know that..  remaining%p = 0
(total - to_remove) % p = 0
to_remove%p = total%p
to_remove%p = k
// LC 1590. Make Sum Divisible by P
// Remove smallest subarray with sum divisible by (totalSum % P)
// → remaining sum is divisible by P
int minSubarray(vector<int>& nums, int p) {
    long long total = accumulate(nums.begin(), nums.end(), 0LL);
    int k = total % p;
    if (k == 0) return 0;
 
    unordered_map<int, int> mp;
    mp[0] = -1;
    int psum = 0, n = nums.size(), ans = n;
    for (int i = 0; i < n; i++) {
        psum = (psum + nums[i]) % p;
        int need = (psum - k + p) % p;
        if (mp.count(need))
            ans = min(ans, i - mp[need]);   // shortest → overwrite every time
        mp[psum] = i;                        // ← overwrite (unlike longest subarray)
    }
    return ans == n ? -1 : ans;
}
// TC - O(n) | SC - O(n)

1. Modulo Arthmatics Questions

Check array pairs are divisible by K — LC 1497 💀 📍

BEST for learning modulo Arithmatic -⇒ Watch Video

class Solution {
public:
    bool canArrange(vector<int>& arr, int k) {
        unordered_map<int, int> um;
 
        // Count frequency of each remainder
        for (int x : arr) {
            int rem = x % k;
 
            // Handle negative numbers
            // Example: -2 % 5 = -2 -> convert to 3
            if (rem < 0) rem += k;
 
            um[rem]++;
        }
 
        // Process all remainder buckets
        while (!um.empty()) {
            auto it = um.begin();
            int ele = it->first;
 
            // Complement remainder needed
            // r needs (k-r)%k
            // Example: k=5, r=2 -> need 3
            int toFind = (k - ele) % k;
 
            // SAME BUCKET CASE
            // 1) rem = 0
            //    0 pairs with 0
            //
            // 2) rem = k/2 (only when k is even)
            //    Example: k=6, rem=3
            //    3 pairs with 3
            //
            // In both cases, count must be even
            if (ele == toFind) {
                if (um[ele] % 2 != 0)
                    return false;
 
                // Entire bucket can be removed
                um.erase(ele);
                continue;
            }
 
            // Complement bucket doesn't exist
            if (!um.count(toFind))
                return false;
 
            // Counts must match
            // Example:
            // rem=1 count=3
            // rem=4 count must also be 3
            if (um[ele] != um[toFind])
                return false;
 
            // Valid pair buckets, remove both
            um.erase(ele);
            um.erase(toFind);
        }
 
        return true;
    }
};
// BETTER SOLUTION
// LC 1497. Check If Array Pairs Are Divisible by k
// Pair rem r with (k-r)%k. All remainders must find a partner.
bool canArrange(vector<int>& arr, int k) {
    unordered_map<int, int> rem_map;
    for (int x : arr) {
        int r = ((x % k) + k) % k;
        if (rem_map[(k - r) % k] > 0)
            --rem_map[(k - r) % k];
        else
            ++rem_map[r];
    }
    for (auto& [key, val] : rem_map)
        if (val != 0) return false;
    return true;
}
// TC - O(n) | SC - O(k)

Number string divisibility (overflow-safe) — LC 2575

// LC 2575. Find the Divisibility Array of a String
// Can't store full number — overflows. Do modulo at each step.
// (psum * 10 + digit) % m  is the same as building number % m digit by digit
vector<int> divisibilityArray(string word, int m) {
    vector<int> ans(word.size(), 0);
    long long psum = 0;
    for (int i = 0; i < word.size(); i++) {
        psum = (psum * 10 + (word[i] - '0')) % m; // nice Maths
        if (psum == 0) ans[i] = 1;
    }
    return ans;
}
// TC - O(n) | SC - O(1)

Mix: binary conversion + modulo — LC 2845

// LC 2845. Count of Interesting Subarrays
// Step 1: convert arr[i] = (arr[i] % modulo == k) → binary array
// Step 2: count subarrays whose sum % modulo == k
class Solution {
public:
    long long countInterestingSubarrays(vector<int>& nums, int m, int k) {
 
        for (auto &num : nums) num = (num % m == k) ? 1 : 0;
        int n = nums.size(), psum = 0;
        unordered_map<int, long long> um;
        um[0] = 1;   // empty prefix
        long long cnt = 0;
 
        for (int i = 0; i < n; i++) {
            psum += nums[i];
 
            int mod = ((psum % m) + m) % m;
            int target = (mod - k + m) % m;
 
            if (um.count(target))
                cnt += um[target];
            um[mod]++;
        }
        return cnt;
    }
};
// TC - O(n) | SC - O(n)

🧩 Pattern 3 — Equal 0s and 1s (The Flip Trick)

The Trick

Replace every 0 with -1. Now “equal 0s and 1s” becomes subarray with sum = 0.

Why? Equal counts → they cancel out → running sum repeats.

arr  = [1, 0, 0, 1, 1, 0]
after: [1,-1,-1, 1, 1,-1]
psum = [0, 1, 0,-1, 0, 1, 0]
         ↑           ↑
         same psum (0) at index -1 and 4 → subarray [0..4] has equal 0s and 1s

Longest subarray with equal 0s and 1s — LC 525

Why Sliding Window fails in this problem

  • Sliding window needs a monotonic property:
  • When you move left pointer, window should become more valid / less valid predictably.
  • Example: For sum ≤ K with positive numbers:
    • expand right → sum always increases
    • shrink left → sum always decreases
    • ✅ monotonic → sliding window works
// LC 525. Contiguous Array
int findMaxLength(vector<int>& nums) {
    unordered_map<int, int> mp;
    mp[0] = -1;
    int psum = 0, maxLen = 0;
    for (int i = 0; i < nums.size(); i++) {
        psum += (nums[i] == 0 ? -1 : 1);   // 0 → -1 flip
        if (mp.count(psum))
            maxLen = max(maxLen, i - mp[psum]);
        else
            mp[psum] = i;
    }
    return maxLen;
}
// TC - O(n) | SC - O(n)

Count subarrays with equal 0s and 1s — GFG

long long countSubarrWithEqualZeroAndOne(int nums[], int n) {
    unordered_map<int, int> mp;
    mp[0] = 1;
    int psum = 0, cnt = 0;
    for (int i = 0; i < n; i++) {
        psum += (nums[i] == 0 ? -1 : 1);
        cnt += mp[psum];
        mp[psum]++;
    }
    return cnt;
}
// TC - O(n) | SC - O(n)

🧩 Pattern 4 — Equal 0s, 1s and 2s (Composite Key Trick)

Substring with Equal 0, 1 and 2 — GFG

We want: count(0) = count(1) = count(2)for some substring/subarray. Let at index i: z = number of 0s till i o = number of 1s till i t = number of 2s till i Instead of storing all three counts directly, we store their differences: (z - o, o - t) Why? ⇒ Because if all three counts increase equally between two indices, these differences remain unchanged.

// GFG - Count subarrays with equal 0, 1, 2  
long long getSubstringWithEqual012(string str) {
    unordered_map<string, int> mp;
    int z = 0, o = 0, t = 0, cnt = 0;
    string key = "0#0";
    mp[key] = 1;
    for (char c : str) {
        if (c == '0') z++;
        else if (c == '1') o++;
        else t++;
        key = to_string(z - o) + "#" + to_string(o - t);
        if(mp.count(key)) cnt += mp[key];
        mp[key]++;
    }
    return cnt;
}
// TC - O(n) | SC - O(n)

🧩 Pattern 5 — XOR Bitmask

Quick Identifier

Problem asks: even/odd occurrence of characters or digits in a subarray → XOR bitmask.

The Insight

XOR same value twice = 0. So if mask_i == mask_j, everything between them cancelled → all even occurrences.

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

The mask is your “prefix sum” — just XOR instead of addition.

Even occurrence (all characters appear even times) — LC 1371

// LC 1371. Longest Substring With Vowels in Even Counts
int findTheLongestSubstring(string s) {
    unordered_map<char, int> idx = {{'a',0},{'e',1},{'i',2},{'o',3},{'u',4}};
    unordered_map<int, int> mp;
    mp[0] = -1;   // empty prefix mask
    int mask = 0, ans = 0;
    for (int i = 0; i < s.size(); i++) {
        if (idx.count(s[i]))
            mask ^= (1 << idx[s[i]]);
        if (mp.count(mask))
            ans = max(ans, i - mp[mask]);
        else
            mp[mask] = i;
    }
    return ans;
}
// TC - O(n) | SC - O(2^5) = O(1)

At-most 1-odd character — LC 1542

Try “what if exactly this one bit was odd?” → flip each bit and check.

// LC 1542. Find Longest Awesome Substring
// Palindrome: all even OR exactly 1 odd (middle char). Digits 0..9 → 10 bits.
int longestAwesome(string s) {
    unordered_map<int, int> mp;
    mp[0] = -1;
    int mask = 0, ans = 1;
    for (int i = 0; i < s.size(); i++) {
        mask ^= (1 << (s[i] - '0'));
 
        if (mp.count(mask))
            ans = max(ans, i - mp[mask]);            // all even
 
        for (int j = 0; j < 10; j++) {              // exactly 1 odd
            int flipped = mask ^ (1 << j);
            if (mp.count(flipped))
                ans = max(ans, i - mp[flipped]);
        }
 
        if (!mp.count(mask)) mp[mask] = i;
    }
    return ans;
}
// TC - O(10n) = O(n) | SC - O(2^10) = O(1)

1915. Number of Wonderful Substrings

Same as above but count instead of length, and chars a..j (10 chars). Count variant: mp[0] = 1, always mp[mask]++. For each i: add mp[mask] (all even) + mp[mask ^ (1<<j)] for each j (1-odd).

🧩 Pattern 6 — 2D Prefix Sum

Build the 2D psum

Extend 1D idea to a grid. psum at (i,j) = sum of entire rectangle from (0,0) to (i,j).

psum[i+1][j+1] = psum[i+1][j] + psum[i][j+1] - psum[i][j] + arr[i][j]
                  ↑ left col      ↑ top row       ↑ double-counted corner

Always use size (m+1) x (n+1) → row 0 and col 0 are all zeros (sentinel).

// Build
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] + arr[i][j];

Query any submatrix (r1,c1) → (r2,c2) in O(1)

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

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];
};

Remember

psum is 1-indexed → always +1 on both dimensions when querying. The formula subtracts two strips and adds back the double-subtracted corner (inclusion-exclusion).

LC 304 — Range Sum Query 2D - Immutable

Pure template application.

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 O(m*n) | Query O(1) | SC O(m*n)

LC 1314 — Matrix Block Sum

At each cell (i,j): sum of all cells within k distance → clamp to grid bounds.

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);   // already +1 for psum
            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)

LC 221 — Maximal Square

DP variant. Each cell = side length of largest square with this cell as bottom-right corner. dp[i][j] = 1 + min(left, top, top-left diagonal)

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

LC 2201 — Count Artifacts That Can Be Extracted

artifact_size == psum of that rectangle → fully 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(n+1, vector<int>(n+1, 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 sz = (a[3]-a[1]+1) * (a[2]-a[0]+1);
        int ex = psum[a[2]+1][a[3]+1] - psum[a[0]][a[3]+1] - psum[a[2]+1][a[1]] + psum[a[0]][a[1]];
        if (sz == ex) ans++;
    }
    return ans;
}
// TC O(n^2 + artifacts) | SC O(n^2)

LC 3148 — Maximum Difference Score in a Grid

Move only right/down. Score telescopes: (c5-c4)+(c4-c3)+...= c_last - c_first → maximize current_cell - minimum_seen_in_top_left_region → use prefix minimum.

int maxScore(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    vector<vector<int>> pmin(m+1, vector<int>(n+1, 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)

🧩 Pattern 7 — 2D Differential Array (Range Update in O(1))

The Problem

You need to “stamp” rectangles onto a grid many times, then query coverage. Naively: each stamp is O(h*w). With many stamps → too slow.

1D First

To add 1 to all indices in range [l, r] of an array:

diff[l]   += 1
diff[r+1] -= 1

After all updates, prefix sum of diff gives the actual values.

range update [1,4] on [0,0,0,0,0,0]:
diff = [0, 1, 0, 0, 0, -1, 0]
psum = [0, 1, 1, 1, 1,  0, 0]  ✓

2D Extension

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

diff[r1][c1]++;
diff[r1][c2+1]--;
diff[r2+1][c1]--;
diff[r2+1][c2+1]++;   // add back the corner that was double-subtracted

Then 2D prefix sum of diff → each cell tells how many rectangles cover it.

Visual (3×3 grid, stamp (0,0)→(1,1)) 

Diff:            After 2D psum:
[ 1,  0, -1]    [1, 1, 0]
[ 0,  0,  0]    [1, 1, 0]
[-1,  0,  1]    [0, 0, 0]   ← stamped region is exactly (0,0)→(1,1) ✓

LC 2132 — Stamping the Grid

bool possibleToStamp(vector<vector<int>>& grid, int h, int w) {
 
    int m = grid.size(), n = grid[0].size();
 
    // Step 1: 2D psum of grid (to check if a region is all empty)
    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] + grid[i][j];
 
    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];
    };
 
    // Step 2: stamp using 2D differential array (size +2: +1 diff, +1 psum)
    vector<vector<int>> diff(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 (getSum(i, j, i+h-1, j+w-1) == 0) {   // all empty → can stamp
                diff[i+1][j+1]++;
                diff[i+1][j+w+1]--;
                diff[i+h+1][j+1]--;
                diff[i+h+1][j+w+1]++;
            }
 
    // Step 3: 2D psum of diff → coverage count per cell
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            diff[i][j] += diff[i-1][j] + diff[i][j-1] - diff[i-1][j-1];
 
    // Step 4: every empty cell must be covered
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            if (grid[i][j] == 0 && diff[i+1][j+1] == 0)
                return false;
    return true;
}
// TC O(m*n) | SC O(m*n)

🧠 Master Cheatsheet

Pattern Recognition

Signal in problemPattern to use
Subarray sum = K, elements can be negativePrefix Sum + HashMap
Subarray divisible by KPrefix Sum + Remainder
Equal 0s and 1sReplace 0→-1, sum = 0
Equal 0, 1 and 2Composite key (z-o)#(o-t)
Even/odd occurrence of chars/digitsXOR Bitmask
Submatrix range sum queries2D Prefix Sum
Stamp/update rectangles, check coverage2D Differential Array

Init Value Decision

Counting?  → mp[0] = 1,  always mp[sum]++
Longest?   → mp[0] = -1, store FIRST occurrence (if !mp.count(sum))
Shortest?  → mp[0] = -1, store LATEST occurrence (mp[sum] = i, always overwrite)

The Negative Remainder Fix (always use this for mod problems)

int rem = ((psum % K) + K) % K;

2D Formulas (memorize these two)

// Build
psum[i+1][j+1] = psum[i+1][j] + psum[i][j+1] - psum[i][j] + arr[i][j];
 
// Query (r1,c1) → (r2,c2)
psum[r2+1][c2+1] - psum[r1][c2+1] - psum[r2+1][c1] + psum[r1][c1];

2D Differential Array (mark rectangle, query later)

// Mark (r1,c1) → (r2,c2)  [using 1-indexed diff array]
diff[r1+1][c1+1]++;  diff[r1+1][c2+2]--;
diff[r2+2][c1+1]--;  diff[r2+2][c2+2]++;
// Then do 2D psum on diff to get coverage counts

1 item under this folder.

Mindmap

Graph View