Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2161.html
2161. Partition Array According to Given Pivot (Medium)
You are given a 0indexed 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
p_{i}
,p_{j}
wherep_{i}
is the new position of thei^{th}
element andp_{j}
is the new position of thej^{th}
element. For elements less thanpivot
, ifi < j
andnums[i] < pivot
andnums[j] < pivot
, thenp_{i} < p_{j}
. Similarly for elements greater thanpivot
, ifi < j
andnums[i] > pivot
andnums[j] > pivot
, thenp_{i} < p_{j}
.
 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 <= 10^{5}
10^{6} <= nums[i] <= 10^{6}
pivot
equals to an element ofnums
.
Similar Questions:
Solution 1. Two Pointers
This problem looks similar to the partitioning process in Quick Sort, but since the efficient partition algorithms (Lomuto’s and Hoare’s) are not stable, you can’t use it here.

// OJ: https://leetcode.com/problems/partitionarrayaccordingtogivenpivot/ // Time: O(N) // Space: O(N) class Solution { public: vector<int> pivotArray(vector<int>& A, int pivot) { vector<int> gt; // numbers greater than pivot int j = 0, cnt = 0; // `j` is the write pointer. `cnt` is the count of numbers equal to pivot for (int i = 0; i < A.size(); ++i) { if (A[i] < pivot) A[j++] = A[i]; else if (A[i] == pivot) ++cnt; else gt.push_back(A[i]); } while (cnt) A[j++] = pivot; for (int i = 0; i < gt.size(); ++i) A[j++] = gt[i]; return A; } };

class Solution: def pivotArray(self, nums: List[int], pivot: int) > List[int]: a, b, c = [], [], [] for x in nums: if x < pivot: a.append(x) elif x == pivot: b.append(x) else: c.append(x) return a + b + c ############ # 2161. Partition Array According to Given Pivot # https://leetcode.com/problems/partitionarrayaccordingtogivenpivot/ class Solution: def pivotArray(self, nums: List[int], pivot: int) > List[int]: left = [] right = [] count = 0 for x in nums: if x < pivot: left.append(x) elif x > pivot: right.append(x) else: count += 1 return left + [pivot] * count + right

class Solution { public int[] pivotArray(int[] nums, int pivot) { int n = nums.length; int[] ans = new int[n]; int k = 0; for (int x : nums) { if (x < pivot) { ans[k++] = x; } } for (int x : nums) { if (x == pivot) { ans[k++] = x; } } for (int x : nums) { if (x > pivot) { ans[k++] = x; } } return ans; } }

func pivotArray(nums []int, pivot int) []int { var ans []int for _, x := range nums { if x < pivot { ans = append(ans, x) } } for _, x := range nums { if x == pivot { ans = append(ans, x) } } for _, x := range nums { if x > pivot { ans = append(ans, x) } } return ans }
Discuss
https://leetcode.com/problems/partitionarrayaccordingtogivenpivot/discuss/1746999
The above post was hidden for no reason…
https://leetcode.com/problems/partitionarrayaccordingtogivenpivot/discuss/1747363