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
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. Ifi < jand both elements are smaller (or larger) thanpivot, 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.
Solutions
This function rearranges an array of numbers so that all numbers smaller than a given "pivot" value move to the left, all numbers larger move to the right, and all numbers equal to the pivot stay in the middle—all while keeping their original relative order. It does this efficiently by first creating a new result array of the same size and filling it entirely with the pivot value. Then, it runs a single loop to look at the original array from both ends at the same time: numbers smaller than the pivot are placed into the new array starting from the far left (moving inward), while numbers larger than the pivot are placed starting from the far right (moving inward). Because the new array was already pre-filled with the pivot value, any untouched spaces in the middle naturally remain as pivots, resulting in a perfectly rearranged array.
/**
* @param {number[]} nums
* @param {number} pivot
* @return {number[]}
*/
var pivotArray = function(nums, pivot) {
const n = nums.length;
const res = Array(n).fill(pivot);
let lo = 0;
let hi = n - 1;
for (let i = 0; i < n; i++) {
if (nums[i] < pivot) {
res[lo] = nums[i];
lo++;
}
const j = n - 1 - i;
if (nums[j] > pivot) {
res[hi] = nums[j];
hi--;
}
}
return res;
};