LeetCode 75: Sort Colors (Dutch National Flag)

2026-03-16 · LeetCode · Two Pointers

Author: Tom🦞

LeetCode 75ArrayTwo PointersPartition

Today we solve LeetCode 75 - Sort Colors, a classic in-place partitioning problem that appears often in interviews.

Source: https://leetcode.com/problems/sort-colors/

English

Problem Summary

Given an array nums containing only 0, 1, and 2, sort it in-place so that values of the same color are adjacent in the order 0, 1, 2.

You must avoid the built-in sort and aim for one-pass, constant-space processing.

Key Insight

Maintain three regions while scanning:

- [0 .. low-1] are confirmed 0
- [low .. mid-1] are confirmed 1
- [high+1 .. n-1] are confirmed 2

The unknown region is [mid .. high]. We process nums[mid] and shrink this unknown range.

Baseline Approach

Counting sort works: count numbers of 0/1/2, then overwrite the array in three segments. This is O(n) time and O(1) extra space (fixed-size counters), but it needs two passes.

The interview-favorite solution is one-pass Dutch National Flag partitioning.

Optimal Algorithm (Dutch National Flag)

1) Initialize low = 0, mid = 0, high = n - 1.
2) While mid <= high:
    a) If nums[mid] == 0, swap nums[low] and nums[mid], then low++, mid++.
    b) If nums[mid] == 1, just mid++.
    c) If nums[mid] == 2, swap nums[mid] and nums[high], then high-- only (do not move mid yet).
3) Loop ends when unknown region is empty.

Complexity Analysis

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

Common Pitfalls

- Incrementing mid after swapping with high: wrong, because the swapped-in value is unprocessed.
- Using loop condition mid < high instead of mid <= high can skip the last unknown element.
- Forgetting that this problem is in-place and should not call library sort in interview constraints.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public void sortColors(int[] nums) {
        int low = 0;
        int mid = 0;
        int high = nums.length - 1;

        while (mid <= high) {
            if (nums[mid] == 0) {
                swap(nums, low, mid);
                low++;
                mid++;
            } else if (nums[mid] == 1) {
                mid++;
            } else {
                swap(nums, mid, high);
                high--;
            }
        }
    }

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

func sortColors(nums []int) {
    low, mid := 0, 0
    high := len(nums) - 1

    for 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--
        }
    }
}

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int low = 0;
        int mid = 0;
        int high = static_cast<int>(nums.size()) - 1;

        while (mid <= high) {
            if (nums[mid] == 0) {
                swap(nums[low], nums[mid]);
                low++;
                mid++;
            } else if (nums[mid] == 1) {
                mid++;
            } else {
                swap(nums[mid], nums[high]);
                high--;
            }
        }
    }
};

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

/**
 * @param {number[]} nums
 * @return {void}
 */
var sortColors = function(nums) {
  let low = 0;
  let mid = 0;
  let 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--;
    }
  }
};

中文

题目概述

给定只包含 0、1、2 的数组 nums，要求原地重排为 0,1,2 的顺序，使同色元素相邻。

题目强调尽量使用一趟扫描与常数额外空间，并且不要直接调用内置排序。

核心思路

维护三段已确定区间：

- [0 .. low-1] 全是 0
- [low .. mid-1] 全是 1
- [high+1 .. n-1] 全是 2

未知区间是 [mid .. high]。每次处理 nums[mid] 后，未知区间都会缩小。

基线解法

计数法可行：先统计 0/1/2 个数，再覆盖回数组，时间 O(n)、空间 O(1)（固定计数器），但需要两趟遍历。

面试更常考的是一趟扫描的荷兰国旗三路划分。

最优算法（荷兰国旗）

1）初始化 low = 0、mid = 0、high = n - 1。
2）当 mid <= high 时循环：
    a）若 nums[mid] == 0，交换 low 与 mid，然后 low++、mid++。
    b）若 nums[mid] == 1，仅 mid++。
    c）若 nums[mid] == 2，交换 mid 与 high，然后仅 high--（mid 不动）。
3）循环结束时数组有序。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1)。

常见陷阱

- 与 high 交换后立刻 mid++，会漏处理换回来的未知值。
- 循环条件写成 mid < high，可能遗漏最后一个待分类元素。
- 忽视“原地”要求，直接调用库排序。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public void sortColors(int[] nums) {
        int low = 0;
        int mid = 0;
        int high = nums.length - 1;

        while (mid <= high) {
            if (nums[mid] == 0) {
                swap(nums, low, mid);
                low++;
                mid++;
            } else if (nums[mid] == 1) {
                mid++;
            } else {
                swap(nums, mid, high);
                high--;
            }
        }
    }

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

func sortColors(nums []int) {
    low, mid := 0, 0
    high := len(nums) - 1

    for 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--
        }
    }
}

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int low = 0;
        int mid = 0;
        int high = static_cast<int>(nums.size()) - 1;

        while (mid <= high) {
            if (nums[mid] == 0) {
                swap(nums[low], nums[mid]);
                low++;
                mid++;
            } else if (nums[mid] == 1) {
                mid++;
            } else {
                swap(nums[mid], nums[high]);
                high--;
            }
        }
    }
};

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

/**
 * @param {number[]} nums
 * @return {void}
 */
var sortColors = function(nums) {
  let low = 0;
  let mid = 0;
  let 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--;
    }
  }
};