Full lesson preview

Partition an array around a pivot

Rearrange an array in-place so elements less than pivot come first, then equal, then greater.

Python practice28 minSearching & SortingAdvancedLast updated March 25, 2026

Problem statement

Given an array nums and a pivot value pivot, rearrange nums in-place so that all elements less than pivot come first, followed by elements equal to pivot, followed by elements greater than pivot. Return the modified array. You must perform the rearrangement in O(n) time and O(1) additional space. The relative ordering within each partition is not required to be preserved.

Task

Implement an in-place three-way partition (Dutch National Flag) to group elements < pivot, == pivot, and > pivot in linear time and constant extra space.

Examples

Example with duplicates

Input

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

Output

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

One valid partitioning moves elements <10 to the front, equals in the middle, and >10 at the end. Order inside partitions may vary; this shows the result produced by a standard three-way partition algorithm.

Input format

A Python list nums and an integer/number pivot.

Output format

The input list nums after in-place partitioning (returned as a list).

Constraints

0 <= len(nums) <= 10^5. Aim for O(n) time and O(1) extra space. Relative order inside partitions need not be maintained.

Samples

Sample 1

Input

nums = [0, 1, 2, 0, 2, 1], pivot = 1

Output

[0, 0, 1, 1, 2, 2]

Elements <1 (zeros) are first, equals (ones) next, greater (twos) last.