Problem Description

You are given an integer array nums (0-indexed) and an integer value pivot. Your task is to rearrange the array according to these rules:

1. All elements less than pivot must appear before all elements greater than pivot
2. All elements equal to pivot must appear between the smaller and larger elements
3. The relative order within each group must be preserved

The key constraint is maintaining relative order - if two elements are both less than pivot (or both greater than pivot), and element at index i comes before element at index j in the original array, then in the rearranged array, the element from index i must still come before the element from index j.

For example, if nums = [9, 12, 5, 10, 14, 3, 10] and pivot = 10:

• Elements less than 10: [9, 5, 3] (keeping their original order)
• Elements equal to 10: [10, 10]
• Elements greater than 10: [12, 14] (keeping their original order)
• Result: [9, 5, 3, 10, 10, 12, 14]

The solution uses three separate lists to collect elements based on their relationship to the pivot value. It traverses the array once, categorizing each element into the appropriate list (a for less than pivot, b for equal to pivot, c for greater than pivot), then concatenates them in the required order. This approach naturally preserves the relative order within each group since elements are appended in the order they appear in the original array.

Intuition

The problem essentially asks us to perform a three-way partition while maintaining relative order. When we think about partitioning elements around a pivot value, we naturally have three groups: elements smaller than the pivot, elements equal to the pivot, and elements larger than the pivot.

The key insight is that we need to maintain the relative order within each group. This immediately suggests that we cannot use in-place swapping techniques (like those used in quicksort), as swapping would destroy the original ordering.

Instead, we can think of this as a stable sorting problem with only three "buckets". Since we need to preserve order and we're only dealing with three categories, the most straightforward approach is to:

1. Make a single pass through the array
2. Separate elements into their respective categories as we encounter them
3. Combine the categories in the required order

By using separate lists for each category and appending elements as we traverse the original array, we naturally preserve the relative order within each group. Elements are added to their respective lists in the same order they appear in the input, so when we concatenate a + b + c, we get the desired arrangement.

This approach trades space for simplicity - we use O(n) extra space but achieve O(n) time complexity with a very clean and easy-to-understand implementation. The beauty of this solution lies in its directness: rather than trying to cleverly rearrange elements in place, we simply collect and reassemble them in the required order.

Learn more about Two Pointers patterns.

Solution Approach

The implementation follows a straightforward three-pass collection strategy:

Step 1: Initialize Three Lists We create three empty lists to collect our elements:

• a = [] for elements less than pivot
• b = [] for elements equal to pivot
• c = [] for elements greater than pivot

Step 2: Single Pass Classification We traverse the array nums once, examining each element x:

for x in nums:
    if x < pivot:
        a.append(x)
    elif x == pivot:
        b.append(x)
    else:
        c.append(x)

During this traversal:

• If x < pivot, we append it to list a
• If x == pivot, we append it to list b
• If x > pivot, we append it to list c

Since we're appending elements in the order we encounter them, the relative order within each category is automatically preserved.

Step 3: Concatenate Results Finally, we concatenate the three lists in the required order:

return a + b + c

This places all elements less than pivot first, followed by elements equal to pivot, and finally elements greater than pivot.

Time and Space Complexity:

• Time Complexity: O(n) where n is the length of the array, as we make a single pass through the input
• Space Complexity: O(n) for storing the three auxiliary lists that together hold all n elements

The elegance of this solution lies in its simplicity - by separating the collection phase from the arrangement phase, we avoid complex index management and naturally maintain the required relative ordering.

Example Walkthrough

Let's walk through a small example with nums = [3, 7, 2, 7, 1, 9] and pivot = 7.

Step 1: Initialize Three Lists

a = []  (for elements < 7)
b = []  (for elements = 7)
c = []  (for elements > 7)

Step 2: Traverse and Classify Each Element

• Index 0: x = 3

  • 3 < 7, so append to a
  • a = [3], b = [], c = []

• Index 1: x = 7

  • 7 == 7, so append to b
  • a = [3], b = [7], c = []

• Index 2: x = 2

  • 2 < 7, so append to a
  • a = [3, 2], b = [7], c = []

• Index 3: x = 7

  • 7 == 7, so append to b
  • a = [3, 2], b = [7, 7], c = []

• Index 4: x = 1

  • 1 < 7, so append to a
  • a = [3, 2, 1], b = [7, 7], c = []

• Index 5: x = 9

  • 9 > 7, so append to c
  • a = [3, 2, 1], b = [7, 7], c = [9]

Step 3: Concatenate the Lists

result = a + b + c = [3, 2, 1] + [7, 7] + [9] = [3, 2, 1, 7, 7, 9]

Verification of Relative Order:

• Elements less than 7 in original: 3 (index 0), 2 (index 2), 1 (index 4)
• Elements less than 7 in result: [3, 2, 1] - same relative order preserved ✓
• Elements equal to 7 in original: 7 (index 1), 7 (index 3)
• Elements equal to 7 in result: [7, 7] - same relative order preserved ✓
• Elements greater than 7 in original: 9 (index 5)
• Elements greater than 7 in result: [9] - only one element ✓

The final result [3, 2, 1, 7, 7, 9] satisfies all requirements: elements less than pivot come first, followed by elements equal to pivot, then elements greater than pivot, with relative order maintained within each group.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the array nums. The algorithm iterates through the array exactly once in the for loop, performing constant-time operations (comparisons and append operations) for each element.

Space Complexity: O(n). While the reference answer mentions O(1) when ignoring the space for the answer array, the actual implementation uses three auxiliary lists a, b, and c that collectively store all n elements from the original array before concatenating them. These lists require O(n) additional space beyond the input. If we were to ignore the space needed for the output (which is a common convention when the output is required by the problem), we would still need O(n) space for the intermediate lists before creating the final result.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Attempting In-Place Modification While Preserving Order

A common pitfall is trying to optimize space complexity by attempting an in-place solution similar to the classic partition algorithm used in QuickSort. However, this approach fails because:

The Problem: Standard two-pointer partition techniques (like those in QuickSort) don't preserve relative order. When you swap elements, you inevitably change the relative ordering within groups.

Incorrect Approach Example:

def pivotArray(self, nums: List[int], pivot: int) -> List[int]:
    left, right = 0, len(nums) - 1
    while left < right:
        if nums[left] < pivot:
            left += 1
        elif nums[right] >= pivot:
            right -= 1
        else:
            nums[left], nums[right] = nums[right], nums[left]
    return nums

This fails because swapping disrupts the original relative order of elements.

The Solution: Accept that preserving relative order requires O(n) extra space. The three-list approach is actually optimal for this constraint.

2. Incorrect Handling of Elements Equal to Pivot

The Problem: Some might mistakenly group equal elements with either the "less than" or "greater than" categories:

# Incorrect: merging equal elements with greater elements
for num in nums:
    if num < pivot:
        less_than_pivot.append(num)
    else:  # This incorrectly groups equal elements with greater elements
        greater_than_pivot.append(num)

The Solution: Always use three distinct conditions with explicit equality check:

if num < pivot:
    less_than_pivot.append(num)
elif num == pivot:  # Explicit equality check
    equal_to_pivot.append(num)
else:
    greater_than_pivot.append(num)

3. Overcomplicating with Index Tracking

The Problem: Attempting to track original indices to maintain order, leading to unnecessary complexity:

# Overly complex approach
indexed_nums = [(num, i) for i, num in enumerate(nums)]
indexed_nums.sort(key=lambda x: (0 if x[0] < pivot else (1 if x[0] == pivot else 2), x[1]))
return [num for num, _ in indexed_nums]

The Solution: Trust that appending elements in order naturally preserves relative ordering. The simple three-list approach handles this elegantly without index tracking.