Sort Colors

Problem#

Sort an array of 0s, 1s, and 2s in-place, single pass, no comparison-sort library call.

Examples#

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

Constraints#

1 <= nums.length <= 300, values in {0, 1, 2}.

Hints#

Hint 1

Maintain three regions: [0..low) = 0, [low..mid) = 1, (high..end] = 2. Middle scans.

Hint 2

Don’t advance mid after swapping with high — you haven’t classified the new value yet.

Approach#

Counting sort — two passes, count then overwrite. O(n) time but two scans.

Dijkstra’s Dutch flag — three pointers in one pass, swapping into the right region.

Solution#

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int low = 0, mid = 0, high = nums.size() - 1;
        while (mid <= high) {
            if (nums[mid] == 0) {
                swap(nums[low++], nums[mid++]);
            } else if (nums[mid] == 1) {
                ++mid;
            } else {
                swap(nums[mid], nums[high--]); // do NOT advance mid
            }
        }
    }
};

func sortColors(nums []int) {
    low, mid, high := 0, 0, len(nums)-1
    for mid <= high {
        switch nums[mid] {
        case 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low++
            mid++
        case 1:
            mid++
        default:
            nums[mid], nums[high] = nums[high], nums[mid]
            high-- // do NOT advance mid
        }
    }
}

from typing import List

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        low, mid, high = 0, 0, len(nums) - 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], nums[high] = nums[high], nums[mid]
                high -= 1  # do NOT advance mid

function sortColors(nums) {
    let low = 0, mid = 0, high = nums.length - 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], nums[high]] = [nums[high], nums[mid]];
            high--; // do NOT advance mid
        }
    }
}

class Solution {
    public void sortColors(int[] nums) {
        int low = 0, mid = 0, high = nums.length - 1;
        while (mid <= high) {
            if (nums[mid] == 0) {
                int tmp = nums[low];
                nums[low] = nums[mid];
                nums[mid] = tmp;
                low++;
                mid++;
            } else if (nums[mid] == 1) {
                mid++;
            } else {
                int tmp = nums[mid];
                nums[mid] = nums[high];
                nums[high] = tmp;
                high--; // do NOT advance mid
            }
        }
    }
}

function sortColors(nums: number[]): void {
    let low = 0, mid = 0, high = nums.length - 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], nums[high]] = [nums[high], nums[mid]];
            high--; // do NOT advance mid
        }
    }
}

Editorial#

The asymmetry between the 0 and 2 cases is the subtle bit. When we swap a 0 into [0..low), we know the value coming from low was already classified as 1 (it sat in [low..mid)), so mid can advance. When we swap a 2 to the back, the value coming from high is unknown — it could be 0 or 1, so mid must re-inspect it. The loop terminates when mid > high because the 1-region has met the 2-region.

Complexity#

Time: O(n).
Space: O(1).

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#