Formatted question description: https://leetcode.ca/all/2161.html

# 2161. Partition Array According to Given Pivot (Medium)

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 than`pivot`

. - Every element equal to
`pivot`

appears**in between**the elements less than and greater than`pivot`

. - The
**relative order**of the elements less than`pivot`

and the elements greater than`pivot`

is maintained.- More formally, consider every
`p`

,_{i}`p`

where_{j}`p`

is the new position of the_{i}`i`

element and^{th}`p`

is the new position of the_{j}`j`

element. For elements less than^{th}`pivot`

, if`i < j`

and`nums[i] < pivot`

and`nums[j] < pivot`

, then`p`

. Similarly for elements greater than_{i}< p_{j}`pivot`

, if`i < j`

and`nums[i] > pivot`

and`nums[j] > pivot`

, then`p`

._{i}< p_{j}

- More formally, consider every

Return `nums`

* after the rearrangement.*

**Example 1:**

Input:nums = [9,12,5,10,14,3,10], pivot = 10Output:[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 = 2Output:[-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 of`nums`

.

**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/partition-array-according-to-given-pivot/
// 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;
}
};
```

## Discuss

https://leetcode.com/problems/partition-array-according-to-given-pivot/discuss/1746999

The above post was hidden for no reason…

https://leetcode.com/problems/partition-array-according-to-given-pivot/discuss/1747363