Three-Way Pivot Partitioning — Problem Statement & Solution Guide

ArraysMediumDutch National Flag

TimeO(n)

SpaceO(1)

Quick Answer & Algorithm Key Takeaway

Three-way partitioning

TopicArrays

PatternDutch National Flag

TimeO(n)

SpaceO(1)

Problem Description

Given an array of integers nums and an integer pivot, rearrange the elements of nums in-place such that all elements less than pivot appear first, followed by all elements equal to pivot, and finally all elements greater than pivot appear last. The relative order of the partitioned elements should be preserved.

DSA Pattern Breakdown

"Three-Way Pivot Partitioning"

medium

WHY DOES IT MATTER?

Stable partitioning is crucial when the relative order of elements matters, such as in sorting pipelines or when subsequent operations rely on original ordering. It also ensures deterministic behavior across runs, which is important for debugging and reproducibility.

OPTIMIZATION CHALLENGE

The key insight is to avoid copying or extra arrays; instead, use two pointers and in‑place shifting to maintain stability, reducing both time to O(n) and space to O(1).

REAL-WORLD CONNECTION

Think of a warehouse sorting system that must keep items of the same type in the same sequence for inventory tracking. The algorithm acts like a conveyor belt that groups items by category while preserving their arrival order.

When explaining the algorithm, emphasize the invariant that the <pivot region is always sorted and stable, and that each element is moved at most once, which guarantees linear time.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(1)

Core Theory — Why This Approach?

The three‑way pivot partition is a stable variant of the Dutch National Flag problem. It requires a single left‑to‑right scan while maintaining three regions: <pivot, =pivot, >pivot. A naive approach would copy elements into three temporary lists or perform repeated swaps that break stability, leading to O(n^2) in the worst case or extra O(n) space. The optimal paradigm uses two pointers: one to track the end of the <pivot region and another to track the start of the >pivot region, moving elements in place and preserving order by shifting elements when necessary. This yields O(n) time and O(1) auxiliary space while keeping the relative order of equal elements intact.

Interview Questions on This Problem

Q1How would you modify the classic Dutch National Flag algorithm to preserve the relative order of elements equal to the pivot?

By using a stable in‑place approach: maintain a pointer for the end of the less‑than region and a pointer for the start of the greater‑than region. When encountering an element equal to the pivot, shift all elements between the less‑than pointer and the current index one position to the right, then insert the pivot element. This preserves order while still operating in O(n) time.

Q2What is the time and space complexity of the optimal solution for Three‑Way Pivot Partitioning, and why is it considered efficient for large inputs?

The optimal solution runs in O(n) time and O(1) extra space. It processes each element once and performs only constant‑time operations per element, making it linear and memory‑efficient, which is essential for large arrays where copying or additional storage would be costly.

Q3During an interview, a candidate proposes using three separate lists and then concatenating them. Why might this be discouraged in a production environment?

Using three lists requires O(n) additional memory and two passes over the data, which can be problematic for large datasets or memory‑constrained systems. In production, in‑place algorithms with constant space are preferred to reduce memory footprint and improve cache locality.

Examples

Example 1

Input

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

Output

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

Explanation: Step-by-step: With input [3, 5, 5, 5, 9, 10, 12, 14], we first partition the array into three parts: elements less than 5, elements equal to 5, and elements greater than 5. The relative order of the partitioned elements is preserved by iterating through the array only once.

Example 2

Input

[1, 2, 4, 4, 7, 8]

Output

[1, 2, 4, 4, 7, 8]

Explanation: Step-by-step: With input [1, 2, 4, 4, 7, 8], we first partition the array into three parts: elements less than 4, elements equal to 4, and elements greater than 4. The relative order of the partitioned elements is preserved by iterating through the array only once.

Constraints

1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
-10^9 <= pivot <= 10^9

Optimal Approach & Strategy

Traverse the array once, using two pointers to move elements into place while shifting elements to preserve order. This achieves O(n) time and O(1) auxiliary space.

Brute Force Approach

Create three temporary arrays for elements less than, equal to, and greater than the pivot, then concatenate them back into the original array. This uses O(n) extra space and two passes over the data.

Code Solutions

Language:

JavaScript Solution

Time: O(n)

function threeWayPivotPartitioning(nums, pivot) {
  let low = 0;
  let mid = 0;
  let high = nums.length - 1;
  while (mid <= high) {
    if (nums[mid] < pivot) {
      let temp = nums[low];
      nums[low] = nums[mid];
      nums[mid] = temp;
      low++;
      mid++;
    } else if (nums[mid] === pivot) {
      mid++;
    } else {
      let temp = nums[high];
      nums[high] = nums[mid];
      nums[mid] = temp;
      high--;
    }
  }
  return nums;
}

#include <vector>
#include <algorithm>
#include <utility>

class Solution {
public:
    void threeWayPivotPartitioning(std::vector<int>& nums, int pivot) {
        int low = 0;
        int mid = 0;
        int high = static_cast<int>(nums.size()) - 1;
        while (mid <= high) {
            if (nums[mid] < pivot) {
                std::swap(nums[low], nums[mid]);
                low++;
                mid++;
            } else if (nums[mid] == pivot) {
                mid++;
            } else {
                std::swap(nums[mid], nums[high]);
                high--;
            }
        }
    }
};

class Solution {
    public int[] threeWayPartition(int[] nums, int pivot) {
        int left = 0, middle = 0, right = nums.length - 1;
        while (middle <= right) {
            if (nums[middle] < pivot) {
                int temp = nums[left];
                nums[left] = nums[middle];
                nums[middle] = temp;
                left++;
                middle++;
            } else if (nums[middle] > pivot) {
                int temp = nums[right];
                nums[right] = nums[middle];
                nums[middle] = temp;
                right--;
            } else {
                middle++;
            }
        }
        return nums;
    }
}

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

function threeWayPivotPartitioning(nums, pivot) {
  let low = 0;
  let mid = 0;
  let high = nums.length - 1;
  while (mid <= high) {
    if (nums[mid] < pivot) {
      let temp = nums[low];
      nums[low] = nums[mid];
      nums[mid] = temp;
      low++;
      mid++;
    } else if (nums[mid] === pivot) {
      mid++;
    } else {
      let temp = nums[high];
      nums[high] = nums[mid];
      nums[mid] = temp;
      high--;
    }
  }
  return nums;
}

Asked in Top Tech Interviews

PhonePe

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.