Partition Array According to Given Pivot — Editorial

Opening the reading…

Intuitionstability comes from collecting values in encounter order

The required result has three consecutive regions: values below pivot, values equal to pivot, and values above pivot. The important extra condition is that each region must keep the order its values had in nums. That means a value cannot simply be moved into the correct region by swapping, because the swap may make two values in the same region change places.

Scan nums from left to right and give every value to exactly one group. Appending to a group preserves the order automatically: the first less-than value reaches less before the second one, and the same is true for equal and greater. Once the scan ends, placing the three groups after one another satisfies both the value restrictions and the stability requirement.

Approach

Create separate vectors named less, equal, and greater, because one destination per category lets you preserve encounter order without rearranging values already collected.

Scan nums from index 0 to n - 1 and test each value against pivot, because every input value must appear exactly once in the result.

Append x to less when x < pivot, because this is the only group allowed before the pivot values.

Append x to equal when x == pivot, because all pivot values must occupy the middle region and remain in their original relative order.

Append x to greater for the remaining case, because x > pivot is the only classification left and those values must come after equal.

Append equal and then greater to less, because less already contains the first region and this order creates the required less, equal, greater layout without another result array.

Return less after the concatenations, because it now contains every input value exactly once in the required order.

Complexityone classification pass and linear working storage

MEASURE	BOUND	WHY
Time	O(n)	The scan examines each input element once. The two insert operations copy the equal and greater groups once, while the less elements are already in the returned vector, so the total number of element operations is at most a constant multiple of n.
Space	O(n)	The three temporary groups together hold every input element, so their total capacity is linear. The returned array is required output and is excluded; in the worst shape, all n values can belong to one group, which still gives O(n) extra space.

Here, n is the length of nums. The returned vector is required output and is excluded from the extra-space bound.

Annotated solutionC++ · stable three-group partition · complete judge-ready solution

CPPClassify values in one pass, then concatenate the three stable groups.

#include <vector>
using namespace std;

class Solution {
public:
    vector<int> pivotArray(vector<int>& nums, int pivot) {
        vector<int> less, equal, greater;

        for (int x : nums) {
            if (x < pivot) {
                less.push_back(x);
            } else if (x == pivot) {
                equal.push_back(x);
            } else {
                greater.push_back(x);
            }
        }

        less.insert(less.end(), equal.begin(), equal.end());
        less.insert(less.end(), greater.begin(), greater.end());
        return less;
    }
};

The range-based loop is the stability mechanism: values enter each vector in exactly the order they appear in nums. The insert calls deliberately target less, turning it into the final output in two stages. Since the output is returned by value, the temporary group storage is separate from the input and the caller receives the completed arrangement.