Problem

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. For elements less than pivot, if i < j and nums[i] < pivot and nums[j] < pivot, then pi < pj. Similarly for elements greater than pivot, if i < j and nums[i] > pivot and nums[j] > pivot, then pi < pj.

Return nums after the rearrangement.

Examples

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

Method 1 - Creating 3 lists and update the arrays

To rearrange the elements of the array based on the given pivot, we need to maintain three separate lists:

  • One for elements less than the pivot.
  • One for elements equal to the pivot.
  • One for elements greater than the pivot.

By iterating through the array and appending each element to the appropriate list, we effectively partition the array into the required format while maintaining relative order. Finally, we concatenate these three lists to obtain the rearranged array.

Approach

  1. Initialize Three Lists:
    • One for elements less than pivot.
    • One for elements equal to pivot.
    • One for elements greater than pivot.
  2. Iterate Through the Original List:
    • Append each element to the corresponding list based on its comparison with pivot.
  3. Concatenate the Three Lists:
    • Combine all three lists to get the partitioned list.
  4. Return the Partitioned List:
    • Return the concatenated list as the result.

Code

Java
public 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);
            }
        }

        int[] ans = new int[nums.length];
        int index = 0;

        for (int num : less) {
            ans[index++] = num;
        }
        for (int num : equal) {
            ans[index++] = num;
        }
        for (int num : greater) {
            ans[index++] = num;
        }

        return ans;
    }
}
Python
class Solution:
    def pivotArray(self, nums: List[int], pivot: int) -> List[int]:
        less_than_pivot: List[int] = []
        equal_to_pivot: List[int] = []
        greater_than_pivot: List[int] = []
        
        for num in nums:
            if num < pivot:
                less_than_pivot.append(num)
            elif num == pivot:
                equal_to_pivot.append(num)
            else:
                greater_than_pivot.append(num)
        
        return less_than_pivot + equal_to_pivot + greater_than_pivot

Complexity

  • ⏰ Time complexity: O(n), where n is the number of elements in nums, as we are iterating through the list once.
  • 🧺 Space complexity: O(n), where n is the number of elements in nums, for storing elements in the three separate lists.