medium

Pivot Array

Partition an array around a pivot value while keeping relative order.

1. Define the problem

Pivot Array

You are given an integer array nums and an integer pivot. Rearrange nums so that every element less than pivot comes first, then every element equal to pivot , then every element greater than pivot. Within each of those three groups, the elements must keep the same relative order they had in the original array. Walk the array once and drop each value into one of three buckets — smaller, equal, or bigger — then glue the buckets back together in that order.

Constraints

  • 1 ≤ nums.length ≤ 105
  • -106 ≤ numsi ≤ 106
  • -106 ≤ pivot ≤ 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 Values less than 10 (9, 5, 3) come first in their original order, then the two 10s, then values greater than 10 (12, 14) in their original order.

2. Know the words first

In plain terms

Relative order
If value A came before value B in the original array, A must still come before B after rearranging, as long as they land in the same group.
3. Visualize the solution

Sort each value into one of three buckets

Sort each value into one of three buckets
Statusinit

nums[0]=9 < pivot(10) — drop it into the smaller bucket.

What happens in this step

index = 0, value = 9
9 < 10, so 9 goes into the "smaller" bucket.
smaller = [9], equal = [], bigger = []
Step 1 of 6

Steps to visualize

  1. Set up three empty buckets: smaller, equal, and bigger.
  2. Walk the array from left to right, one value at a time.
  3. Drop each value into the bucket that matches how it compares to the pivot.
  4. Once every value has been sorted into a bucket, join the three buckets end to end: smaller, then equal, then bigger.
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.

Sort each value into one of three buckets
Statusinit

nums[0]=9 < pivot(10) — drop it into the smaller bucket.

What happens in this step

index = 0, value = 9
9 < 10, so 9 goes into the "smaller" bucket.
smaller = [9], equal = [], bigger = []
Step 1 of 6
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 = [1], pivot = 1[1]smallest valid input: a single element equal to the pivot
nums = [5, 5, 5], pivot = 5[5, 5, 5]every value equals the pivot
nums = [1, 2, 3, 4], pivot = 4[1, 2, 3, 4]every value except the pivot is smaller than it
nums = [-3, -1, -5, 0, -1], pivot = -1[-3, -5, -1, -1, 0]negative values with a negative pivot appearing twice
nums = [3, 1, 4, 1, 5], pivot = 3[1, 1, 3, 4, 5]the pivot value appears at the front of the array

Keep reading