Tags
- ⭐ = solved in first try
- 📍 = revisit
- 🔥 = important
- ⚠️ = solved but edge case missed
- 👀 = solved but had to see little solution first
- 🐢 = solved, but less optimized
- 💀 = out of the box
- no tag = pending/not started
3. Pattern: Prefix Sum
3.1 Prefix Sum + HashMap
| Question | Tags | Remember | My Solution |
|---|---|---|---|
| 1. Running Sum of 1d Array (easy) | ⭐ | ||
| 2. Range Sum Query - Immutable (easy) | ⭐ | ||
| 3. Subarray Sum Equals K (medium) | ⭐🔥 | count variant: um[0]=1, um[sum]++ | |
| 4. Find Pivot Index (easy) | ⭐ | left_sum == total - left_sum - nums[i] | |
| 5. Maximum Size Subarray Sum Equals k (medium) | 🔥 | length variant: um[0]=-1, store first only | |
| 6. Count Number of Nice Subarrays (medium) | convert odd→1 even→0, then same as #3 | ||
| 7. Binary Subarrays With Sum (medium) | exactly same as #6 | ||
| 8. Count Number of Bad Pairs (medium) | 🔥 | total pairs - good pairs. good: i-nums[i] == j-nums[j] | |
| 9. Count Vowel Strings in Ranges (medium) | mark 1/0 → build psum → answer queries in O(1) | ||
| 10. Minimum Operations to Reduce X to Zero (medium) | find largest subarray with sum = total-x | ||
| 11. Contiguous Array (medium) | replace 0→-1, find longest subarray with sum=0 | ||
| 12. Shortest Subarray With Sum at Least K (hard) | needs deque — not pure hashmap | ||
| 13. Count of Range Sum (hard) |
3.2 Prefix Sum & Divisibility / Modulo
| Question | Tags | Remember | My Solution |
|---|---|---|---|
| 1. Subarray Sums Divisible By K (medium) | 🔥 | rem = ((sum%k)+k)%k — fix negative remainder | |
| 2. Continuous Subarray Sum (medium) | 🔥 | same remainder → divisible; check length > 1 | |
| 3. Check If Array Pairs Are Divisible by k (medium) | pair remainder r with (k-r)%k | ||
| 4. Make Sum Divisible by P (medium) | find smallest subarray with sum = totalSum%p | ||
| 5. Find the Divisibility Array of a String (medium) | psum = psum*10 + digit; psum %= m — prevent overflow | ||
| 6. Count of Interesting Subarrays (medium) | convert to 0/1 array, then modulo trick same as #1 |
3.3 Prefix Sum & XOR (Bitmask)
💡 Quick identifier: problem asks even/odd occurrence of chars/digits in subarray
| Question | Tags | Remember | My Solution |
|---|---|---|---|
| 1. XOR Queries of a Subarray (medium) | warm-up — psum with XOR instead of + | ||
| 2. Find the Longest Substring Containing Vowels in Even Counts (medium) | 🔥 | 5 vowels → 5 bits; same mask = all even between | |
| 3. Number of Wonderful Substrings (medium) | 🔥📍 | count variant + atmost-1-odd → flip each of 10 bits | |
| 4. Find Longest Awesome Substring (hard) | 💀 | palindrome: all even OR 1 odd middle char. digits 0-9 → 10 bits | |
| 5. Count Triplets That Can Form Two Arrays of Equal XOR (medium) | 📍 | if xor[i..k]=0 then any j in between works → count pairs |
3.4 2D Prefix Sum
| Question | Tags | Remember | My Solution |
|---|---|---|---|
| 1. Range Sum Query 2D - Immutable (medium) | 🔥 | classic 2D template — psum size (m+1)x(n+1) | |
| 2. Matrix Block Sum (medium) | 🔥 | clamp bounds with min/max, then standard 2D query | |
| 3. Maximal Square (medium) | DP: psum[i][j] = 1 + min(left, up, diagonal) | ||
| 4. Count Artifacts That Can Be Extracted (medium) | artifact_size == excavation psum → count it | ||
| 5. Stamping the Grid (hard) | 2D diff array to mark stamps + 2D psum to verify coverage | ||
| 6. Maximum Difference Score in a Grid (medium) | score = last - first (intermediate cancels). prefix min trick |