#2161

Medium

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Partition Array According to Given Pivot

Rearrange an array around a pivot while maintaining relative order using a two-pointer scanning approach efficiently.

Problem Statement

Given a 0-indexed integer array nums and an integer pivot, rearrange the array so that all elements less than the pivot come first, followed by elements equal to the pivot, and then elements greater than the pivot. The relative order within each group must be maintained.

Return the rearranged array after partitioning. For example, nums = [9,12,5,10,14,3,10] with pivot = 10 should return [9,5,3,10,10,12,14].

Examples

Example 1

Input: nums = [9,12,5,10,14,3,10], pivot = 10

Output: [9,5,3,10,10,12,14]

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]

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 Approach

Collect Elements in Three Buckets

Iterate through nums and append each element to one of three lists: less than pivot, equal to pivot, and greater than pivot. This guarantees the relative ordering is preserved within each group.

Merge the Buckets

After partitioning into three lists, concatenate them in order: less than pivot, equal to pivot, greater than pivot. This forms the final array satisfying the partition rules.

Maintain Linear Time and Space

This approach uses O(N) time by scanning the array once and O(N) additional space for the three lists. Avoid in-place swaps that could break relative ordering.

Complexity Analysis

Metric	Value
Time	O(N)
Space	O(N)

Time complexity is O(N) since each element is visited once. Space complexity is O(N) for storing elements in three separate lists before merging.

What Interviewers Usually Probe

Do you track elements less than, equal to, and greater than the pivot separately?
Can you maintain the original relative ordering of elements in a single pass?
Are you considering both time efficiency and space trade-offs for this two-pointer pattern?

Common Pitfalls or Variants

Common pitfalls

Trying to do in-place swaps without tracking order, which breaks relative ordering.
Confusing elements equal to the pivot with either smaller or larger group.
Using nested loops, increasing time complexity unnecessarily.

Follow-up variants

Partition using in-place stable partition algorithms to reduce space but maintain order.
Extend to multiple pivots, sorting by multiple thresholds with stable grouping.
Apply to linked lists instead of arrays to practice pointer manipulation.

FAQ

What is the simplest way to partition an array according to a given pivot?

Use three separate lists for elements less than, equal to, and greater than the pivot, then merge them to preserve order.

Does this solution maintain the original order of elements?

Yes, the two-pointer scanning with bucket collection ensures the relative order within each group is preserved.

Can this problem be solved in-place without extra space?

In-place solutions exist but require careful stable partitioning to avoid breaking relative ordering.

What are common mistakes when implementing pivot partitioning?

Breaking relative order, misplacing pivot elements, or using nested loops that increase time complexity.

How does the two-pointer scanning pattern apply here?

It efficiently separates elements into three categories in a single pass while tracking invariants, exactly matching this problem's requirement.

terminal

Solution

Solution 1: Simulation

We can traverse the array $\textit{nums}$, sequentially finding all elements less than $\textit{pivot}$, all elements equal to $\textit{pivot}$, and all elements greater than $\textit{pivot}$, then concatenate them in the order required by the problem.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def pivotArray(self, nums: List[int], pivot: int) -> List[int]:
        a, b, c = [], [], []
        for x in nums:
            if x < pivot:
                a.append(x)
            elif x == pivot:
                b.append(x)
            else:
                c.append(x)
        return a + b + c

Solution 2: Two pointers

#### TypeScript

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def pivotArray(self, nums: List[int], pivot: int) -> List[int]:
        a, b, c = [], [], []
        for x in nums:
            if x < pivot:
                a.append(x)
            elif x == pivot:
                b.append(x)
            else:
                c.append(x)
        return a + b + c

Continue Practicing

#2149 rearrange array elements by sign #2109 adding spaces to a string #2105 watering plants ii