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
pivotcomes 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^6pivot equals some element of nums
Hints for Partition Array According to Given Pivot
Hint 1
An in-place swap-based partition (as in quicksort) is not stable — it scrambles the order inside a group.
Hint 2
Use an output array and fill it group by group.
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
- Create a result array and a write index at 0.
- Scan
nums; append every value smaller thanpivot. - Scan again; append every value equal to
pivot. - 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
pivotmay 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 + greaterJava
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