Segmented Array Rearrangement — Problem Statement & Solution Guide

Two PointersMediumThree Pointers / Segregation

TimeO(n)

SpaceO(1)

Quick Answer & Algorithm Key Takeaway

Master coding challenges related to Two Pointers and solve the Segmented Array Rearrangement problem optimally.

TopicTwo Pointers

PatternThree Pointers / Segregation

TimeO(n)

SpaceO(1)

Problem Description

An integer array nums is provided, consisting exclusively of three distinct integer values: 0, 1, and 2. Your task is to reorder the array in-place so that elements are organized into contiguous segments by value: all occurrences of 0 must precede all occurrences of 1, which in turn must precede all occurrences of 2.

The reordering process must be executed directly within the input array without allocating extra array memory. Furthermore, the algorithm must process the array in a single traversal (one pass) using constant auxiliary space.

DSA Pattern Breakdown

"Segmented Array Rearrangement"

medium

WHY DOES IT MATTER?

The three‑segment partition is a foundational pattern for problems that require grouping by categories, such as segregating even/odd numbers or processing logs by severity, and mastering it builds intuition for in‑place data reorganization.

OPTIMIZATION CHALLENGE

The key insight is that you can decide the final position of an element as soon as you see it, eliminating the need for a second pass or auxiliary storage – a single sweep suffices when you maintain correct boundaries for each segment.

REAL-WORLD CONNECTION

Think of a conveyor belt in a factory where items of three colors are sorted into separate bins on the fly; the belt’s pointers act like low, mid, and high, directing each item to its correct bin without stopping the line.

During implementation, always increment the mid pointer only after handling the 0 and 1 cases; when you swap a 2 to the high end, do NOT increment mid because the new element at mid hasn't been examined yet.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(1)

Core Theory — Why This Approach?

The classic solution to this three‑value segregation problem is the Dutch National Flag algorithm, a two‑pointer technique that partitions an array into three contiguous regions in a single linear scan. A naive approach might sort the array with quicksort or mergesort, which costs O(n log n) time, or count the occurrences of each value and rewrite the array, which uses O(n) extra space – both undesirable for an in‑place interview constraint. By maintaining three pointers – low, mid, and high – we can ensure that everything left of low is 0, everything between low and mid is 1, and everything right of high is 2, achieving O(n) time and O(1) space while preserving in‑place requirements.

Interview Questions on This Problem

Q1How would you sort an array containing only 0,1,2 without using extra space?

Apply the Dutch National Flag algorithm: initialize low=0, mid=0, high=n-1 and iterate while mid<=high, swapping elements to move 0s to the front, 2s to the back, and leaving 1s in the middle.

Q2What is the time and space complexity of the two‑pointer solution for the three‑color sort?

The algorithm runs in O(n) time because each element is examined at most once, and it uses O(1) auxiliary space since only a few index variables are stored.

Q3Why is counting sort not the preferred solution for this problem in an interview setting?

Counting sort requires a second pass to write counts back into the array, which uses O(n) extra space for the count array; interviewers typically expect an in‑place linear solution that demonstrates pointer manipulation.

Examples

Example 1

Input

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

Output

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

Explanation: The original array contains two 0s, two 1s, and two 2s. Swapping elements in-place brings both 0s to indices [0, 1], both 1s to indices [2, 3], and both 2s to indices [4, 5].

Example 2

Input

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

Output

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

Explanation: Segregating the values moves the two 0s to the beginning (indices 0–1), places the three 1s in the center (indices 2–4), and pushes the two 2s to the tail end (indices 5–6).

Example 3

Input

nums = [2, 1, 2]

Output

[1, 2, 2]

Explanation: Since there are no 0s present, the single 1 is positioned at index 0, followed by the two 2s at indices 1 and 2.

Example 4

Input

nums = [0, 0, 1]

Output

[0, 0, 1]

Explanation: The array is already correctly partitioned into contiguous blocks of 0s and 1s, so no swaps change the sequence order.

Constraints

1 <= nums.length <= 10^5
nums[i] is either 0, 1, or 2 for all 0 <= i < nums.length
Auxiliary Space Complexity: O(1) - Must reorder in-place
Time Complexity Requirement: O(N) - Must process in a single pass

Optimal Approach & Strategy

Use the Dutch National Flag algorithm with three pointers to partition the array in a single linear scan, achieving O(n) time and O(1) space.

Brute Force Approach

Sort the array using any comparison sort like quicksort, which takes O(n log n) time, or count the number of 0s, 1s, and 2s then rewrite the array, which uses O(n) extra space.

Code Solutions

Language:

JavaScript Solution

Time: O(n)

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var sortColors = function(nums) {
    const n = nums.length;
    if (n <= 1) return;

    let low = 0;
    let mid = 0;
    let high = n - 1;

    while (mid <= high) {
        if (nums[mid] === 0) {
            [nums[low], nums[mid]] = [nums[mid], nums[low]];
            low++;
            mid++;
        } else if (nums[mid] === 1) {
            mid++;
        } else { // nums[mid] === 2
            [nums[mid], nums[high]] = [nums[high], nums[mid]];
            high--;
            // Do not increment mid because the swapped element from high is unprocessed
        }
    }
};

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int n = nums.size();
        if (n <= 1) return;

        int low = 0;
        int mid = 0;
        int high = n - 1;

        while (mid <= high) {
            if (nums[mid] == 0) {
                swap(nums[low], nums[mid]);
                low++;
                mid++;
            } else if (nums[mid] == 1) {
                mid++;
            } else { // nums[mid] == 2
                swap(nums[mid], nums[high]);
                high--;
                // Do not increment mid because the swapped element from high is unprocessed
            }
        }
    }
};

class Solution {
    public void sortColors(int[] nums) {
        int n = nums.length;
        if (n <= 1) return;

        int low = 0;
        int mid = 0;
        int high = n - 1;

        while (mid <= high) {
            if (nums[mid] == 0) {
                swap(nums, low, mid);
                low++;
                mid++;
            } else if (nums[mid] == 1) {
                mid++;
            } else { // nums[mid] == 2
                swap(nums, mid, high);
                high--;
                // Do not increment mid because the swapped element from high is unprocessed
            }
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        if n <= 1:
            return

        low = 0
        mid = 0
        high = n - 1

        while mid <= high:
            if nums[mid] == 0:
                nums[low], nums[mid] = nums[mid], nums[low]
                low += 1
                mid += 1
            elif nums[mid] == 1:
                mid += 1
            else:  # nums[mid] == 2
                nums[mid], nums[high] = nums[high], nums[mid]
                high -= 1
                # Do not increment mid because the swapped element from high is unprocessed

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var sortColors = function(nums) {
    const n = nums.length;
    if (n <= 1) return;

    let low = 0;
    let mid = 0;
    let high = n - 1;

    while (mid <= high) {
        if (nums[mid] === 0) {
            [nums[low], nums[mid]] = [nums[mid], nums[low]];
            low++;
            mid++;
        } else if (nums[mid] === 1) {
            mid++;
        } else { // nums[mid] === 2
            [nums[mid], nums[high]] = [nums[high], nums[mid]];
            high--;
            // Do not increment mid because the swapped element from high is unprocessed
        }
    }
};

Asked in Top Tech Interviews

PayPal

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.