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:

1. Every element less than pivot appears before every element greater than pivot.
2. Every element equal to pivot appears in between the elements less than and greater than pivot.
3. The relative order of the elements less than pivot and the elements greater than pivot is maintained.
   • More formally, consider every p``i```, pj``` where `pi is the new position of the `i``th` element and `p``j is the new position of the j``th element. If i < j and both elements are smaller (or larger) than pivot, then `pi < p``j```.

Return nums after the rearrangement.

For example:

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.

How would you implement this?

Rearranging Array Around a Pivot

Problem Description

Given a 0-indexed integer array nums and an integer pivot, rearrange nums such that:

1. Every element less than pivot appears before every element greater than pivot.
2. Every element equal to pivot appears in between the elements less than and greater than pivot.
3. The relative order of elements less than pivot and elements greater than pivot is maintained.

Return the rearranged array.

Naive Solution

A straightforward approach is to iterate through the array three times:

1. Collect elements less than the pivot.
2. Collect elements equal to the pivot.
3. Collect elements greater than the pivot.

Finally, concatenate the collected elements in the order: less, equal, greater.

def rearrange_array_naive(nums, pivot):
    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

Optimal Solution

A more efficient solution involves a single pass through the array using three separate lists to hold elements less than, equal to, and greater than the pivot. This maintains the relative order while rearranging the elements.

def rearrange_array(nums, pivot):
    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

Big(O) Runtime Analysis

The optimal solution iterates through the input array nums once. For each element, a comparison is made, and the element is appended to one of three lists. Appending to a list takes O(1) time on average.

Therefore, the overall time complexity is O(n), where n is the length of the nums array.

Big(O) Space Usage Analysis

Three lists, less, equal, and greater, are used to store elements less than, equal to, and greater than the pivot, respectively. In the worst-case scenario, all elements could be less than the pivot, equal to the pivot, or greater than the pivot. This means one of the lists could potentially store all n elements from the input array.

Therefore, the space complexity is O(n), where n is the length of the nums array.

Edge Cases

1. Empty Input Array:
   • If the input array is empty, the function should return an empty array.
2. Array with Only One Element:
   • If the array has only one element, it should be returned as is since no rearrangement is needed.
3. All Elements Equal to Pivot:
   • If all elements are equal to the pivot, the array should remain unchanged.
4. Pivot Not in Array:
   • According to the problem constraints, the pivot is guaranteed to be an element of nums, so we don't need to explicitly handle this edge case.

These edge cases are handled correctly by the optimal solution as the lists less, equal, and greater would be constructed accordingly and concatenated correctly.