Solve LeetCode 75: Dutch National Flag Problem with Java, C++, C, and Python

Problem Description

Given an array nums of n elements containing only 0, 1, and 2 (representing red, white, and blue), sort the array in‑place so that all 0s come first, followed by all 1s, then all 2s. The solution must not use any library sort function.

Constraints

n == nums.length

1 ≤ n ≤ 300

nums[i] is 0, 1, or 2

Analysis

This is the classic Dutch National Flag problem. A three‑pointer approach is used: left points to the boundary of the next 0 position, right points to the boundary of the next 2 position, and index scans the array.

If nums[index] == 0, swap it with nums[left] and increment both left and index. If nums[index] == 2, swap it with nums[right] and decrement right (do not increment index because the swapped value needs re‑evaluation). If nums[index] == 1, simply move index forward.

Solution Code

Java

public void sortColors(int[] nums) {
    int left = 0; // right boundary of 0s
    int right = nums.length - 1; // left boundary of 2s
    int index = 0; // current element
    while (index <= right) {
        if (nums[index] == 0) {
            // move 0 to the front
            swap(nums, left++, index++);
        } else if (nums[index] == 1) {
            // 1 stays in place
            index++;
        } else if (nums[index] == 2) {
            // move 2 to the back
            swap(nums, right--, index);
        }
    }
}

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

C++

void sortColors(vector<int>& nums) {
    int left = 0; // right boundary of 0s
    int right = nums.size() - 1; // left boundary of 2s
    int index = 0; // current element
    while (index <= right) {
        if (nums[index] == 0) {
            swap(nums[left++], nums[index++]);
        } else if (nums[index] == 1) {
            index++;
        } else if (nums[index] == 2) {
            swap(nums[right--], nums[index]);
        }
    }
}

C

void swap(int *a, int *b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

void sortColors(int *nums, int numsSize) {
    int left = 0; // right boundary of 0s
    int right = numsSize - 1; // left boundary of 2s
    int index = 0; // current element
    while (index <= right) {
        if (nums[index] == 0) {
            swap(&nums[left++], &nums[index++]);
        } else if (nums[index] == 1) {
            index++;
        } else if (nums[index] == 2) {
            swap(&nums[right--], &nums[index]);
        }
    }
}

Python

def sortColors(self, nums: List[int]) -> None:
    # left is the right boundary of 0s, right is the left boundary of 2s, index scans the array
    left, right, index = 0, len(nums) - 1, 0
    while index <= right:
        if nums[index] == 0:
            nums[left], nums[index] = nums[index], nums[left]
            left += 1
            index += 1
        elif nums[index] == 1:
            index += 1
        elif nums[index] == 2:
            nums[right], nums[index] = nums[index], nums[right]
            right -= 1