Equations Are Constraints
Pillar: FIX — "Rearrange until one unknown is alone. The equation then forces its value."
The Core Move
You have an equation with two unknowns. You fix one. The equation tells you the other.
That's it. That's the move. Every "fix" application in this course reduces to this single step.
Take Two Sum: given an array and a target \(t\), find indices \(i, j\) such that \(a_i + a_j = t\). Two unknowns. Fix \(a_i\) by iterating over it. The equation forces \(a_j = t - a_i\). Now you just need to look up whether \(a_j\) exists — a hash map answers that in \(O(1)\).
The equation \(a_i + a_j = t\) is not a formula to "solve." It's a constraint that eliminates one degree of freedom the moment you fix the other.
Wait — does fixing always help? What if the equation has three unknowns?
Fixing eliminates one degree of freedom per variable you fix. With two unknowns and one equation, fixing one determines the other. With three unknowns and one equation, fixing one still leaves two unknowns — you'd need another constraint or another fix. The power of Fix scales with how many constraints the problem gives you relative to how many unknowns it has.
Why does this turn \(O(n^2)\) into \(O(n)\)? The brute force tries every pair — two nested loops. Fixing replaces the inner loop with a hash map lookup. You still visit every element (the outer loop), but at each element, you do \(O(1)\) work instead of \(O(n)\) work. The equation did the heavy lifting — it told you exactly what to look for, so you didn't have to search.
Count Good Pairs — The Pattern in Its Purest Form
Problem: given an array, count pairs \((i, j)\) with \(i < j\) and \(a_i = a_j\).
Brute force checks all \(\binom{n}{2}\) pairs — \(O(n^2)\). The fix approach: iterate \(j\) from left to right. At each \(j\), ask: "how many indices before \(j\) have \(a_j\)'s value?" A frequency map answers that in \(O(1)\).
Trace it on the array \([1, 2, 3, 1, 1, 3]\):
| \(j\) | \(a_j\) | Frequency of \(a_j\) before \(j\) | Pairs added | Running total | Frequency map after |
|---|---|---|---|---|---|
| 0 | 1 | 0 | 0 | 0 | \(\{1:1\}\) |
| 1 | 2 | 0 | 0 | 0 | \(\{1:1,\; 2:1\}\) |
| 2 | 3 | 0 | 0 | 0 | \(\{1:1,\; 2:1,\; 3:1\}\) |
| 3 | 1 | 1 | 1 | 1 | \(\{1:2,\; 2:1,\; 3:1\}\) |
| 4 | 1 | 2 | 2 | 3 | \(\{1:3,\; 2:1,\; 3:1\}\) |
| 5 | 3 | 1 | 1 | 4 | \(\{1:3,\; 2:1,\; 3:2\}\) |
Answer: 4 pairs. \(O(n)\) time.
int countGoodPairs(vector<int>& numbers) {
unordered_map<int, int> frequency;
int totalPairs = 0;
for (int value : numbers) {
totalPairs += frequency[value];
frequency[value]++;
}
return totalPairs;
}
The Modulo Trick
Sometimes the constraint hides behind a modulus. The move: take everything \(\bmod k\) to collapse the search space.
Problem: find a subarray whose sum is divisible by \(k\).
Build prefix sums \(p_0, p_1, \ldots, p_n\). A subarray sum \(p_j - p_i\) is divisible by \(k\) exactly when \(p_i \equiv p_j \pmod{k}\).
Is this always true? What if the prefix sums are negative?
Yes — congruence modulo \(k\) means \(p_j - p_i\) is a multiple of \(k\), regardless of the signs of \(p_i\) and \(p_j\). In code, be careful: C++ % can return negative values for negative operands. Use ((x % k) + k) % k to always get a non-negative remainder.
There are \(n+1\) prefix sums but only \(k\) residues. By the Pigeonhole Principle, if \(n \geq k\), two prefix sums share the same residue. Done — no brute force needed.
The modulus didn't add information. It removed a variable (the actual sum) and replaced it with a much smaller one (the residue).
Complement Counting
Instead of counting what you want, count everything and subtract what you don't want.
Problem: count pairs \((i, j)\) in an array where \(\gcd(a_i, a_j) > 1\).
Counting pairs with a shared factor directly is painful. Flip it: total pairs \(= \binom{n}{2}\). Pairs with \(\gcd = 1\) can be attacked via Euler's totient or inclusion-exclusion over prime factors. So:
When does complement counting NOT help?
Complement counting saves you when one side of the partition is structurally simpler than the other. If both "what you want" and "what you don't want" are equally hard to count, flipping gains nothing. The signal to look for: can you express the complement using a known formula or a simpler structure (like a frequency map)?
Count Bad Pairs — Equation Transformation + Complement
This problem layers two Fix moves on top of each other.
Problem: count pairs \((i, j)\) with \(i < j\) where \(a_j - a_i \neq j - i\).
Direct counting is a mess. Step back and rearrange the equation:
Move the \(i\)-terms to one side and the \(j\)-terms to the other:
Define \(b_i = a_i - i\). Now the condition is simply \(b_i \neq b_j\) — count pairs where the transformed values are different.
Why is rearranging allowed? Can we always separate i-stuff from j-stuff?
Yes, any linear equation in \(a_i, a_j, i, j\) can be rearranged this way. The key insight: group all terms involving index \(i\) on one side and all terms involving index \(j\) on the other. This works because addition and subtraction allow free regrouping. It breaks for non-linear constraints like \(a_i \cdot a_j = k\) — you can still fix one variable, but the separation is less clean.
Counting "different" pairs directly is awkward. But counting "same" pairs is exactly Count Good Pairs on the \(b\) array. So flip it:
Two Fix moves stacked:
- Equation transformation — rearrange to isolate \(i\)-stuff from \(j\)-stuff, creating the \(b\) array.
- Complement counting — count the easy thing (matching pairs on \(b\)) and subtract from total.
long long countBadPairs(vector<int>& numbers) {
long long length = (long long)numbers.size();
long long totalPairs = length * (length - 1) / 2;
unordered_map<int, long long> frequency;
long long goodPairs = 0;
for (int index = 0; index < (int)length; index++) {
int transformed = numbers[index] - index;
goodPairs += frequency[transformed];
frequency[transformed]++;
}
return totalPairs - goodPairs;
}
Two-Variable Substitution
When you have a pair \((x, y)\) satisfying some constraint \(f(x, y) = 0\), fix \(x\) and express \(y\) in terms of \(x\).
Example: count pairs \((a, b)\) with \(1 \leq a, b \leq n\) and \(a \cdot b = n\).
Fix \(a\). Then \(b = n / a\). For \(b\) to be a positive integer, \(a\) must divide \(n\). So the count of valid pairs is exactly the number of divisors of \(n\).
Does this always reduce the problem to divisor counting?
No — the reduction to divisors is specific to the constraint \(a \cdot b = n\). For additive constraints (\(a + b = k\)), fixing \(a\) gives \(b = k - a\), and the count depends on range checks. For modular constraints (\(a \cdot b \equiv 1 \pmod{m}\)), fixing \(a\) requires computing a modular inverse. The pattern is the same — fix one, derive the other — but the "derive" step depends on the equation.
The Complete Fix Pattern
Every example above follows the same five steps:
- Pick a variable to fix. Usually the current element or the right endpoint of a pair.
- Ask: what does the other variable need to be? There's always a constraint connecting them.
- Derive it from the problem's equation. Rearrange, substitute, take a modulus — whatever isolates the unknown.
- Look it up. Use a hash map, a set, or a sorted structure to check whether that value exists (or how many times it appears).
- Update bookkeeping for future lookups. Add the current element's information so that later iterations can find it.
If fixing one variable gives you \(O(1)\) or \(O(\log n)\) lookup for the other, you've almost certainly found the solution.
Quick Recap
- Fix one variable, the equation forces the other. This is the entire logic behind Two Sum, Count Good Pairs, Count Bad Pairs, and two-variable substitution.
- The complete Fix pattern: pick a variable, ask what the other must be, derive it from the equation, look it up, update bookkeeping.
- Equation transformation + complement counting is a two-move combo: rearrange the constraint to create a simpler problem, then count the easy version and subtract.
- The modulo trick shrinks the search space by replacing values with residues. Combined with Pigeonhole, it often gives existence proofs for free.
Problems
| Problem | Link | Difficulty | Technique |
|---|---|---|---|
| LC 1 — Two Sum | leetcode.com/problems/two-sum | Easy | Fix \(a_i\), look up \(t - a_i\) |
| LC 1512 — Number of Good Pairs | leetcode.com/problems/number-of-good-pairs | Easy | Fix right endpoint, frequency map |
| LC 2364 — Count Number of Bad Pairs | leetcode.com/problems/count-number-of-bad-pairs | Medium | Equation transform + complement |
| LC 560 — Subarray Sum Equals K | leetcode.com/problems/subarray-sum-equals-k | Medium | Prefix sums + complement counting |
| LC 974 — Subarray Sums Divisible by K | leetcode.com/problems/subarray-sums-divisible-by-k | Medium | Modulo trick + Pigeonhole |
| LC 1014 — Best Sightseeing Pair | leetcode.com/problems/best-sightseeing-pair | Medium | Fix one index, maximize the other |