Stable Three-Way Partition Around a Pivot
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
Given `nums` and a value `pivot` that occurs in it, return a rearrangement with all entries below the pivot first, all entries equal to it next and all entries above it last. Preserve the original relative order among the below-pivot entries and, separately, among the above-pivot entries. Retain every occurrence of every value.
```cpp
class Solution {
public:
vector<int> pivotArray(vector<int>& nums, int pivot);
};
```
### Examples
**Example 1:**
```text
nums = [4,1,3,2,5], pivot = 3
Output: [1,2,3,4,5]
Explanation: The smaller sequence 1,2 and larger sequence 4,5 retain their order.
```
**Example 2:**
```text
nums = [2,-1,2,0,3], pivot = 2
Output: [-1,0,2,2,3]
Explanation: Both copies of the pivot occupy the middle group.
```
### Constraints
- `1 <= nums.length <= 10^5`.
- `-10^6 <= nums[i] <= 10^6`; pivot equals an input entry.
### Clarifying Questions
Partitioning does not permit sorting within the smaller or larger group. An output buffer is allowed by the given task.
```hint Inspect the structure
Can three source-order passes guarantee stability without a complicated in-place partition?
```
### Reasoning checkpoints
- Place the three value groups in the required order with no entries lost or duplicated.
- Preserve relative order within the below-pivot and above-pivot groups.
- Handle repeated pivot entries and cases where either outer group is empty.
### Optional extensions
What algorithmic tradeoff appears if constant auxiliary memory is required?
Overview: Stable Three-Way Partition Around a Pivot. Rearrange nums so entries smaller than pivot come first, entries equal to it next, and larger entries last. Preserve relative order within the smaller group and within the larger group. Return the rearranged array; pivot is guaranteed to occur in nums.
