Given a list of integers nums and an integer pivot, rearrange nums in place so that all values < pivot come first, then all values == pivot, then all values > pivot. The order inside each region does not matter. Return the tuple (below, equal) with the sizes of the first two regions.
Tests call (r := three_way(a := [...], p), sorted(a[:r[0]]), a[r[0]:r[0]+r[1]], sorted(a[r[0]+r[1]:])) and compare all four parts.
Examples
Input: nums = [3, 1, 2, 3, 0, 5, 3], pivot = 3
Output: (3, 3); nums becomes e.g. [1, 2, 0, 3, 3, 3, 5]
Input: nums = [9, 9], pivot = 1
Output: (0, 0)
Constraints
0 <= len(nums) <= 10**5- Target: O(n) time, O(1) extra space, a single pass.
Goals
- Maintain three regions (below, equal, unclassified, above) with three indices
- Know when to advance the scanning index and when not to after a swap