Fix the Equation
In The Fixing Mindset, you learned the core move: fix one thing, deduce the rest. We walked through Two Sum, Good Pairs, and Bad Pairs to see how that works.
Now let's get our hands dirty. This page covers the three main "array-level" fixing techniques — the Map Technique, Prefix Sum Remainder Fixing, and Pair Counting — plus two bonus mathematical tools that came up in the session. By the end, you'll have 10 problems to practice on.
Prerequisites: Arrays, hash maps, basic prefix sums.
1. The Map Technique (Deeper Dive)
You've seen Two Sum. Let's push the idea further.
The pattern is always the same: you have some condition involving two indices \(i\) and \(j\). You rearrange the equation so that everything involving \(i\) is on one side and everything involving \(j\) is on the other. Then as you iterate, you fix one side and look up the other in a map.
Teaching Example: Subarray Sum Equals K
Problem: Given an array, count subarrays whose sum equals \(K\).
A subarray from index \(l\) to \(r\) has sum \(P[r] - P[l-1]\), where \(P\) is the prefix sum array. So the condition is:
Rearrange:
Now apply the fixing mindset. As you walk through the array computing the running prefix sum, fix the current prefix \(P[r]\). The "partner" you need is \(P[r] - K\). How many times have you seen that value before? A hash map tells you instantly.
int subarraySum(vector<int>& nums, int k) {
unordered_map<int, int> seen = {{0, 1}}; // empty prefix = sum of 0
int prefix = 0, ans = 0;
for (int x : nums) {
prefix += x;
// FIX: current prefix sum
// CALCULATE: how many previous prefixes equal (prefix - k)?
if (seen.count(prefix - k))
ans += seen[prefix - k];
seen[prefix]++;
}
return ans;
}
Why seen = {{0, 1}}? Because the empty prefix (before the array starts) has sum 0. If the running prefix itself equals \(K\), then \(P[r] - K = 0\), and we need that "0 prefix" to be in the map. This trips people up constantly — don't forget the base case.
The General Recipe
Whenever you see a subarray condition like "sum equals X" or "count of something equals X," try this:
- Express the condition using prefix sums: \(P[r] - P[l-1] = X\)
- Rearrange: \(P[l-1] = P[r] - X\)
- Iterate, fix the current prefix, look up the partner in a map
- Don't forget to seed the map with the base case
This single pattern solves at least five of the ten problems on this page.
2. Fix the Remainder
Here's a twist on the prefix sum idea that feels like magic the first time you see it.
Problem: Count subarrays whose sum is divisible by \(K\).
The condition for a subarray \([l, r]\):
This means \(P[r]\) and \(P[l-1]\) leave the same remainder when divided by \(K\):
Read that again. You don't need two prefixes that differ by exactly \(K\). You need two prefixes with the same remainder mod K. That's a completely different — and much easier — lookup.
int subarraysDivByK(vector<int>& nums, int k) {
unordered_map<int, int> seen = {{0, 1}};
int prefix = 0, ans = 0;
for (int x : nums) {
prefix += x;
// FIX: the remainder of the current prefix
int rem = ((prefix % k) + k) % k; // handle negative mods
// CALCULATE: how many previous prefixes had the same remainder?
if (seen.count(rem))
ans += seen[rem];
seen[rem]++;
}
return ans;
}
That ((prefix % k) + k) % k line handles negative numbers. In C++, -7 % 5 gives -2, not 3. Adding \(K\) and taking mod again fixes it. This is a classic gotcha — burn it into your memory.
Why Does This Work?
Think of it this way. If two numbers leave the same remainder when divided by \(K\), their difference is divisible by \(K\). That's basic modular arithmetic:
So instead of checking "does this subarray sum divide evenly by K?" you're checking "have I seen this remainder before?" Same fix-and-lookup pattern, just with remainders instead of raw values.
3. Pair Counting with Combinatorics
Sometimes you don't need a map at all. If you just need to count pairs of identical things, it's pure math.
If a value appears \(f\) times, the number of pairs is \(\binom{f}{2} = \frac{f(f-1)}{2}\).
You've seen this in Good Pairs (from Page 1). But let's look at a slightly different approach — counting on the fly:
int numIdenticalPairs(vector<int>& nums) {
int cnt[101] = {}, ans = 0;
for (int x : nums) {
ans += cnt[x]++; // every previous occurrence of x forms a new pair
}
return ans;
}
Each time you see x, there are cnt[x] previous occurrences of x. Each one forms a pair with the current element. The cnt[x]++ happens after adding to ans (post-increment), so the count is correct.
This is cleaner than first counting all frequencies and then computing \(\binom{f}{2}\) for each — though both approaches are \(O(N)\).
4. Two Pointers as Fixing
When the array is sorted, you get a different flavor of fixing.
Problem (Two Sum II): Array is sorted. Find two numbers that sum to target. Return their 1-indexed positions.
With a sorted array, you don't need a hash map. Place one pointer at the start, one at the end. Fix both boundaries and let the sorted order guide you:
- Sum too small? The left value is too low → move left pointer right.
- Sum too big? The right value is too high → move right pointer left.
- Sum equals target? Done.
vector<int> twoSum(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while (l < r) {
int sum = nums[l] + nums[r];
if (sum == target) return {l + 1, r + 1};
if (sum < target) l++;
else r--;
}
return {};
}
Why does this work and not miss any valid pair? Because the array is sorted. If the sum is too small, every pair using the current left element and a smaller right element would also be too small. So you can safely discard the current left. Same logic in reverse for "too big."
This is still fixing — you're fixing the search boundaries and using the sorted property to shrink the space.
5. The Complement Trick
You saw this with Bad Pairs on Page 1, but it deserves its own section because it comes up everywhere.
When counting the "hard" thing is painful, count the "easy" thing and subtract.
Total pairs of \(N\) elements: \(\frac{N(N-1)}{2}\). If you can count "good" pairs easily (using a map), then bad pairs = total - good. You already saw this with Bad Pairs. Here's another application:
Teaching Example: Count Number of Teams
Problem: Given rating[0..n-1], count triplets \((i, j, k)\) where \(i < j < k\) and either rating[i] < rating[j] < rating[k] or rating[i] > rating[j] > rating[k].
Triplets are hard to count directly. But here's the key insight: fix the middle element.
For each index \(j\), count:
leftSmaller= how many elements to the left are smaller thanrating[j]rightLarger= how many elements to the right are larger thanrating[j]
Ascending triplets through \(j\) = leftSmaller * rightLarger.
Do the same for descending: leftLarger * rightSmaller.
int numTeams(vector<int>& rating) {
int ans = 0, n = rating.size();
for (int j = 1; j < n - 1; ++j) {
// FIX: the middle soldier j
int leftSmaller = 0, leftLarger = 0;
int rightSmaller = 0, rightLarger = 0;
for (int i = 0; i < j; ++i) {
if (rating[i] < rating[j]) leftSmaller++;
else leftLarger++;
}
for (int k = j + 1; k < n; ++k) {
if (rating[k] > rating[j]) rightLarger++;
else rightSmaller++;
}
// CALCULATE: ascending + descending triplets through j
ans += leftSmaller * rightLarger + leftLarger * rightSmaller;
}
return ans;
}
This is \(O(N^2)\) — which is fine for the given constraints (\(N \le 1000\)). The insight isn't about speed here. It's about choosing what to fix. If you fix the first element, you still have two unknowns. If you fix the middle, the left and right become independent counts that multiply. That's the power of choosing the right thing to fix.
Bonus: Play with Modulo
This one comes from the session and it's a neat mathematical trick.
Say you have a linear Diophantine equation:
Two unknowns, one equation. Looks stuck. But take everything mod 5:
The \(5y\) term vanishes. You've killed an entire variable with one operation. Now solve for \(x\) mod 5 (the modular inverse of 3 mod 5 is 2, so \(x \equiv 4 \pmod{5}\)), and back-substitute to find \(y\).
The general principle: when an equation has too many variables, take it modulo one of the coefficients to eliminate a term. This shows up in number theory problems, and it's a clean example of "fixing" applied to equations rather than arrays.
Bonus: The DP Trick
This is a trick for when you're staring at a DP problem and can't figure out the recurrence. It works surprisingly often.
Step 1: Assume the recurrence has a certain form. For a 1D problem, try:
Start with two terms. If that doesn't work, try three.
Step 2: Brute-force the first few values. Compute \(DP(0)\), \(DP(1)\), \(DP(2)\), \(DP(3)\) by hand or with a simple simulation.
Step 3: Plug into the assumed form. With two unknowns (\(a\) and \(b\)), you need two equations:
Solve this system on paper. If it gives consistent values for \(a\) and \(b\), you've found your recurrence. If it doesn't, try adding a third term.
Why does this work? Many competitive programming DPs have linear recurrences with small constant coefficients. The number of prior states that matter is usually small — in 2D DP, transitions typically depend on \(DP(i-1, j)\) and \(DP(i, j-1)\), maybe \(DP(i-1, j-1)\). The space of possibilities is limited.
This trick won't solve everything, but when you're stuck in an interview and have no idea what the transition should be, brute-forcing a few values and fitting a recurrence is a legitimate and fast escape hatch.
Practice Set
Problems are ordered from easiest to hardest. Problems marked with * were used as teaching examples on this page or the previous one — try to solve them from memory before looking at the solution.
Warm-Up (Easy)
- 1. Two Sum * — Fix
x, Calctarget - x - 1512. Number of Good Pairs * — Fix value, Calc frequency
- 167. Two Sum II * — Fix boundaries, shrink with sorted order
Core Practice (Medium)
- 560. Subarray Sum Equals K * — Fix prefix, Calc
prefix - K - 974. Subarray Sums Divisible by K * — Fix remainder, Calc same remainder
- 1248. Count Nice Subarrays — Fix odd-count prefix, Calc
prefix - K - 2364. Count Bad Pairs * — Fix
nums[i] - i, complement count
Harder (Medium-Hard)
- 523. Continuous Subarray Sum — Fix mod, but also check index distance \(\ge 2\)
- 2488. Count Subarrays With Median K — Fix balance from both sides of K
- 1395. Count Number of Teams * — Fix middle, Calc
left * right
Solutions
Warm-Up
1. Two Sum
2. Number of Good Pairs
3. Two Sum II
Core Practice
4. Subarray Sum Equals K
5. Subarray Sums Divisible by K
6. Count Nice Subarrays
Transform the array: odd → 1, even → 0. Now it's literally "Subarray Sum Equals K."
7. Count Bad Pairs
Rearrange: bad means nums[i] - i != nums[j] - j. Count good (same transformed value) and subtract.
long long countBadPairs(vector<int>& nums) {
unordered_map<int, int> m;
long long good = 0, n = nums.size();
for (int i = 0; i < n; ++i) {
int val = nums[i] - i;
// FIX: (nums[i] - i)
// CALCULATE: previous occurrences of same value
if (m.count(val)) good += m[val];
m[val]++;
}
return (n * (n - 1) / 2) - good;
}
Harder
8. Continuous Subarray Sum
Same remainder trick, but with a twist: the subarray length must be at least 2. So store the first index where each remainder appears, and only count a match if the gap is > 1.
bool checkSubarraySum(vector<int>& nums, int k) {
unordered_map<int, int> m = {{0, -1}};
int sum = 0;
for (int i = 0; i < nums.size(); ++i) {
sum = (sum + nums[i]) % k;
// FIX: current mod
// CALCULATE: if mod seen before at index prev, check distance
if (m.count(sum)) {
if (i - m[sum] > 1) return true;
} else {
m[sum] = i; // only store FIRST occurrence
}
}
return false;
}
The key difference from Divisible by K: there we counted all previous matches. Here we need i - prev_index > 1, so we store the index and only save the first occurrence (to maximize the gap).
9. Count Subarrays With Median K
This one's tricky. The median of a subarray is K when the count of elements > K equals the count of elements < K (odd length) or differs by 1 (even length).
Define a "balance": +1 for elements > K, -1 for elements < K, 0 for K itself. Scan left from K's position to build a frequency map of balances. Then scan right, and for each right-balance, look up the left-balance that makes the total 0 or 1.
int countSubarrays(vector<int>& nums, int k) {
int p = find(nums.begin(), nums.end(), k) - nums.begin();
unordered_map<int, int> m;
int bal = 0, ans = 0;
// Scan left from K (inclusive)
for (int i = p; i >= 0; --i) {
bal += (nums[i] == k ? 0 : (nums[i] < k ? -1 : 1));
m[bal]++;
}
bal = 0;
// Scan right from K (inclusive)
for (int i = p; i < nums.size(); ++i) {
bal += (nums[i] == k ? 0 : (nums[i] < k ? -1 : 1));
// FIX: right balance
// CALCULATE: need left balance of -bal (total=0) or -bal+1 (total=1)
ans += m[-bal] + m[-bal + 1];
}
return ans;
}
10. Count Number of Teams
Fix the middle element. Count smaller-left × larger-right (ascending) plus larger-left × smaller-right (descending).
int numTeams(vector<int>& rating) {
int ans = 0, n = rating.size();
for (int i = 1; i < n - 1; ++i) {
// FIX: middle soldier i
int leftLess = 0, rightGreater = 0, leftGreater = 0, rightLess = 0;
for (int j = 0; j < i; ++j) {
if (rating[j] < rating[i]) leftLess++;
else leftGreater++;
}
for (int j = i + 1; j < n; ++j) {
if (rating[j] > rating[i]) rightGreater++;
else rightLess++;
}
// CALCULATE: ascending + descending through i
ans += leftLess * rightGreater + leftGreater * rightLess;
}
return ans;
}
What's Next
You now have the full array-level toolkit: maps, prefix sums, remainders, complements, two pointers, and a couple of mathematical bonus tools.
The next page — Fix the Structure — takes the same fixing mindset into trees. You'll fix edges, fix elements, and see how contribution counting works when the data isn't flat anymore.