You are given a 0-indexed integer array nums and an integer pivot. Rearrange nums such that the following conditions are satisfied:
pivot appears before every element greater than pivot.pivot appears in between the elements less than and greater than pivot.pivot and the elements greater than pivot is maintained.
pi, pj where pi is the new position of the ith element and pj is the new position of the jth element. For elements less than pivot, if i < j and nums[i] < pivot and nums[j] < pivot, then pi < pj. Similarly for elements greater than pivot, if i < j and nums[i] > pivot and nums[j] > pivot, then pi < pj.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] <= 106pivot equals to an element of nums.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.
C++
Java
Python
C#
JavaScript
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.
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) due to iteration through the array. Space Complexity: O(1) as the rearrangement is performed in-place.
| 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. |
Partition Array According to Given Pivot - Leetcode 2161 - Python • NeetCodeIO • 7,445 views views
Watch 9 more video solutions →Practice Partition Array According to Given Pivot with our built-in code editor and test cases.
Practice on FleetCode