Three-Way Pivot Partitioning — Problem Statement & Solution Guide
Problem Description
Given an array of integers nums and an integer pivot, rearrange the elements of nums in-place such that all elements less than pivot appear first, followed by all elements equal to pivot, and finally all elements greater than pivot appear last. The relative order of the partitioned elements should be preserved.
Examples
Input
[3, 5, 5, 5, 9, 10, 12, 14]
Output
[3, 9, 10, 12, 14, 5, 5, 5]
Explanation: Step-by-step: With input [3, 5, 5, 5, 9, 10, 12, 14], we first partition the array into three parts: elements less than 5, elements equal to 5, and elements greater than 5. The relative order of the partitioned elements is preserved by iterating through the array only once.
Input
[1, 2, 4, 4, 7, 8]
Output
[1, 2, 4, 4, 7, 8]
Explanation: Step-by-step: With input [1, 2, 4, 4, 7, 8], we first partition the array into three parts: elements less than 4, elements equal to 4, and elements greater than 4. The relative order of the partitioned elements is preserved by iterating through the array only once.
Constraints
- 1 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
- -10^9 <= pivot <= 10^9
Optimal Approach & Strategy
We use Dijkstra's Dutch National Flag algorithm with three pointers: low, mid, and high. The low pointer tracks the boundary of elements less than the pivot, mid scans the current element, and high tracks the boundary of elements greater than the pivot. By swapping elements relative to these boundaries in a single pass, we achieve O(N) time complexity and O(1) auxiliary space.
Brute Force Approach
Create three auxiliary lists to separate elements that are less than, equal to, and greater than the pivot. Iterate through the input array and append each element to its respective list. Finally, copy the elements from the three lists back into the original array in order. This requires O(N) extra space.
Verified Code Solutions
function threeWayPivotPartitioning(nums, pivot) {
let low = 0;
let mid = 0;
let high = nums.length - 1;
while (mid <= high) {
if (nums[mid] < pivot) {
let temp = nums[low];
nums[low] = nums[mid];
nums[mid] = temp;
low++;
mid++;
} else if (nums[mid] === pivot) {
mid++;
} else {
let temp = nums[high];
nums[high] = nums[mid];
nums[mid] = temp;
high--;
}
}
return nums;
}#include <vector>
#include <algorithm>
#include <utility>
class Solution {
public:
void threeWayPivotPartitioning(std::vector<int>& nums, int pivot) {
int low = 0;
int mid = 0;
int high = static_cast<int>(nums.size()) - 1;
while (mid <= high) {
if (nums[mid] < pivot) {
std::swap(nums[low], nums[mid]);
low++;
mid++;
} else if (nums[mid] == pivot) {
mid++;
} else {
std::swap(nums[mid], nums[high]);
high--;
}
}
}
};class Solution {
public int[] threeWayPartition(int[] nums, int pivot) {
int left = 0, middle = 0, right = nums.length - 1;
while (middle <= right) {
if (nums[middle] < pivot) {
int temp = nums[left];
nums[left] = nums[middle];
nums[middle] = temp;
left++;
middle++;
} else if (nums[middle] > pivot) {
int temp = nums[right];
nums[right] = nums[middle];
nums[middle] = temp;
right--;
} else {
middle++;
}
}
return nums;
}
}def threeWayPartition(nums, pivot):
left, middle, right = 0, 0, len(nums) - 1
while middle <= right:
if nums[middle] < pivot:
nums[left], nums[middle] = nums[middle], nums[left]
left += 1
middle += 1
elif nums[middle] > pivot:
nums[middle], nums[right] = nums[right], nums[middle]
right -= 1
else:
middle += 1
return numsfunction threeWayPivotPartitioning(nums, pivot) {
let low = 0;
let mid = 0;
let high = nums.length - 1;
while (mid <= high) {
if (nums[mid] < pivot) {
let temp = nums[low];
nums[low] = nums[mid];
nums[mid] = temp;
low++;
mid++;
} else if (nums[mid] === pivot) {
mid++;
} else {
let temp = nums[high];
nums[high] = nums[mid];
nums[mid] = temp;
high--;
}
}
return nums;
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.