2161. Partition Array According to Given Pivot
Description
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
pivot
appears before every element greater thanpivot
. - Every element equal to
pivot
appears in between the elements less than and greater thanpivot
. - The relative order of the elements less than
pivot
and the elements greater thanpivot
is maintained.- More formally, consider every
pi
,pj
wherepi
is the new position of theith
element andpj
is the new position of thejth
element. For elements less thanpivot
, ifi < j
andnums[i] < pivot
andnums[j] < pivot
, thenpi < pj
. Similarly for elements greater thanpivot
, ifi < j
andnums[i] > pivot
andnums[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] <= 106
pivot
equals to an element ofnums
.
Solutions
Solution 1: Simulation
We can traverse the array $\textit{nums}$, sequentially finding all elements less than $\textit{pivot}$, all elements equal to $\textit{pivot}$, and all elements greater than $\textit{pivot}$, then concatenate them in the order required by the problem.
Time complexity $O(n)$, where $n$ is the length of the array $\textit{nums}$. Ignoring the space consumption of the answer array, the space complexity is $O(1)$.
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|