DSA SheetMedium
EditorialPractice

2 POINTERS › TWO POINTER ON ARRAYS

Partition Array According to Given Pivot

MediumEditorial · 6 minGenerated by gpt-5.6-luna · Aug 26

Open — the attempt gate is not wired up yet

This editorial is meant to unlock after you have run the problem at least once, with the worked solution behind one further deliberate click. That needs per-learner unlock state nothing stores today, so for now the whole article is open.

Try it yourself first →

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.

An input array split into three stable groups around a pivotThe picture shows an input array on the left and three empty groups on the right, labelled less, equal, and greater. A left-to-right scan sends each input value to exactly one group: smaller values go to less, pivot values go to equal, and larger values go to greater. The values within each group appear in the same order as in the input. The three groups are then joined into one result array in the order less, equal, greater, making the preserved internal order visible.735385293325578933255789values < 5values = 5values > 5append in orderthen appendthen appendinput — scan left → rightpivot = 5 · each group keeps encounter order

Approach

  1. Create separate vectors named less, equal, and greater, because one destination per category lets you preserve encounter order without rearranging values already collected.
  2. 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.
  3. Append x to less when x < pivot, because this is the only group allowed before the pivot values.
  4. Append x to equal when x == pivot, because all pivot values must occupy the middle region and remain in their original relative order.
  5. Append x to greater for the remaining case, because x > pivot is the only classification left and those values must come after equal.
  6. 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.
  7. 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

MEASUREBOUNDWHY
TimeO(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.
SpaceO(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.

Common mistakestwo ways to lose the required stable order or grouping

Previous · Remove Element