Partition Array According to Given Pivot
Problem
Given an integer array nums and an integer pivot, rearrange nums such that all elements less than pivot come first, followed by elements equal to pivot, then elements greater than pivot, preserving the relative order within each group, and return the rearranged array.
- 1 ≤ nums.length ≤ 10⁵
- −10⁶ ≤ nums[i], pivot ≤ 10⁶
Example
nums = [9,12,5,10,14,3,10], pivot = 10[9,5,3,10,10,12,14]The algorithm partitions the array into three groups: less than 10, equal to 10, and greater than 10. The relative order within each group is preserved. The less-than group is [9,5,3], the equal group is [10,10], and the greater group is [12,14]. Concatenating these groups yields the output.
Approach
Straightforward Solution
A naive approach might attempt in-place partitioning similar to quicksort's partition, but maintaining relative order in-place is complex and inefficient, often requiring O(n^2) time or additional data structures.
Core Observation
The problem requires a stable partition of the array into three segments based on comparison with the pivot, preserving the original order within each segment.
Path to Optimal
Recognizing the need for stability and linear time, the problem naturally suggests collecting elements into separate lists for each category (less, equal, greater) during a single pass, then concatenating them. This approach is simple, efficient, and preserves order.
Optimal Approach
PreviewIterate through nums once, appending each element to one of three lists depending on its relation to pivot. Finally, concatenate these lists to produce the result…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n)
The algorithm makes a single pass through the input array, performing O(1) operations per element, and concatenates three lists in O(n) time.
Space
O(n)
Three auxiliary lists are used to store all elements, collectively requiring O(n) space proportional to the input size. This space is necessary to preserve relative order while partitioning.
Pattern Spotlight
Simulation (Stable Partitioning)
When a problem requires rearranging elements by categories while preserving relative order, simulate the partition by collecting elements into separate buckets in a single pass, then concatenate to maintain stability and linear time.
Solution
| 1 | class Solution: |
| 2 | def pivotArray(self, nums: list[int], pivot: int) -> list[int]: |
| 3 | less = [] |
| 4 | equal = [] |
| 5 | greater = [] |
| 6 | |
| 7 | for num in nums: |
| 8 | if num < pivot: |
| 9 | less.append(num) |
| 10 | elif num == pivot: |
| 11 | equal.append(num) |
| 12 | else: |
| 13 | greater.append(num) |
| 14 | |
| 15 | return less + equal + greater |
Step-by-Step Solution
Collect Elements into Three Ordered Buckets Based on Pivot Comparison
| 3 | less = [] |
| 4 | equal = [] |
| 5 | greater = [] |
| 7 | for num in nums: |
| 8 | if num < pivot: |
| 9 | less.append(num) |
| 10 | elif num == pivot: |
| 11 | equal.append(num) |
| 12 | else: |
| 13 | greater.append(num) |
Objective
To iterate through the input array once and distribute elements into three separate lists representing less than, equal to, and greater than the pivot.
Key Insight
By categorizing elements during a single pass, the algorithm preserves the relative order within each category naturally, avoiding complex in-place rearrangements. This simulation approach leverages the simplicity of list appends to maintain order and achieve linear time complexity.
Interview Quick-Check
Core Logic
The single pass iteration classifies each element into one of three buckets, preserving order by appending elements in the order they appear.
State & Boundaries
The iteration covers all elements exactly once, ensuring no element is missed or duplicated.
Common Pitfalls & Bugs
A common mistake is to attempt in-place partitioning without preserving order, which violates the problem's stability requirement.
Complexity
Appending to lists is O(1) amortized, so the overall iteration remains O(n).
Concatenate Buckets to Form the Final Stable Partitioned Array
To combine the three lists in order to produce the final array with elements less than pivot first, then equal, then greater.
1 more step with full analysis available on Pro.
Line Analysis
This solution has 4 Critical lines interviewers watch for.
return less + equal + greaterReturn the concatenation of less, equal, and greater lists as the final partitioned array.
Concatenating these lists in order produces the required stable partition, combining all elements while preserving their relative order within each group.
less.append(num)Append the current element to the 'less' list.
Appending maintains the original relative order of elements less than the pivot, which is critical for stability.
equal.append(num)Append the current element to the 'equal' list.
Appending here preserves the relative order of elements equal to the pivot, maintaining stability.
Full line-by-line criticality + rationale for all 11 lines available on Pro.
Test Your Understanding
Why is it necessary to use separate lists instead of partitioning in-place to preserve relative order?
See the answer with Pro.
Related Problems
Simulation pattern
Don't just read it. Drill it.
Reconstruct Partition Array According to Given Pivot from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Partition Array According to Given Pivot drill