Partition Array According to Given Pivot

Medium
1150.

Partition Array According to Given Pivot

Partition Array According to Given Pivot is a medium coding problem on arrays, two pointers and simulation, asked in Amazon and Microsoft interviews.

Rearrange the integer array nums around the value pivot so that:

  • every element smaller than pivot comes first,
  • then every element equal to pivot,
  • then every element greater than pivot.

Inside the "smaller" group and inside the "greater" group the elements must keep the relative order they had in nums (the partition is stable). Return the rearranged array.

Example 1

Input
nums = [7,2,11,4,7,15,1], pivot = 7
Output
[2,4,1,7,7,11,15]
Explanation
`2, 4, 1` are smaller and stay in that order; `11, 15` are greater and stay in that order.

Example 2

Input
nums = [-3,8,-1,5], pivot = 5
Output
[-3,-1,5,8]

Example 3

Input
nums = [4], pivot = 4
Output
[4]

Constraints

  • 1 <= nums.length <= 10^5
  • -10^6 <= nums[i] <= 10^6
  • pivot equals some element of nums
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} pivot
 * @return {number[]}
 */
var pivotArray = function(nums, pivot) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Partition Array According to Given Pivot — Solution

Partition Array According to Given Pivot solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Partition Array According to Given Pivot is a medium coding problem on arrays, two pointers and simulation, asked in Amazon and Microsoft interviews.

  • Difficulty: Medium
  • Topics: Arrays, Two Pointers, Simulation
  • Asked at: Amazon, Microsoft
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Rearrange the integer array nums around the value pivot so that:

  • every element smaller than pivot comes first,
  • then every element equal to pivot,
  • then every element greater than pivot.

Inside the "smaller" group and inside the "greater" group the elements must keep the relative order they had in nums (the partition is stable). Return the rearranged array.

Example 1

Input: nums = [7,2,11,4,7,15,1], pivot = 7
Output: [2,4,1,7,7,11,15]
Explanation: `2, 4, 1` are smaller and stay in that order; `11, 15` are greater and stay in that order.

Example 2

Input: nums = [-3,8,-1,5], pivot = 5
Output: [-3,-1,5,8]

Example 3

Input: nums = [4], pivot = 4
Output: [4]

Constraints

  • 1 <= nums.length <= 10^5
  • -10^6 <= nums[i] <= 10^6
  • pivot equals some element of nums

Hints for Partition Array According to Given Pivot

  1. Hint 1

    An in-place swap-based partition (as in quicksort) is not stable — it scrambles the order inside a group.

  2. Hint 2

    Use an output array and fill it group by group.

  3. Hint 3

    Three passes over nums: copy the smaller values, then the equal ones, then the greater ones.

How to solve Partition Array According to Given Pivot

Stability is the whole difficulty, and an extra output array removes it: scanning nums from left to right and copying only one group per scan preserves each group's original order automatically.

Approach

  1. Create a result array and a write index at 0.
  2. Scan nums; append every value smaller than pivot.
  3. Scan again; append every value equal to pivot.
  4. Scan a third time; append every value greater than pivot.

Why it works

Each scan visits elements in their original order and appends them, so within a group the output order equals the input order. Every element belongs to exactly one of the three groups, so the result is a permutation of nums with the groups in the required sequence.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • The classic Lomuto/Hoare partition swaps elements and breaks the relative order.
  • Values equal to pivot may appear several times — all of them go in the middle.
  • A single pass with two pointers (smaller from the front, greater from the back) also works, but the back-filled group must then be written in reverse scan order.

Reference solution

Python

from typing import List

def pivotArray(nums: List[int], pivot: int) -> List[int]:
    less = [x for x in nums if x < pivot]
    equal = [x for x in nums if x == pivot]
    greater = [x for x in nums if x > pivot]
    return less + equal + greater

Java

public static int[] pivotArray(int[] nums, int pivot) {
    int n = nums.length;
    int[] res = new int[n];
    int w = 0;
    for (int x : nums) if (x < pivot) res[w++] = x;
    for (int x : nums) if (x == pivot) res[w++] = x;
    for (int x : nums) if (x > pivot) res[w++] = x;
    return res;
}

C++

vector<int> pivotArray(vector<int>& nums, int pivot) {
    vector<int> res;
    res.reserve(nums.size());
    for (int x : nums) if (x < pivot) res.push_back(x);
    for (int x : nums) if (x == pivot) res.push_back(x);
    for (int x : nums) if (x > pivot) res.push_back(x);
    return res;
}

JavaScript

var pivotArray = function(nums, pivot) {
    var res = [];
    for (var i = 0; i < nums.length; i++) if (nums[i] < pivot) res.push(nums[i]);
    for (var j = 0; j < nums.length; j++) if (nums[j] === pivot) res.push(nums[j]);
    for (var k = 0; k < nums.length; k++) if (nums[k] > pivot) res.push(nums[k]);
    return res;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Two Pointers Technique