Partition Array According to Given Pivot - Video Solutions
Partition Array According to Given Pivot - Leetcode 2161 - Python
Partition Array According to Given Pivot - Video Solution
Watch 10 video solutions for Partition Array According to Given Pivot, a medium level problem involving Array, Two Pointers, Simulation. This walkthrough by NeetCodeIO has 10,417 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
You are given a 0-indexed integer array nums and an integer pivot. Rearrange nums such that the following conditions are satisfied:
- Every element less than
pivotappears before every element greater thanpivot. - Every element equal to
pivotappears in between the elements less than and greater thanpivot. - The relative order of the elements less than
pivotand the elements greater thanpivotis maintained.- More formally, consider every
pi,pjwherepiis the new position of theithelement andpjis the new position of thejthelement. For elements less thanpivot, ifi < jandnums[i] < pivotandnums[j] < pivot, thenpi < pj. Similarly for elements greater thanpivot, ifi < jandnums[i] > pivotandnums[j] > pivot, thenpi < pj.
- More formally, consider every
Return nums after the rearrangement.
Example 1:
Input: nums = [9,12,5,10,14,3,10], pivot = 10 Output: [9,5,3,10,10,12,14] Explanation: The elements 9, 5, and 3 are less than the pivot so they are on the left side of the array. The elements 12 and 14 are greater than the pivot so they are on the right side of the array. The relative ordering of the elements less than and greater than pivot is also maintained. [9, 5, 3] and [12, 14] are the respective orderings.
Example 2:
Input: nums = [-3,4,3,2], pivot = 2 Output: [-3,2,4,3] Explanation: The element -3 is less than the pivot so it is on the left side of the array. The elements 4 and 3 are greater than the pivot so they are on the right side of the array. The relative ordering of the elements less than and greater than pivot is also maintained. [-3] and [4, 3] are the respective orderings.
Constraints:
1 <= nums.length <= 105-106 <= nums[i] <= 106pivotequals to an element ofnums.
Approach Overview
Problem Overview: You are given an integer array and a pivot value. Reorder the array so that all elements smaller than the pivot appear first, followed by elements equal to the pivot, and then elements greater than the pivot. The relative order of elements in each group must remain the same.
Approach 1: Three Lists Approach (O(n) time, O(n) space)
The most straightforward solution is to simulate the partitioning process using three temporary arrays. Iterate through the input array once and place each element into one of three lists: less, equal, or greater. If the current number is smaller than the pivot, append it to less. If it equals the pivot, append it to equal. Otherwise append it to greater. After processing all elements, concatenate the three lists in order: less + equal + greater. Because elements are appended in the same order they appear, the relative ordering requirement is preserved automatically.
This approach relies on basic array traversal and is easy to reason about. The time complexity is O(n) since each element is processed once. The space complexity is O(n) due to the additional lists. When interviewers prioritize clarity and correctness over memory optimization, this is often the quickest implementation.
Approach 2: In-Place Partitioning (O(n) time, O(1) extra space)
If you want to reduce extra memory usage, you can simulate the same grouping with careful index management. Iterate through the array and build the result directly while tracking boundaries for elements smaller than and equal to the pivot. The idea is similar to the partition logic used in quicksort: maintain positions where the next less-than or equal-to element should be placed while scanning the array once.
Using a two pointers style approach, you move through the array and place elements into their correct region while preserving order. This requires careful shifting or staged placement but avoids allocating new arrays. The algorithm still runs in O(n) time because every element is examined once, while the additional memory stays at O(1).
This approach is more space-efficient and demonstrates a deeper understanding of array manipulation and partitioning strategies. The logic is slightly more complex than the three-list method, so it’s often used when memory constraints matter.
Recommended for interviews: Start with the Three Lists approach. It clearly shows you understand the problem and preserves ordering without tricky edge cases. After that, discuss the in-place optimization. Interviewers like seeing the simple simulation first, followed by a space-optimized partition strategy that still achieves O(n) time.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Three Lists Approach | O(n) | O(n) | Best for clarity and interviews where extra memory is acceptable |
| In-Place Partitioning | O(n) | O(1) | When memory usage matters or when demonstrating deeper array manipulation skills |