Partition Array According to Given Pivot (LeetCode 2161)
You have a 0-indexed integer array nums and an integer pivot. Reorder nums so that:
- Everything smaller than
pivotsits before everything larger thanpivot. - Everything equal to
pivotsits between the smaller and larger groups. - Within the smaller group and within the larger group, the elements keep their original relative order.
Return nums once it's been reordered this way.
Worked Examples
nums = [9,12,5,10,14,3,10], pivot = 10[9,5,3,10,10,12,14]nums = [-3,4,3,2], pivot = 2[-3,2,4,3]⚖️Formal Constraints & Bounds
1 <= nums.length <= 105-106 <= nums[i] <= 106pivotequals to an element ofnums
Core Insight
Scanning forward places elements < pivot in original relative order at the front, scanning backward places elements > pivot in original relative order at the back, and the remaining middle slots are filled with pivot.
Real-World Scenario & Production Applications
Stable sorting passes, database query partition by boundary with stable tie-breaking, and audio buffer sorting.
Subproblems & Recurrence Decomposition3 Phases
Scan nums left to right, writing every element strictly less than pivot into a new result array in its original relative order, advancing a left write cursor.
res = [0] * len(nums)
left, right = 0, len(nums) - 1
for num in nums:
if num < pivot:
res[left] = num
left += 1Step-by-Step Execution Trace Table
| Pass | Pointer / Index | Action | res State |
|---|---|---|---|
| Left Pass | i = 0..n-1 | If nums[i] < pivot: res[left++] = nums[i] | Left prefix filled with [9, 5, 3] (left = 3) |
| Right Pass | i = n-1..0 | If nums[i] > pivot: res[right--] = nums[i] | Right suffix filled with [12, 14] (right = 4) |
| Middle Fill | left..right | While left <= right: res[left++] = pivot | Middle slots filled with [10, 10] |
| Final | — | All three partitions stably assembled | [9, 5, 3, 10, 10, 12, 14] |
| 1 | res = [0] * len(nums) |
| 2 | left = 0 |
| 3 | right = len(nums) - 1 |
| 4 | for i in range(len(nums)): |
| 5 | if nums[i] < pivot: |
| 6 | res[left] = nums[i] |
| 7 | left += 1 |
| 8 | if nums[len(nums)-1-i] > pivot: |
| 9 | res[right] = nums[len(nums)-1-i] |
| 10 | right -= 1 |
| 11 | while left <= right: |
| 12 | res[left] = pivot |
| 13 | left += 1 |
| 14 | return res |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Sort Colors (LC 75) could swap elements freely because all elements of the same color are identical. But in LC 2161, elements have distinct values and must maintain their original relative order (stability). Swapping across boundaries destroys stability!
⚖️ The Analogy: Two Pens Writing Inward
Imagine two scribes writing into a fresh output array res of size :
- The Left Scribe (
left = 0) writes from the start, moving forward. - The Right Scribe (
right = N - 1) writes from the end, moving backward.
You walk through the original array:
- Scanning forward from index
0toN-1: whenever you see an element< pivot, the Left Scribe writes it atres[left++]. Because you scan forward, smaller elements are naturally placed in their exact original relative order! - Scanning backward (
N-1-i): whenever you see an element> pivot, the Right Scribe writes it atres[right--]. Because you read backward and write backward, larger elements are also placed in their exact original relative order! - What is left between
leftandright? Exactly the slots reserved forpivot! Fill that gap withpivot.
Violating relative order stability: Using QuickSort-style in-place two-pointer partitioning scrambles the relative order of elements smaller or larger than pivot. LC 2161 strictly requires maintaining input relative order.
Allocating three separate passes unnecessarily: A clean two-pointer approach writes smaller elements from the left and larger elements from the right of the result buffer in a single pass.
Miscounting pivot frequency: Elements equal to pivot must appear between the smaller and larger partitions; forgetting to track the pivot count produces misaligned partitions.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Three-way partitioning + strict stability (relative order preservation) requirement.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: res[0..left-1] has all elements < pivot seen so far; res[right+1..n-1] has all elements > pivot in order.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Attempting in-place swaps like Dutch National Flag: breaks relative order (stability) of elements.
Using three separate lists and concatenating: incurs high memory allocation and reallocation overhead instead of a preallocated fixed-size result array.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I preallocate a result array of length N. In a single loop from 0 to N-1, I check nums[i] to place elements < pivot at left++, and simultaneously check nums[N-1-i] to place elements > pivot at right--. Finally, I fill remaining indices between left and right with pivot. Runs in
O(N)time andO(N)auxiliary space while guaranteeing stability."
Complexity & Mathematical Proof
O(N)
Look at the execution steps: One linear pass of length N inspects elements from both ends and writes into the result array. The second fill loop fills the middle pivot elements in at most N steps. Total time is linear.
O(N) Auxiliary
Look at memory allocations: A preallocated result array of size N is required to preserve stability. Pointers left and right use O(1) scalars.
T(N) = O(N)
Derivation Progression
Inspects nums[i] and nums[N - 1 - i], placing < pivot at left and > pivot at right.
Fills index range [left..right] with pivot value.
O(N) + O(N) = O(N)
Exact 2N operations, running in strict linear time.
Variable Definitions
Total number of elements in the array
Memory Architecture & Bounds
O(1) Iterative
O(N) Preallocated result array
O(N) Output array of size N
Boundary Best / Worst Cases
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: "elements less than pivot appear before elements equal to pivot", "relative order must be preserved". The requirement of stability makes in-place space Dutch National Flag unsuitable. An optimal linear approach uses a dual-pointer fill into an auxiliary result array.
. Time budget . Space budget auxiliary array for stable placement.
Scanning forward for would reverse their relative order if writing from right; must scan nums backwards when writing to right from end down to middle.
Partition Array According to Given Pivot (LeetCode 2161)
You have a 0-indexed integer array nums and an integer pivot. Reorder nums so that:
- Everything smaller than
pivotsits before everything larger thanpivot. - Everything equal to
pivotsits between the smaller and larger groups. - Within the smaller group and within the larger group, the elements keep their original relative order.
Return nums once it's been reordered this way.
Worked Examples
nums = [9,12,5,10,14,3,10], pivot = 10[9,5,3,10,10,12,14]nums = [-3,4,3,2], pivot = 2[-3,2,4,3]⚖️Formal Constraints & Bounds
1 <= nums.length <= 105-106 <= nums[i] <= 106pivotequals to an element ofnums
Core Insight
Scanning forward places elements < pivot in original relative order at the front, scanning backward places elements > pivot in original relative order at the back, and the remaining middle slots are filled with pivot.
Real-World Scenario & Production Applications
Stable sorting passes, database query partition by boundary with stable tie-breaking, and audio buffer sorting.
Subproblems & Recurrence Decomposition3 Phases
Scan nums left to right, writing every element strictly less than pivot into a new result array in its original relative order, advancing a left write cursor.
res = [0] * len(nums)
left, right = 0, len(nums) - 1
for num in nums:
if num < pivot:
res[left] = num
left += 1Step-by-Step Execution Trace Table
| Pass | Pointer / Index | Action | res State |
|---|---|---|---|
| Left Pass | i = 0..n-1 | If nums[i] < pivot: res[left++] = nums[i] | Left prefix filled with [9, 5, 3] (left = 3) |
| Right Pass | i = n-1..0 | If nums[i] > pivot: res[right--] = nums[i] | Right suffix filled with [12, 14] (right = 4) |
| Middle Fill | left..right | While left <= right: res[left++] = pivot | Middle slots filled with [10, 10] |
| Final | — | All three partitions stably assembled | [9, 5, 3, 10, 10, 12, 14] |
| 1 | res = [0] * len(nums) |
| 2 | left = 0 |
| 3 | right = len(nums) - 1 |
| 4 | for i in range(len(nums)): |
| 5 | if nums[i] < pivot: |
| 6 | res[left] = nums[i] |
| 7 | left += 1 |
| 8 | if nums[len(nums)-1-i] > pivot: |
| 9 | res[right] = nums[len(nums)-1-i] |
| 10 | right -= 1 |
| 11 | while left <= right: |
| 12 | res[left] = pivot |
| 13 | left += 1 |
| 14 | return res |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Sort Colors (LC 75) could swap elements freely because all elements of the same color are identical. But in LC 2161, elements have distinct values and must maintain their original relative order (stability). Swapping across boundaries destroys stability!
⚖️ The Analogy: Two Pens Writing Inward
Imagine two scribes writing into a fresh output array res of size :
- The Left Scribe (
left = 0) writes from the start, moving forward. - The Right Scribe (
right = N - 1) writes from the end, moving backward.
You walk through the original array:
- Scanning forward from index
0toN-1: whenever you see an element< pivot, the Left Scribe writes it atres[left++]. Because you scan forward, smaller elements are naturally placed in their exact original relative order! - Scanning backward (
N-1-i): whenever you see an element> pivot, the Right Scribe writes it atres[right--]. Because you read backward and write backward, larger elements are also placed in their exact original relative order! - What is left between
leftandright? Exactly the slots reserved forpivot! Fill that gap withpivot.
Violating relative order stability: Using QuickSort-style in-place two-pointer partitioning scrambles the relative order of elements smaller or larger than pivot. LC 2161 strictly requires maintaining input relative order.
Allocating three separate passes unnecessarily: A clean two-pointer approach writes smaller elements from the left and larger elements from the right of the result buffer in a single pass.
Miscounting pivot frequency: Elements equal to pivot must appear between the smaller and larger partitions; forgetting to track the pivot count produces misaligned partitions.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Three-way partitioning + strict stability (relative order preservation) requirement.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: res[0..left-1] has all elements < pivot seen so far; res[right+1..n-1] has all elements > pivot in order.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Attempting in-place swaps like Dutch National Flag: breaks relative order (stability) of elements.
Using three separate lists and concatenating: incurs high memory allocation and reallocation overhead instead of a preallocated fixed-size result array.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I preallocate a result array of length N. In a single loop from 0 to N-1, I check nums[i] to place elements < pivot at left++, and simultaneously check nums[N-1-i] to place elements > pivot at right--. Finally, I fill remaining indices between left and right with pivot. Runs in
O(N)time andO(N)auxiliary space while guaranteeing stability."
Complexity & Mathematical Proof
O(N)
Look at the execution steps: One linear pass of length N inspects elements from both ends and writes into the result array. The second fill loop fills the middle pivot elements in at most N steps. Total time is linear.
O(N) Auxiliary
Look at memory allocations: A preallocated result array of size N is required to preserve stability. Pointers left and right use O(1) scalars.
T(N) = O(N)
Derivation Progression
Inspects nums[i] and nums[N - 1 - i], placing < pivot at left and > pivot at right.
Fills index range [left..right] with pivot value.
O(N) + O(N) = O(N)
Exact 2N operations, running in strict linear time.
Variable Definitions
Total number of elements in the array
Memory Architecture & Bounds
O(1) Iterative
O(N) Preallocated result array
O(N) Output array of size N
Boundary Best / Worst Cases
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: "elements less than pivot appear before elements equal to pivot", "relative order must be preserved". The requirement of stability makes in-place space Dutch National Flag unsuitable. An optimal linear approach uses a dual-pointer fill into an auxiliary result array.
. Time budget . Space budget auxiliary array for stable placement.
Scanning forward for would reverse their relative order if writing from right; must scan nums backwards when writing to right from end down to middle.