Three-Way Array Partitioning — Problem Statement & Solution Guide

SortingMediumDutch National Flag

TimeO(n)

SpaceO(1)

Problem Description

Given an integer array nums and two integer boundaries low and high, partition the array in-place into three contiguous segments. The first segment must contain all elements strictly less than low. The second segment must contain all elements greater than or equal to low and less than or equal to high. The third segment must contain all elements strictly greater than high. The relative order of elements within each segment does not need to be preserved, but the segments must appear in the order: less-than-low, in-range, greater-than-high. If the input array is null or empty, return an empty array.

DSA Pattern Breakdown

"Three-Way Array Partitioning"

medium

WHY DOES IT MATTER?

This pattern is essential for optimizing sorting algorithms like QuickSort (3-way partitioning handles duplicates efficiently) and for in-place data reorganization in memory-constrained environments. It demonstrates mastery of pointer manipulation and invariant maintenance, which are critical for system design and low-level optimization.

OPTIMIZATION CHALLENGE

The key insight is maintaining three pointers (left, current, right) and using conditional swaps to ensure each element is visited at most once. This avoids the O(n log n) cost of sorting and the O(n) space cost of auxiliary arrays, achieving O(n) time and O(1) space.

REAL-WORLD CONNECTION

Analogous to traffic control in a multi-lane highway where vehicles are directed to left, middle, or right lanes based on speed limits. The 'low' and 'high' boundaries act as speed thresholds, and the partitioning ensures each lane contains only vehicles within its designated speed range, optimizing flow and reducing congestion.

During interviews, explicitly state the invariants you are maintaining (e.g., 'all elements before left are < low'). This shows rigorous thinking. Also, mention that this is a generalization of the Dutch National Flag problem, which signals deep algorithmic knowledge.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(1)

Core Theory — Why This Approach?

Three-way array partitioning is a specialized variant of the Dutch National Flag problem, extending the classic two-way partitioning (elements less than pivot vs. greater than pivot) to three distinct regions: less than low, between low and high (inclusive), and greater than high. The optimal paradigm utilizes a three-pointer technique where left tracks the boundary of the 'less than low' segment, right tracks the boundary of the 'greater than high' segment, and current scans the array. By maintaining the invariant that all elements before left are < low, all elements after right are > high, and all elements between left and right are unprocessed or in the middle segment, we achieve linear time complexity.

Interview Questions on This Problem

Q1How would you modify the three-way partitioning algorithm to handle duplicate values efficiently without using extra space?

The standard three-pointer approach naturally handles duplicates by keeping them in the middle segment if they fall within [low, high]. If duplicates exist outside the range, they are swapped to the correct outer segments. The key is ensuring the current pointer only advances when the element is in the correct middle segment, preventing infinite loops with duplicates.

Q2In a distributed system, how would you adapt this in-place partitioning logic to sort a large dataset across multiple nodes?

You would use a distributed partitioning strategy where each node performs a local three-way partition based on global boundaries. Then, nodes exchange data: nodes with 'low' segments send to the leftmost node, 'high' segments to the rightmost, and middle segments remain or are redistributed. This reduces network overhead by only moving data that needs to change partitions.

Q3What are the edge cases to consider when `low` equals `high` or when the array is already partitioned?

When low equals high, the middle segment contains only elements equal to that value. The algorithm still works, but the middle segment may be empty if no elements match. If the array is already partitioned, the pointers will traverse the array without swaps, resulting in O(n) time with minimal operations. Always test with empty arrays, single elements, and all elements in one segment.

Examples

Example 1

Input

nums = [12, 4, 7, 15, 2, 9, 11], low = 5, high = 10

Output

[2, 4, 7, 9, 11, 12, 15]

Explanation: Elements less than 5: [2, 4]. Elements between 5 and 10 inclusive: [7, 9]. Elements greater than 10: [11, 12, 15]. Concatenating these segments in order yields [2, 4, 7, 9, 11, 12, 15].

Example 2

Input

nums = [100, 200, 300, 50, 75], low = 150, high = 250

Output

[50, 75, 100, 200, 300]

Explanation: Elements less than 150: [50, 75, 100]. Elements between 150 and 250 inclusive: [200]. Elements greater than 250: [300]. The final partitioned array is [50, 75, 100, 200, 300].

Example 3

Input

nums = [5, 5, 5, 5], low = 5, high = 5

Output

[5, 5, 5, 5]

Explanation: All elements are equal to 5, which falls within the range [5, 5]. There are no elements less than 5 or greater than 5. The array remains unchanged as all elements belong to the middle segment.

Example 4

Input

nums = [1, 2, 3, 4, 5], low = 0, high = 100

Output

[1, 2, 3, 4, 5]

Explanation: All elements are between 0 and 100 inclusive. There are no elements less than 0 or greater than 100. The entire array constitutes the middle segment, so the output is identical to the input.

Constraints

0 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
-10^9 <= low <= high <= 10^9

Optimal Approach & Strategy

Use a three-pointer technique to partition the array in-place in a single pass. Maintain invariants for the three segments and swap elements to their correct positions as you scan, achieving O(n) time and O(1) space.

Brute Force Approach

Sort the entire array using a standard O(n log n) algorithm, then find the boundaries for the three segments. This is simple but inefficient for large inputs due to the logarithmic time complexity and potential extra space usage.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n)

/**
 * @param {number[]} nums
 * @param {number} low
 * @param {number} high
 * @return {void}
 */
var partition = function(nums, low, high) {
    let n = nums.length;
    let lt = 0, gt = n - 1, i = 0;
    while (i <= gt) {
        if (nums[i] < low) {
            [nums[lt], nums[i]] = [nums[i], nums[lt]];
            lt++;
            i++;
        } else if (nums[i] > high) {
            [nums[i], nums[gt]] = [nums[gt], nums[i]];
            gt--;
        } else {
            i++;
        }
    }
};

class Solution {
public:
    void partition(vector<int>& nums, int low, int high) {
        int n = nums.size();
        int lt = 0, gt = n - 1, i = 0;
        while (i <= gt) {
            if (nums[i] < low) {
                swap(nums[lt], nums[i]);
                lt++;
                i++;
            } else if (nums[i] > high) {
                swap(nums[i], nums[gt]);
                gt--;
            } else {
                i++;
            }
        }
    }
};

class Solution {
    public void partition(int[] nums, int low, int high) {
        int n = nums.length;
        int lt = 0, gt = n - 1, i = 0;
        while (i <= gt) {
            if (nums[i] < low) {
                int temp = nums[lt];
                nums[lt] = nums[i];
                nums[i] = temp;
                lt++;
                i++;
            } else if (nums[i] > high) {
                int temp = nums[i];
                nums[i] = nums[gt];
                nums[gt] = temp;
                gt--;
            } else {
                i++;
            }
        }
    }
}

class Solution:
    def partition(self, nums: List[int], low: int, high: int) -> None:
        n = len(nums)
        lt, gt, i = 0, n - 1, 0
        while i <= gt:
            if nums[i] < low:
                nums[lt], nums[i] = nums[i], nums[lt]
                lt += 1
                i += 1
            elif nums[i] > high:
                nums[i], nums[gt] = nums[gt], nums[i]
                gt -= 1
            else:
                i += 1

/**
 * @param {number[]} nums
 * @param {number} low
 * @param {number} high
 * @return {void}
 */
var partition = function(nums, low, high) {
    let n = nums.length;
    let lt = 0, gt = n - 1, i = 0;
    while (i <= gt) {
        if (nums[i] < low) {
            [nums[lt], nums[i]] = [nums[i], nums[lt]];
            lt++;
            i++;
        } else if (nums[i] > high) {
            [nums[i], nums[gt]] = [nums[gt], nums[i]];
            gt--;
        } else {
            i++;
        }
    }
};

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.

Three-Way Array Partitioning Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Input

Output

Constraints

More Sorting

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Three-Way Array Partitioning — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Solve in Interative Editor