Partition Array According to Given Pivot

Problem Description

You are given a 0-indexed integer array nums and an integer pivot. Rearrange nums such that every element less than pivot appears before every element greater than pivot, with every element equal to pivot appearing in between. The relative order of elements less than and greater than pivot must be maintained.

Key Insights

• The elements less than the pivot must be on the left side of the array.
• The elements greater than the pivot must be on the right side of the array.
• The elements equal to the pivot must be placed between those less than and greater than the pivot.
• The relative order of elements within the less-than and greater-than groups must remain unchanged.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve the problem, we can use a three-step approach involving three lists (or arrays): one for elements less than the pivot, one for elements equal to the pivot, and one for elements greater than the pivot. After populating these lists, we can concatenate them to form the final array. This approach ensures the relative order of elements is preserved.

1. Initialize three empty lists: less, equal, and greater.
2. Iterate through the input array nums:
   • If an element is less than the pivot, append it to the less list.
   • If an element is equal to the pivot, append it to the equal list.
   • If an element is greater than the pivot, append it to the greater list.
3. Concatenate the less, equal, and greater lists to form the rearranged array.
4. Return the final array.

Code Solutions