After the Sort: Partition and Two Pointers in C++

Posted on by NY Comdori

Sorting an array to answer a question about it is often the wrong move, and this post is about the two ways to notice.

The first: sometimes you do not need the array sorted, only partly sorted. Quicksort’s partition step puts one element in its final place and separates everything else into two sides — and if all you want is the k-th largest, that single step is enough, and repeating it is O(n) rather than O(n log n). Four problems below are that idea.

The second: sometimes you do want it sorted, and then sorted order pays you back by replacing a data structure. Five problems below are the ones everyone first solves with a hash map, where sorting instead drops the space from O(n) to O(1) and — the deck’s point — is what an interviewer is actually looking for.

This closes a three-part series on Joseph Choi’s sorting session deck; part one covered the algorithms and part two covered intervals. Everything was compiled with -Wall -Wextra -Wshadow -fsanitize=undefined,address under both C++17 and C++20 and checked against brute force before the prose was written.

Part 1: the partition step, on its own

Recall what quicksort’s partition does. Pick a pivot; rearrange so everything smaller sits left of it and everything larger sits right; return where the pivot landed. The pivot is now in its final sorted position, and you learned that without sorting either side.

Quicksort then recurses on both halves. Quickselect recurses on one. That is the whole difference, and it is what turns O(n log n) into O(n) on average: each level of recursion halves the work instead of preserving it, so the total is n + n/2 + n/4 + … which sums to 2n rather than n log n.

Kth Largest Element in an Array (LC 215, Medium)

The deck lays out the ladder honestly: sort and index, O(n log n); a size-k heap, also O(n log k); or partition, average O(n). It also notes counting sort works and costs space. Then it asks the question that matters — is there anything that gets this to O(n)?

int partition215(vector<int>& nums, int left, int right) {
    int pivot_index = rand() % (right - left + 1) + left;
    int pivot = nums[pivot_index];
    swap(nums[pivot_index], nums[right]);
    int idx = left;
    for (int i = left; i < right; i++) if (nums[i] < pivot) swap(nums[i], nums[idx++]);
    swap(nums[right], nums[idx]);
    return idx;
}
int findKthLargest(vector<int>& nums, int k) {
    int left = 0, right = nums.size() - 1;
    while (true) {
        int pivot = partition215(nums, left, right);
        if (pivot == (int)nums.size() - k) return nums[pivot];
        else if (pivot > (int)nums.size() - k) right = pivot - 1;
        else left = pivot + 1;
    }
}

The k-th largest sits at index n - k once sorted, so the loop partitions until the pivot lands exactly there. If the pivot is too far right, search left; too far left, search right. No merge, no second recursion, no sort.

The random pivot is the whole ballgame, and it is worth connecting to part one. There I measured what a fixed last-element pivot does to quicksort: on already-sorted input at n = 4,000 it cost 7,998,000 comparisons against 59,822 on random input — exactly n(n−1)/2, the theoretical worst case, to the comparison. Quickselect degrades the same way, and LC 215’s test suite is known to include sorted and adversarial inputs. rand() % (right - left + 1) + left is not a stylistic flourish; it is what stops the solution timing out.

Notice too that the deck writes the teaching version of quicksort with a fixed pivot and the production version here with a random one. That is the right instinct, and worth copying: the simplest pivot is fine for explaining the idea and not fine for running it.

One honest caveat on the complexity: average O(n), worst case still O(n²), and randomisation makes the bad case unlikely rather than impossible. If you need a hard guarantee there is median-of-medians, which is O(n) worst case and slower in practice on every realistic input — which is why nobody uses it.

K Closest Points to Origin (LC 973, Medium)

The same algorithm with the comparison key changed from the value to a distance.

int partition973(vector<vector<int>> &points, int start, int end) {
    int pivot = end;
    long long pivotDistance = (long long)points[pivot][0]*points[pivot][0] + (long long)points[pivot][1]*points[pivot][1];
    int idx = start;
    for (int i = start; i < end; ++i) {
        long long distance = (long long)points[i][0]*points[i][0] + (long long)points[i][1]*points[i][1];
        if (distance <= pivotDistance) swap(points[i], points[idx++]);
    }
    swap(points[pivot], points[idx]);
    return idx;
}
void quickSelect973(vector<vector<int>> &points, int k) {
    int start = 0, end = points.size() - 1;
    while (start <= end) {
        int pivot = partition973(points, start, end);
        if (pivot == k - 1) return;
        else if (pivot < k - 1) start = pivot + 1; else end = pivot - 1;
    }
}
vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
    quickSelect973(points, k);
    return vector<vector<int>>(begin(points), begin(points) + k);
}

Two things earn their place. The distance is computed as x*x + y*y with no square root — comparing squared distances gives the same ordering as comparing distances, and skipping sqrt avoids both the cost and the floating-point equality mess. That trick generalises to any monotone transform of a key.

And the cast to long long is mandatory. Coordinates go to 10⁴, so a squared distance reaches 2 × 10⁸ — which fits in an int — but the habit is worth keeping, because the same expression with coordinates at 10⁵ overflows and the failure is a silently wrong ordering rather than a crash.

Note the loop here is while (start <= end) where LC 215 used while (true). Both terminate, because the pivot index always lands inside the current window and the window always shrinks, but the bounded form is the one I would write — a while (true) that relies on a return for termination is a bad habit even when it is correct.

Top K Frequent Elements (LC 347, Medium)

Third time, and now the key is one level of indirection away: count the frequencies, then quickselect over the distinct values ordered by their counts.

int partition347(vector<int> &nums, unordered_map<int,int> &freq, int start, int end) {
    int pivot = end, idx = start;
    for (int i = start; i < end; ++i) if (freq[nums[i]] >= freq[nums[pivot]]) swap(nums[i], nums[idx++]);
    swap(nums[pivot], nums[idx]);
    return idx;
}
vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int,int> freq;
    for (int num : nums) ++freq[num];
    vector<int> unique;
    for (const auto &p : freq) unique.push_back(p.first);
    int start = 0, end = unique.size() - 1;
    while (start <= end) {
        int pivot = partition347(unique, freq, start, end);
        if (pivot == k - 1) return vector<int>(begin(unique), begin(unique) + pivot + 1);
        else if (pivot < k - 1) start = pivot + 1; else end = pivot - 1;
    }
    return {};
}

The partition compares freq[nums[i]] >= freq[nums[pivot]] — note the >=, which sorts descending, so the k most frequent end up at the front and the answer is the prefix. Getting that operator backwards gives you the k least frequent with no other symptom.

The reason this is worth doing over the obvious heap is the complexity: building the frequency map is O(n), and quickselect over the m distinct values is O(m) average, so the whole thing is O(n) — against O(n log k) for the heap and O(n log n) for sorting by count. LC 347 explicitly asks for better than O(n log n), and this is the answer it is fishing for.

One subtlety about the problem rather than the code: LC 347 guarantees the answer is unique, which matters because ties in frequency would make “the top k” ambiguous. When I tested this against brute force I had to skip the cases where the k-th and (k+1)-th frequencies are equal, because in those cases several outputs are equally valid and the problem promises they do not occur.

Sort Colors (LC 75, Medium)

The deck files this as a variation on partition, and that is exactly the right framing: partition splits an array in two, and this problem needs it split in three. It also flags the tricky part in advance — when you swap something down from the blue end, what if the thing you swapped in is red?

void sortColors(vector<int>& nums) {
    int rIdx = 0, bIdx = nums.size() - 1, i = 0;
    while (i <= bIdx) {
        if (nums[i] == 0) swap(nums[i++], nums[rIdx++]);
        else if (nums[i] == 2) swap(nums[i], nums[bIdx--]);
        else ++i;
    }
}

This is the Dutch national flag partition. Three indices: rIdx is where the next 0 goes, bIdx is where the next 2 goes, and i is the scanner. The loop condition is i <= bIdx, because everything above bIdx is already known to be a 2.

The answer to the deck’s question is in the asymmetry of the two branches, and it is the single thing to understand here. On a 0 we advance i as well as rIdx; on a 2 we do not advance i. Why: the value swapped in from the front is one we have already scanned, so it can only be a 1 — safe to move past. The value swapped in from the back has never been examined, so it could be anything, including a 0, and it has to be re-examined on the next iteration. Advance i in the 2-branch and you leave 0s stranded in the middle.

One pass, O(1) space, which is what the problem’s follow-up asks for. The two-pass counting-sort solution — count the 0s, 1s and 2s, then overwrite — is easier and perfectly acceptable if the follow-up is not asked; this version exists because it is.

Part 2: when sorting replaces the hash map

Now the other direction. Two Sum on an unsorted array is the canonical hash-map problem: one pass, O(n) time, O(n) space. The deck’s question is what happens when you move to three numbers, and its answer reframes the whole family.

Brute force is three loops, O(n³), which the deck calls evil. Reusing Two Sum gives O(n²) time with O(n) space for the hash map. But sort the array first and you get O(n²) time with O(1) space, because in sorted order you can replace the hash lookup with two indices walking inward: if the sum is too small, the only way to increase it is to move the left pointer right; too large, move the right pointer left.

The deck is explicit that the sorted version is the preferred interview answer, and its reasoning is worth quoting in spirit: same time complexity, better space. Sorting costs O(n log n), which disappears inside the O(n²) you were already paying.

There is a second payoff the deck brings out across the next four problems, and it is the bigger one. A hash map answers “is this exact value present?” It cannot answer “what is the closest value,” or “how many values are below this.” Sorted order can. Every problem below asks an inequality question, and that is precisely why the hash map stops working.

3Sum (LC 15, Medium)

vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> result;
    sort(nums.begin(), nums.end());
    int n = nums.size();
    for (int i = 0; i + 2 < n; ++i) {              // need two more elements to the right
        if (i > 0 && nums[i] == nums[i-1]) continue;   // skip a repeated anchor
        int left = i + 1, right = nums.size() - 1;
        while (left < right) {
            int sum = nums[left] + nums[right] + nums[i];
            if (sum < 0) ++left;
            else if (sum > 0) --right;
            else {
                result.push_back({nums[i], nums[left++], nums[right--]});
                for (; left < right && nums[left] == nums[left-1]; ++left);
            }
        }
    }
    return result;
}

Fix an anchor, then two-pointer the rest. The structure is simple; the duplicate handling is where this problem is won or lost, and there are two separate places it happens.

The anchor: if (i > 0 && nums[i] == nums[i-1]) continue; — if this anchor value was already used, every triplet it could form was already found. The i > 0 guard is what keeps nums[i-1] in bounds.

The left pointer, after a hit: for (; left < right && nums[left] == nums[left-1]; ++left); — having recorded a triplet and advanced left, skip any repeats of the value just used. Without it, [-2,0,0,2,2] reports [-2,0,2] twice.

Notice there is no explicit dedup on the right pointer, and it is not needed: once left has moved past all copies of its old value, any repeat of the old right value pairs with a different left value and so produces a different sum. I checked that reasoning rather than trusting it — 20,000 random arrays drawn from a nine-value range, comparing against a brute-force triple loop, asserting both that the set of triplets matches and that the output contains no duplicates.

One change from the deck: it declares int i = 0; just before the for loop that declares its own i, so the outer one is shadowed and unused. Harmless, but -Wshadow flags it and it is the kind of thing that becomes a real bug when someone later edits the loop. I also bounded the anchor at i + 2 < n, since an anchor with fewer than two elements to its right cannot form a triplet.

Two Sum Less Than K (LC 1099, Easy, Premium)

Note: Premium. Find the maximum sum of two distinct elements that is strictly less than k, or −1 if there is none.

The deck states the key observation plainly: a hash table does not help here, because you are not looking for an exact value. That one sentence is the reason this whole section exists.

int twoSumLessThanK(vector<int>& nums, int k) {
    sort(begin(nums), end(nums));
    int maxSum = INT_MIN, left = 0, right = nums.size() - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum >= k) --right; else { maxSum = max(maxSum, sum); ++left; }
    }
    return maxSum == INT_MIN ? -1 : maxSum;
}

Sum too big means the only useful move is to shrink it, so decrement right. Sum small enough means it is a candidate — record it — and the only way to find a larger valid sum is to increment left. O(n log n) for the sort and O(n) for the walk.

The INT_MIN sentinel handles “no valid pair exists,” and the final ternary converts it to the −1 the problem wants. Using 0 or −1 as the sentinel instead would break on inputs with negative values, where a legitimate answer can be negative.

3Sum Closest (LC 16, Medium)

Again an inequality question rather than an equality one — the deck’s note is that the distance could be +2 or −2, so you are minimising an absolute difference.

int threeSumClosest(vector<int>& nums, int target) {
    sort(begin(nums), end(nums));
    long long closest = INT_MAX;
    for (int i = 0; i < (int)nums.size(); ++i) {
        int left = i + 1, right = nums.size() - 1;
        while (left < right) {
            long long sum = nums[i] + nums[left] + nums[right];
            if (sum == target) return sum;
            else if (sum > target) --right; else ++left;
            long long sumDiff = llabs(sum - target);
            long long closestDiff = llabs(closest - target);
            closest = sumDiff < closestDiff ? sum : closest;
        }
    }
    return closest;
}

Same skeleton as 3Sum, with the exact-match check replaced by a running best. The early return on an exact hit is a genuine optimisation, not just tidiness: nothing can beat a distance of zero.

The long long is defensive rather than necessary — LC 16 caps values at 1,000 and length at 500, so three of them sum well inside int. It costs nothing and it means the abs(sum - target) subtraction cannot overflow, which is the expression that would actually be at risk if the constraints grew.

Worth knowing about abs in C++: the overload that takes a long long lives in <cstdlib> as std::abs, and if you end up calling the C int abs(int) instead, a 64-bit argument gets silently narrowed. I checked what that costs — abs on a value of 5,000,000,000 returns 705,032,704 through the narrowing overload. On LeetCode with bits/stdc++.h the right overload is found and this is a non-issue; in a project with tighter includes it is a real one, and llabs or an explicit std::abs removes the ambiguity.

3Sum With Multiplicity (LC 923, Medium)

Count the triples of indices summing to the target, modulo 10⁹+7. Now duplicates are not a nuisance to be skipped — they are the entire answer, and the deck asks the right question: how do you count duplicate pairs efficiently?

int threeSumMulti(vector<int>& arr, int target) {
    sort(begin(arr), end(arr));
    long long result = 0;
    for (int i = 0; i < (int)arr.size(); ++i) {
        int left = i + 1, right = arr.size() - 1;
        while (left < right) {
            int sum = arr[i] + arr[left] + arr[right];
            if (sum == target) {
                if (arr[left] == arr[right]) {
                    result += (long long)(right - left + 1) * (right - left) / 2;
                    break;
                }
                int leftIdx = left + 1;
                for (; leftIdx < right && arr[left] == arr[leftIdx]; ++leftIdx);
                int rightIdx = right - 1;
                for (; rightIdx > left && arr[right] == arr[rightIdx]; --rightIdx);
                result += (long long)(leftIdx - left) * (right - rightIdx);
                left = leftIdx; right = rightIdx;
            } else if (sum < target) ++left; else --right;
        }
    }
    return result % 1000000007;
}

Two cases, and the deck names both. When arr[left] != arr[right], count how many copies of each value sit at the two ends and multiply: every copy on the left pairs with every copy on the right, so the contribution is (leftCount) × (rightCount). Then jump both pointers past those runs.

When arr[left] == arr[right], the whole window is one repeated value and pairing is no longer a product — it is a choice of two from m equal elements, which is m(m−1)/2. The deck’s example is exactly this: five 2s with target 4 gives 5C2 = 10. Using the product formula here would count ordered pairs and double the answer; this is the one place in the post where a combinatorial identity replaces a loop, and it is also why the branch breaks — the window is fully consumed.

The accumulator is long long and the modulo is applied once at the end. That is safe at these constraints — length 3,000 gives at most about 4.5 × 10⁹ index triples, which fits — but it is close enough that taking the modulo inside the loop would be the more defensive habit.

3Sum Smaller (LC 259, Medium, Premium)

Note: Premium. Count the index triples whose sum is strictly less than the target.

The deck’s question is the whole solution: how do you quickly count all the pairs when the current sum is already below the target?

int threeSumSmaller(vector<int>& nums, int target) {
    sort(begin(nums), end(nums));
    int result = 0;
    for (int i = 0; i < (int)nums.size(); ++i) {
        int left = i + 1, right = nums.size() - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum >= target) { --right; continue; }
            result += right - left;
            ++left;
        }
    }
    return result;
}

The line is result += right - left;, and it is the best single idea in this post. If nums[i] + nums[left] + nums[right] is below the target, then every element between left and right also works as the third member — because they are all at most nums[right], so all those sums are at most this one. That is right - left triples counted in one operation, with no inner loop.

This is what sorted order buys that a hash map never could. The question “how many values are below this one” is answered by a subtraction of indices, and it is only meaningful because the data is ordered. Getting the count off by one here is the standard mistake: it is right - left and not right - left + 1, because right itself is the element already in the sum.

The nine problems on one page

ProblemTechniqueKey or comparisonTimeSpace
215 Kth Largestquickselectvalue; target index n − kO(n) avgO(1)
973 K Closest Pointsquickselectx² + y², no sqrtO(n) avgO(1)
347 Top K Frequentquickselectfrequency, descendingO(n) avgO(m)
75 Sort Colors3-way partition0 / 1 / 2, one passO(n)O(1)
15 3Sumsort + two pointerssum == 0, dedup twiceO(n²)O(1)
1099 Two Sum < Ksort + two pointersmax sum < kO(n log n)O(1)
16 3Sum Closestsort + two pointersmin abs(sum − target)O(n²)O(1)
923 3Sum Multiplicitysort + two pointerscount; product or mC2O(n²)O(1)
259 3Sum Smallersort + two pointerscount via right − leftO(n²)O(1)

Every entry in the space column is O(1) except the frequency map, and that is the point of the whole post.

Misfits, edge cases, and the things that bite

A fixed pivot is a timeout waiting to happen

Measured in part one: the same Lomuto partition with a last-element pivot took 7,998,000 comparisons on sorted input against 59,822 on random input at n = 4,000, a factor of 134, and landed on exactly the theoretical worst case. Quickselect inherits this. Randomise the pivot in every partition-based solution you write, including the three above.

3Sum needs dedup in two places, not one

The anchor skip and the post-hit left skip are separate mechanisms and both are required. [0,0,0,0] catches a missing anchor skip; [-2,0,0,2,2] catches a missing left skip. Neither shows up on the problem’s own sample inputs, which is why this problem has a reputation for passing locally and failing on submission.

Sort Colors: why one branch advances the scanner and the other does not

The 0-branch advances i; the 2-branch does not. The value swapped in from the front has already been scanned and must be a 1; the value swapped in from the back is unexamined and could be a 0. Advance in both and 0s get stranded. The shortest failing input is [2,0] — it becomes [0,2] correctly only because the un-advanced i re-examines the swapped-in 0.

Counting problems need combinatorics, not another loop

LC 923’s equal-ends case is m(m−1)/2 and not a product, and LC 259 counts right - left triples in one statement. Both are places where reaching for an inner loop is the difference between O(n²) and O(n³). When a problem says “count” rather than “find,” the first question is whether the answer for a whole run can be computed in closed form.

Two type notes

Squared distances need width. At LC 973’s constraints x*x + y*y fits in an int, but the cast costs nothing and the overflow failure mode is a wrong ordering with no crash.

abs has overloads that narrow. Calling the C int abs(int) on a 64-bit value truncates — abs of 5,000,000,000 comes back as 705,032,704 through that path. Fine on LeetCode, a real hazard elsewhere; llabs or a qualified std::abs settles it.

When these are the wrong tools

  • You cannot modify the input. Quickselect rearranges the array in place. If that is forbidden, you are back to a heap, and the O(n) result is gone.
  • The data is a stream. Quickselect needs random access and multiple passes. For a running k-th largest, a size-k heap is the answer and it is the only one that works online.
  • k is tiny and n is huge. A size-k heap is O(n log k) and touches each element once, which beats quickselect’s repeated passes in cache behaviour even though the asymptotics favour quickselect.
  • The question is about exact membership. Two Sum on an unsorted array really is a hash-map problem — O(n) beats O(n log n), and sorting there is a pessimisation. The two-pointer trade only pays when the question is an inequality, or when the array is sorted already, or when O(1) space is required.
  • You need the original indices. Sorting destroys them. LC 1 returns indices, which is why it is a hash-map problem and 3Sum — which returns values — is not.

How to practise this

  1. Write the Lomuto partition from memory, then turn it into quickselect by deleting one recursive call. If you can do that, three of these problems are done.
  2. Before sorting an array, ask what you are giving up: the original indices, and O(n) if the question was about exact membership.
  3. For any two-pointer problem, say out loud why moving each pointer is safe. “The sum is too small, and the only way to increase it is to move left” is the sentence.
  4. Test [0,0,0,0], [-2,0,0,2,2] and [2,0]. Between them they catch the dedup and scanner bugs above.
  5. In order: 75 → 215 → 973 → 347, then 1099 → 15 → 16 → 259 → 923. The first group is one partition four ways; the second builds from two pointers on a pair to counting with combinatorics.

The rest of this series

Credit and the rest of the series

The problem selection, the ordering, and the framing come from Joseph Choi‘s sorting session deck — including the ladder of approaches for LC 215 and the question about getting to O(n), the reading of Sort Colors as a three-way partition plus the warning about what gets swapped in from the back, the argument that the sorted 3Sum is the preferred interview answer on space grounds, the observation that a hash table cannot answer an inequality question, and the two counting questions that make LC 923 and LC 259 tractable. The C++ here is my own, rewritten where I preferred different types or a removed shadow, and every listing was compiled and differentially tested before publication.

Other pattern write-ups on this site: