Partition Array According to Given Pivot - Solution & Explanation
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.
Approach 1: Three Lists Approach
This approach involves creating three separate lists to hold elements less than, equal to, and greater than the pivot. After populating these lists based on the original array, we concatenate them to produce the final result, thereby satisfying the problem conditions.
This solution first counts the number of elements that are less than, equal to, and greater than the pivot to determine the indices where these elements should be placed in the result array. Then, it iterates through the original array again, placing each element at the appropriate position in the result array.
Complexity
Time Complexity: O(n) where n is the number of elements in the array. Space Complexity: O(n) as we create a new array to store the ordered elements.
Approach 2: In-Place Partitioning Approach
This in-place approach leverages a two-pointer technique to rearrange elements directly within the original array. One pointer manages the position of elements less than the pivot, while the other handles elements greater than the pivot. This approach reduces space complexity compared to the three lists approach.
This C solution implements an in-place partition using two pointers to swap elements. Elements less than the pivot are moved to the start of the array, while elements greater than the pivot are moved to the end, thus maintaining minimal extra space usage.
Complexity
Time Complexity: O(n) due to iteration through the array. Space Complexity: O(1) as the rearrangement is performed in-place.
Approach 3: Simulation
We can traverse the array nums, sequentially finding all elements less than pivot, all elements equal to pivot, and all elements greater than pivot, then concatenate them in the order required by the problem.
Time complexity O(n), where n is the length of the array nums. Ignoring the space consumption of the answer array, the space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
Approach 4: Two pointers
Code
TypeScript
JavaScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Three Lists Approach | Time Complexity: O(n) where n is the number of elements in the array. Space Complexity: O(n) as we create a new array to store the ordered elements. |
| In-Place Partitioning Approach | Time Complexity: O(n) due to iteration through the array. Space Complexity: O(1) as the rearrangement is performed in-place. |
| Simulation | — |
| Two pointers | — |
Detailed 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 |
Video Solution
Partition Array According to Given Pivot - Leetcode 2161 - Python • NeetCodeIO • 10,417 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Partition Array According to Given Pivot easy or hard?
Partition Array According to Given Pivot Python/Java solution
How to solve Partition Array According to Given Pivot in O(n)?
What is the best approach for Partition Array According to Given Pivot?
Is Partition Array According to Given Pivot asked at Google/Amazon/Meta?
What data structure is used in Partition Array According to Given Pivot?
What is the time complexity of Partition Array According to Given Pivot?
Ready to solve this problem?
Practice Partition Array According to Given Pivot with our built-in code editor and test cases.
Practice on FleetCode