medium

Partition Array According to a Pivot Value

Rearrange an array into less-than, equal-to, and greater-than groups around a pivot value.

1. Define the problem

Partition Array According to a Pivot Value

Given an integer array nums and an integer pivot, rearrange nums such that all elements smaller than pivot come first, then all elements equal to pivot, then all elements greater than pivot. The relative order of elements within each of the three groups must stay the same as the original array . Unlike the classic in-place swap partition, this needs a stable partition : walk through once, and collect the three groups in the order you see them.

Constraints

  • 1 ≤ nums.length ≤ 105
  • -106 ≤ numsi ≤ 106
  • pivot equals an element of nums

Example

Inputnums = [9, 12, 5, 10, 14, 3, 10], pivot = 10
Output[9, 5, 3, 10, 10, 12, 14]

Explanation The elements smaller than 10 are 9, 5, 3 (in original order); the elements equal to 10 are 10, 10; the elements greater than 10 are 12, 14.

2. Know the words first

In plain terms

Stable partition
A partition that preserves the original relative order of elements within each resulting group, instead of freely swapping them around.
3. Visualize the solution

Walk once, sort each value into its group in order

Walk once, sort each value into its group in order
Status9 < 10

pivot = 10. 9 is less than the pivot — append it to the 'less' group.

What happens in this step

pivot = 10
nums[0] = 9

9 < 10 → append to "less": less=[9], equal=[], greater=[]
Step 1 of 5

Steps to visualize

  1. Scan the array left to right, one pass.
  2. If the value is smaller than the pivot, append it to the "less" group.
  3. If it equals the pivot, append it to the "equal" group.
  4. If it is larger, append it to the "greater" group.
  5. Concatenate less, then equal, then greater — each group keeps its original relative order.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Walk once, sort each value into its group in order
Status9 < 10

pivot = 10. 9 is less than the pivot — append it to the 'less' group.

What happens in this step

pivot = 10
nums[0] = 9

9 < 10 → append to "less": less=[9], equal=[], greater=[]
Step 1 of 5
5. Solution

Solution

solution.tsTypeScript
function pivotArray(nums, pivot) {
  const less = [];
  const equal = [];
  const greater = [];

  for (const num of nums) {
    if (num < pivot) less.push(num);
    else if (num === pivot) equal.push(num);
    else greater.push(num);
  }

  return [...less, ...equal, ...greater];
}
Time
O(n)
Space
O(n)
6. Test cases

Test cases

InputExpectedCovers
nums = [9, 12, 5, 10, 14, 3, 10], pivot = 10[9, 5, 3, 10, 10, 12, 14]example from the docstring
nums = [-3, 4, 3, 2], pivot = 2[-3, 2, 4, 3]negative and positive values around the pivot
nums = [1, 2, 3], pivot = 5[1, 2, 3]every value smaller than the pivot
nums = [7, 8, 9], pivot = 1[7, 8, 9]every value greater than the pivot
nums = [4, 4, 4], pivot = 4[4, 4, 4]every value equal to the pivot
nums = [5], pivot = 5[5]smallest valid input, a single element equal to the pivot
nums = [-1, -5, 0, -1, 3], pivot = -1[-5, -1, -1, 0, 3]negative pivot with duplicate values equal to it

Keep reading