{x}
blog image

Partition Array According to Given Pivot

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 pi, pj where pi is the new position of the ith element and pj is the new position of the jth element. If i < j and both elements are smaller (or larger) than 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] <= 106
  • pivot equals to an element of nums.

Solution Explanation: Partition Array According to Given Pivot

This problem requires rearranging an array nums based on a given pivot value, ensuring that elements less than the pivot come before those equal to the pivot, which in turn come before elements greater than the pivot. The relative order within each group (less than, equal to, greater than) must be preserved.

Approach: Three-Pass Simulation

The most straightforward solution involves three passes through the array:

  1. Collect less than pivot: Iterate through nums and collect all elements less than pivot into a separate list (e.g., less).

  2. Collect equal to pivot: Iterate through nums and collect all elements equal to pivot into a separate list (e.g., equal).

  3. Collect greater than pivot: Iterate through nums and collect all elements greater than pivot into a separate list (e.g., greater).

  4. Concatenate: Concatenate the three lists: less + equal + greater. This resulting list satisfies all the problem's conditions.

Time and Space Complexity

  • Time Complexity: O(n), where n is the length of nums. We perform three linear passes through the array.
  • Space Complexity: O(n) in the worst case. In the worst-case scenario, all elements are either less than or greater than the pivot, resulting in two large lists in addition to the original array. If we disregard the output array's space, then the space complexity reduces to O(1) because we only use a constant amount of extra space (a few lists of potentially limited size).

Code Implementation (Python)

class Solution:
    def pivotArray(self, nums: List[int], pivot: int) -> List[int]:
        less = []
        equal = []
        greater = []
        for num in nums:
            if num < pivot:
                less.append(num)
            elif num == pivot:
                equal.append(num)
            else:
                greater.append(num)
        return less + equal + greater

Code Implementation (Java)

class Solution {
    public int[] pivotArray(int[] nums, int pivot) {
        List<Integer> less = new ArrayList<>();
        List<Integer> equal = new ArrayList<>();
        List<Integer> greater = new ArrayList<>();
 
        for (int num : nums) {
            if (num < pivot) {
                less.add(num);
            } else if (num == pivot) {
                equal.add(num);
            } else {
                greater.add(num);
            }
        }
 
        List<Integer> result = new ArrayList<>();
        result.addAll(less);
        result.addAll(equal);
        result.addAll(greater);
 
        int[] arr = new int[result.size()];
        for (int i = 0; i < result.size(); i++) {
            arr[i] = result.get(i);
        }
        return arr;
    }
}

The implementations in other languages (C++, Go, TypeScript) follow a similar structure, adapting the data structures and syntax to each language's specifics, while maintaining the three-pass strategy. The core logic remains consistent across all languages.