Sort Colors (Dutch Flag)

Problem

An array contains only 0s, 1s, and 2s. Sort them in place in one pass without using a sort library. (The "Dutch national flag" problem.)

Constraints

• 1 ≤ nums.length ≤ 300
• nums[i] ∈ {0,1,2}

Approach — Two Pointers

This is a Two Pointers problem. The idea: walk two indices through the data together (or toward each other), turning an O(n²) pair search into one linear pass. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) time, O(1) extra space.

Solution code

Python

class Solution:
    def sortColors(self, nums):
        lo, i, hi = 0, 0, len(nums) - 1
        while i <= hi:
            if nums[i] == 0:
                nums[lo], nums[i] = nums[i], nums[lo]; lo += 1; i += 1
            elif nums[i] == 2:
                nums[hi], nums[i] = nums[i], nums[hi]; hi -= 1
            else:
                i += 1
        return nums

Java

class Solution {
    public void sortColors(int[] nums) {
        int lo = 0, mid = 0, hi = nums.length - 1;
        while (mid <= hi) {
            if (nums[mid] == 0)      swap(nums, lo++, mid++);
            else if (nums[mid] == 2) swap(nums, mid, hi--);
            else                     mid++;
        }
    }
    private void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.