Decrease and conquer on LeetCode is the habit of proving that a whole block of candidates cannot possibly hold the answer, and then deleting it without looking. Twelve problems here run on that one move: 167, 11, 42, 121, 53, 1014, 169, 240, 277, 280, plus two that are worth including precisely because one of them isn’t this pattern at all and the other should be.
All the code here compiles and runs against the sample cases plus the edge cases listed at the bottom. More problems: the LeetCode series.
The twelve problems at a glance
| # | Problem | Difficulty | Shape |
|---|---|---|---|
| 167 | Two Sum II — Input Array Is Sorted | Medium | Two pointers closing in |
| 11 | Container With Most Water | Medium | Two pointers closing in |
| 42 | Trapping Rain Water | Hard | Two pointers closing in |
| 121 | Best Time to Buy and Sell Stock | Easy | One running best |
| 53 | Maximum Subarray | Medium | One running best |
| 1014 | Best Sightseeing Pair | Medium | One running best |
| 169 | Majority Element | Easy | One running best |
| 240 | Search a 2D Matrix II | Medium | Discard a slice |
| 277 | Find the Celebrity | Medium (Premium) | Discard a slice |
| 280 | Wiggle Sort | Medium (Premium) | Discard a slice |
| 221 | Maximal Square | Medium | Not this pattern — see below |
| 1150 | Check If a Number Is Majority Element | Easy (Premium) | Should be this pattern — see below |
277, 280 and 1150 sit behind LeetCode Premium, so you can read the approach here but won’t be able to submit against them without a subscription.
The idea
Brute force on all of these problems enumerates candidates: every pair, every subarray, every buy-and-sell day. That’s O(n²), and at n = 105 it’s 1010 operations against a budget of maybe 108.
Decrease and conquer never enumerates. At each step it makes one comparison, uses that comparison to prove that an entire block of candidates is beaten by something already in hand, and throws the block away. The array shrinks, the answer can’t have been in what left, and one pass is enough.
Which means the code is never the hard part. Every solution below is a short loop that a competent programmer could write in two minutes. The hard part is the sentence that justifies the discard, and if you can’t say that sentence out loud, you don’t have the solution — you have a loop that happens to pass the samples. Each section below leads with the sentence.
Shape one: two pointers closing in
Start at both ends. Compare. Move one pointer inward, and in doing so discard every remaining candidate that used the pointer you moved. Three problems, one rule, three different reasons the rule is safe.
167. Two Sum II — Input Array Is Sorted (Medium)
The task: a sorted array and a target. Return the one-based positions of the two entries that add to the target, using constant extra space.
The discard: if the current sum is too big, then every pair using the right pointer is too big, because the left pointer only ever moves toward larger values. So the whole column belongs to nobody. Symmetrically for too small.
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int left = 0;
int right = (int)numbers.size() - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target) return {left + 1, right + 1}; // problem is 1-indexed
if (sum > target) --right; // no pair using `right` can work
else ++left; // no pair using `left` can work
}
return {}; // unreachable: the problem guarantees a solution
}
};The binary-search alternative is O(n log n): walk the array, search for the complement of each entry. That’s fine, and it’s what most people write first. The two-pointer version is faster because a binary search throws away half of one row, while a pointer move throws away an entire row or column of the pair grid.
11. Container With Most Water (Medium)
The task: each entry is the height of a vertical line. Pick two lines so that the rectangle they bound with the x-axis holds the most water. Return the area.
The discard, stated properly: suppose the left line is the shorter of the two. Take any other partner j strictly inside, so j < right. That pair’s width is smaller than the current width, and its height is min(height[left], height[j]), which is at most height[left]. So its area is strictly less than the area we just measured. No pair using the left line can ever beat what’s already recorded, and the left line can be dropped for good.
That paragraph is the problem. Everything below it is bookkeeping.
class Solution {
public:
int maxArea(vector<int>& height) {
int left = 0;
int right = (int)height.size() - 1;
int best = 0;
while (left < right) {
int limiting = min(height[left], height[right]);
best = max(best, (right - left) * limiting);
// move the shorter side: it can't do better with any closer partner
if (height[left] < height[right]) ++left;
else --right;
}
return best;
}
};On height = [1, 8, 6, 2, 5, 4, 8, 3, 7]:
| Step | left | right | Width | Limiting | Area | Best | Move |
|---|---|---|---|---|---|---|---|
| 1 | 0 (h=1) | 8 (h=7) | 8 | 1 | 8 | 8 | left is shorter → ++left |
| 2 | 1 (h=8) | 8 (h=7) | 7 | 7 | 49 | 49 | right is shorter → –right |
| 3 | 1 (h=8) | 7 (h=3) | 6 | 3 | 18 | 49 | –right |
| 4 | 1 (h=8) | 6 (h=8) | 5 | 8 | 40 | 49 | tie → –right |
| 5 | 1 (h=8) | 5 (h=4) | 4 | 4 | 16 | 49 | –right |
| 6 | 1 (h=8) | 4 (h=5) | 3 | 5 | 15 | 49 | –right |
| 7 | 1 (h=8) | 3 (h=2) | 2 | 2 | 4 | 49 | –right |
| 8 | 1 (h=8) | 2 (h=6) | 1 | 6 | 6 | 49 | –right, pointers meet |
42. Trapping Rain Water (Hard)
The task: the same bar chart, but now compute how much rain settles in the dips after it stops raining.
Same pointer rule as 11, different accounting, and a subtler justification. The water above any one column is set by the shorter of the tallest wall to its left and the tallest wall to its right. The obvious solution precomputes both of those as arrays, which is O(n) time and O(n) space.
The discard: if height[left] <= height[right], then somewhere to the right there stands a wall at least as tall as the left column. You don’t know where and you don’t care. That’s enough to guarantee the right-hand maximum is not the limiting one, so the water above left is decided entirely by the running left maximum, which you already have. The column is settled forever and the pointer moves on. That’s how the second array disappears and the space drops to O(1).
class Solution {
public:
int trap(vector<int>& height) {
int left = 0;
int right = (int)height.size() - 1;
int leftMax = 0, rightMax = 0;
int water = 0;
while (left < right) {
if (height[left] <= height[right]) {
// a wall at least this tall exists on the right, so leftMax decides
leftMax = max(leftMax, height[left]);
water += leftMax - height[left];
++left;
} else {
rightMax = max(rightMax, height[right]);
water += rightMax - height[right];
--right;
}
}
return water;
}
};Being asked 11 and then 42 back to back is common, and the point of the pairing is to see whether you notice they share a pointer rule while needing different arguments for why it’s safe.
Shape two: one pass, one running best
Walk forward carrying a single summary of everything behind you. At each step the summary tells you whether the past is worth keeping, and when it isn’t you delete all of it at once.
121. Best Time to Buy and Sell Stock (Easy)
The task: one buy, one later sell, maximise the profit. Zero if there isn’t any.
The discard: the moment you see a cheaper price, every earlier day is dominated as a buy day — it costs more and it offers no sell day the cheaper one doesn’t also offer. All of them go, replaced by a single integer.
class Solution {
public:
int maxProfit(vector<int>& prices) {
int cheapest = INT_MAX;
int best = 0;
for (int price : prices) {
cheapest = min(cheapest, price); // update first, so buy-day == sell-day gives 0
best = max(best, price - cheapest);
}
return best;
}
};Updating cheapest before computing the profit matters. Do it the other way round and the first iteration evaluates price - INT_MAX, which is signed overflow. Doing it in this order, the worst case on any day is a profit of exactly zero, which is already the floor.
53. Maximum Subarray (Medium)
The task: the contiguous slice with the largest sum. Values can be negative.
The discard: if the best slice ending at the previous index has a negative sum, then every slice ending here that includes it is worse than the single element here. The entire prefix is deleted and a new slice starts. That’s Kadane’s algorithm, and it’s the same “one integer replaces the past” move as 121.
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int endingHere = nums[0]; // best sum of a slice that ends at the current index
int best = nums[0];
for (int i = 1; i < (int)nums.size(); ++i) {
// extend the previous slice, or throw it away and start fresh
endingHere = max(endingHere + nums[i], nums[i]);
best = max(best, endingHere);
}
return best;
}
};Both variables start at nums[0], not at zero. Start best at zero and an all-negative array returns 0, which is not a valid slice — the problem wants a non-empty one. On [−3, −1, −2] the answer is −1.
1014. Best Sightseeing Pair (Medium)
The task: a pair i < j scores values[i] + values[j] + i − j. Return the best score.
The discard is unlocked by one line of algebra. Regroup the score so each half mentions only one index:
(values[i] + i) + (values[j] − j)
Once the two halves are separated, the left index stops interacting with the right one. For any given j, the best partner is simply whichever earlier index maximises values[i] + i, so every other earlier index is dominated and can go. The quadratic search collapses to one running maximum.
class Solution {
public:
int maxScoreSightseeingPair(vector<int>& values) {
int bestLeft = values[0] + 0; // largest values[i] + i seen so far
int best = INT_MIN;
for (int j = 1; j < (int)values.size(); ++j) {
best = max(best, bestLeft + values[j] - j);
bestLeft = max(bestLeft, values[j] + j);
}
return best;
}
};The order of those two lines is the whole correctness argument: score the pair before folding j into bestLeft, or you’ll pair an index with itself. Splitting a two-index expression into a left part and a right part is worth keeping as a reflex — it turns a surprising number of pair problems into one-pass problems.
169. Majority Element (Easy)
The task: return the value that appears more than ⌊n/2⌋ times. It’s guaranteed to exist.
A frequency map is O(n) time and O(n) space, and the time can’t be improved. The space can.
The discard: pair off two different values and delete both. At most one of them was the majority, so the majority still has a strict majority of what’s left. Repeat until only one value survives. Boyer–Moore voting does exactly this with a counter instead of an actual deletion, which is why it needs two integers rather than a map.
class Solution {
public:
int majorityElement(vector<int>& nums) {
int candidate = nums[0];
int count = 0;
for (int num : nums) {
if (count == 0) candidate = num; // everything so far has cancelled out
count += (num == candidate) ? 1 : -1;
}
return candidate;
}
};This leans entirely on the guarantee that a majority exists. Without it the survivor is just the last candidate standing and means nothing, so you’d need a second pass to count its occurrences and confirm. Say that out loud in an interview before anyone asks.
Shape three: discard a row, a column, or a person
240. Search a 2D Matrix II (Medium)
The task: a matrix whose rows increase left to right and whose columns increase top to bottom. Is the target in it?
Binary searching each row is O(m log n), and it wastes almost all of that work: only one row can contain the answer, and you searched every other one to find that out.
The discard: stand at the top-right corner. That cell is the largest in its row and the smallest in its column, which makes every comparison decisive. If it’s bigger than the target, nothing in that column can match, because everything below is bigger still — delete the column. If it’s smaller, nothing in that row can match, because everything to the left is smaller — delete the row. Every single comparison removes an entire row or column, so the whole search is at most m + n steps.
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int rows = (int)matrix.size();
int cols = (int)matrix[0].size();
int i = 0, j = cols - 1; // top-right: max of its row, min of its column
while (i < rows && j >= 0) {
if (matrix[i][j] == target) return true;
if (matrix[i][j] < target) ++i; // this row is entirely too small
else --j; // this column is entirely too big
}
return false;
}
};The bottom-left corner works identically. The other two corners don’t: at the top-left, both directions increase, so a comparison tells you nothing about which way to go.
277. Find the Celebrity (Medium, Premium)
The task: among n people, a celebrity is known by everyone and knows nobody. You can only ask “does A know B?”. Find the celebrity or report that there isn’t one, with as few questions as possible.
Asking about every ordered pair is n² questions.
The discard: one question eliminates one person, permanently, whatever the answer. Ask whether the current candidate knows person i. If yes, the candidate knows somebody and is out. If no, then i is not known by everyone and i is out. Either way somebody is gone after a single question, so n − 1 questions leave exactly one survivor. That survivor is the only possible celebrity, which is not the same as being one — a second pass confirms it.
/* The knows API is defined for you:
bool knows(int a, int b); */
class Solution {
public:
int findCelebrity(int n) {
// Pass 1: each question removes one person from contention.
int candidate = 0;
for (int i = 1; i < n; ++i) {
if (knows(candidate, i)) candidate = i;
}
// Pass 2: the survivor is the only possible celebrity. Verify it.
for (int i = 0; i < n; ++i) {
if (i == candidate) continue;
if (knows(candidate, i) || !knows(i, candidate)) return -1;
}
return candidate;
}
};That’s n − 1 questions in the first pass and at most 2(n − 1) in the second, comfortably inside the 3n the follow-up asks for.
One thing to be careful about in the verification, because it’s a trap that compiles and passes. Written without the inner brackets, as
if (candidate != i && knows(candidate, i) || !knows(i, candidate)) return -1;C++ binds && tighter than ||, so that parses as (candidate != i && knows(candidate, i)) || !knows(i, candidate) — the guard protects only the first half. When i equals the candidate, it falls through to asking whether the candidate knows themselves. That happens to be harmless on LeetCode, but only because the problem guarantees every person knows themselves, so the term is false and nothing happens. Take that guarantee away and the same code returns −1 for a graph that does have a celebrity. GCC will point at it if you let it: -Wparentheses flags this exact line.
280. Wiggle Sort (Medium, Premium)
The task: rearrange the array so it alternates: each odd position at least as large as its neighbours, each even position no larger. Any valid arrangement is accepted.
Sorting and then interleaving works and costs O(n log n). One pass does it in O(n).
The discard: walk left to right fixing one adjacent pair at a time, and never look back. The reason you never have to look back is worth spelling out. When you swap at an odd index, the left neighbour receives the smaller value; that neighbour sits at an even position, where the constraint already settled behind it wants it to be small. When you swap at an even index, the left neighbour receives the larger value, and it sits at an odd position, where the settled constraint wants it large. Every repair pushes the previous element in the direction its own constraint already tolerates, so no fix can break a fix.
class Solution {
public:
void wiggleSort(vector<int>& nums) {
int n = (int)nums.size();
for (int i = 1; i < n; ++i) {
bool needsGreater = (i % 2 == 1); // odd positions must be peaks
if (needsGreater ? nums[i] < nums[i - 1]
: nums[i] > nums[i - 1]) {
swap(nums[i], nums[i - 1]);
}
}
}
};The two that don’t belong, and why they’re here anyway
221. Maximal Square — this isn’t decrease and conquer
The task: in a grid of zeros and ones, find the area of the largest square made entirely of ones.
Nothing gets discarded here. This is dynamic programming: you fill a table, every cell is visited, and no candidate is ever ruled out early. It’s in this group because it shares a technique with the pattern — a padded row and column that removes every boundary check — not because it shares the idea. Being able to say which one a problem is, rather than reaching for whichever loop you wrote last, is most of what pattern practice is for.
The recurrence: a square can only end at a cell if squares also end at the three cells above, left, and diagonally up-left. The new side length is one more than the smallest of those three, because the smallest is what limits the fit.
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
int rows = (int)matrix.size();
int cols = (int)matrix[0].size();
// side[i][j] = side of the largest square whose bottom-right corner is (i-1, j-1).
// Padded, so the i-1 and j-1 lookups need no boundary checks.
vector<vector<int>> side(rows + 1, vector<int>(cols + 1, 0));
int best = 0;
for (int i = 1; i <= rows; ++i) {
for (int j = 1; j <= cols; ++j) {
if (matrix[i - 1][j - 1] == '0') continue;
side[i][j] = min({side[i - 1][j - 1],
side[i - 1][j],
side[i][j - 1]}) + 1;
best = max(best, side[i][j]);
}
}
return best * best; // the question asks for area, not side
}
};The final best * best catches people out often enough to be worth a note. So does the input type: the grid holds char, so the comparison is against '0' and not 0.
1150. Check If a Number Is Majority Element — this should be, and usually isn’t
The task: given a sorted array and a target, does the target occupy more than half of it?
The reflex is to count the occurrences and compare against n / 2. That’s correct, it passes, and it’s O(n) — which throws away the only interesting word in the problem statement. The array is sorted. A linear count would work just as well on a shuffled array, so if your solution doesn’t care about the sortedness, you’ve been handed something and declined it.
The discard: because equal values are contiguous, the target occupies a single block. Find where that block starts, then look at the position n / 2 slots further along. If the target still sits there, the block is longer than half the array; if it doesn’t, it isn’t. Two binary searches’ worth of work, and really only one.
class Solution {
public:
bool isMajorityElement(vector<int>& nums, int target) {
int n = (int)nums.size();
int first = (int)(lower_bound(nums.begin(), nums.end(), target) - nums.begin());
// if the block is longer than half the array, it still covers first + n/2
return first + n / 2 < n && nums[first + n / 2] == target;
}
};O(log n) instead of O(n), and no counting at all. The bounds check on the left of the && is doing real work: lower_bound returns the end iterator when the target is absent entirely.
Complexity
Every problem in the three shapes runs in one pass with a constant number of integers: O(n) time and O(1) space, or O(m + n) and O(1) for the matrix search. The two-pointer problems make exactly n − 1 comparisons, because each one retires a position and there are n positions to retire. That’s the cleanest kind of complexity argument there is, and it’s the same counting argument as the “at most n swaps” in the cycle sort post.
The exceptions: 221 is O(mn) time and O(mn) space, reducible to O(n) space by keeping only the previous row, since the recurrence never looks back further than that. 1150 is O(log n) as written above and O(n) if you count.
Edge cases and common bugs
- Precedence in a mixed
&&/||guard —a && b || cis(a && b) || c, so a leading guard protects only what’s next to it. Bracket the alternation explicitly, and build with-Wparentheses, which catches exactly this. - Widening the result instead of an operand —
long long sum = a + b;adds inintand then widens, so it prevents nothing. If the sum can overflow you must cast an operand:(long long)a + b. This looks like protection in review, which is what makes it dangerous. size_tfor a right-hand pointer —size_t right = v.size() - 1;wraps to roughly 1.8 × 1019 on an empty container. Useint right = (int)v.size() - 1;so the loop just doesn’t run.- Moving the taller pointer in 11 or 42 — the discard proof only covers the shorter side. Moving the taller one deletes a candidate that could still win, and the failure is a plausible-looking answer that’s slightly too small.
- Seeding a running best with zero when the answer can be negative — 53 must start from
nums[0]. Starting from 0 returns 0 on an all-negative array, and the problem requires a non-empty slice. - Subtracting from a sentinel — computing
price - cheapestbeforecheapesthas ever been assigned means subtracting fromINT_MAX. Update the running minimum first. while (left <= right)in a two-pointer scan — in 167 that pairs an element with itself, which the problem forbids. The condition is strictly<.- Updating the running best in the wrong order — in 1014, folding
jintobestLeftbefore scoring the pair lets an index pair with itself. - Trusting Boyer–Moore without the guarantee — 169 promises a majority exists. If it doesn’t, the survivor is meaningless and needs a verification pass.
Inputs worth running by hand: a single element; two elements; an array already in the target arrangement; an entirely descending array; an array where every value is identical; and for 53, all negatives.
Interview follow-ups
- “Solve 42 a different way.” — two other routes: precompute the running maximum from each end into two arrays, which is O(n) space and much easier to explain; or a monotonic stack that settles water in horizontal layers instead of columns.
- “What if a majority isn’t guaranteed?” — add the verification pass. Then the natural sequel is 229, where you want everything appearing more than n/3 times, and Boyer–Moore generalises to two candidates because at most two values can clear that bar.
- “What if only the rows are sorted, not the columns?” — the staircase collapses and you’re back to a binary search per row at O(m log n). Knowing which property you were relying on is the point of the question.
- “Now allow more than one transaction.” — 121 opens into 122, 123 and 188, where the single running minimum becomes a small state machine.
- “Return the subarray, not the sum.” — Kadane needs two extra indices: where the current slice started, and the bounds of the best one seen.
How to recognize it next time
The signal is a brute force that enumerates pairs or slices, combined with some ordering you can exploit — a sorted array, a monotonic quantity, a promise that an answer exists. Then ask the only question that matters: after one comparison, what can I delete and never reconsider?
If the answer is “one element”, you have a linear scan and you’ve gained nothing. If it’s “every pair involving this position”, or “this whole row”, or “this person, forever”, you have a decrease-and-conquer solution and the code will be about ten lines.
And when nothing can be deleted, don’t force it. 221 is on this list as a reminder that the honest answer is sometimes to fill in a table instead.
This walkthrough follows a session deck on decrease and conquer by Joseph Choi; the code here has been rewritten in a single consistent style and the explanations are my own. Every solution above was compiled and run against the problems’ sample cases and the edge cases listed, with the undefined-behaviour and address sanitizers on. If something here is wrong or there’s a cleaner way to say it, leave a comment. More problems: the LeetCode series.