How does the two-pointer scanning pattern work in Sort Colors?

Two-pointer scanning divides the array into partitions for 0s, 1s, and 2s. Swaps move colors to the correct partition while maintaining invariant positions, ensuring in-place sorting with O(n) time and O(1) space.

Can I use Python's sort function for this problem?

No, using built-in sorting functions is prohibited. The problem requires explicitly rearranging elements using in-place strategies like two-pointer scanning or counting methods.

What is the main advantage of the single-pass approach over two-pass counting?

Single-pass two-pointer scanning avoids iterating over the array multiple times, efficiently maintaining partition invariants and moving each element directly to its correct position.

How do I handle edge cases such as arrays with all identical colors?

Edge cases require careful pointer handling. If all elements are the same, swaps may not occur, but the invariant tracking still ensures correct partitions without errors or infinite loops.

Why is it important to update indices carefully after each swap?

Incorrect index updates can cause skipped elements or repeated swaps, violating the partition invariant and producing incorrect final order, which is a common failure mode for this problem.

#75

Medium

auto_awesome双·指针·invariant

LeetCode 题解工作台

颜色分类

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。我们使用整数 0 、 1 和 2 分别表示红色、白色和蓝色。必须在不使用库内置的 sort 函数的情况下解决这个问题。示例 1：输入： nums =…

数组双指针排序

题目描述

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

示例 1：

输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

示例 2：

输入：nums = [2,0,1]
输出：[0,1,2]

提示：

n == nums.length
1 <= n <= 300
nums[i] 为 0、1 或 2

进阶：

你能想出一个仅使用常数空间的一趟扫描算法吗？

lightbulb

解题思路

方法一：三指针

我们定义三个指针 $i$ , $j$ 和 $k$ ，其中指针 $i$ 用于指向数组中元素值为 $0$ 的最右边界，指针 $j$ 用于指向数组中元素值为 $2$ 的最左边界，初始时 $i=-1$ , $j=n$ 。指针 $k$ 用于指向当前遍历的元素，初始时 $k=0$ 。

当 $k \lt j$ 时，我们执行如下操作：

若 $nums[k]=0$ ，则将其与 $nums[i+1]$ 交换，然后 $i$ 和 $k$ 都加 $1$ ；
若 $nums[k]=2$ ，则将其与 $nums[j-1]$ 交换，然后 $j$ 减 $1$ ；
若 $nums[k]=1$ ，则 $k$ 加 $1$ 。

遍历结束后，数组中的元素就被分成了 $[0,i]$ , $[i+1,j-1]$ 和 $[j,n-1]$ 三个部分。

时间复杂度 $O(n)$ ，其中 $n$ 是数组的长度。只需要遍历一遍数组即可。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        i, j, k = -1, len(nums), 0
        while k < j:
            if nums[k] == 0:
                i += 1
                nums[i], nums[k] = nums[k], nums[i]
                k += 1
            elif nums[k] == 2:
                j -= 1
                nums[j], nums[k] = nums[k], nums[j]
            else:
                k += 1

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Do you correctly maintain the low, mid, and high pointers to enforce the invariant?
question_mark
Can you handle arrays where all elements are the same or already partially sorted?
question_mark
Will you update indices carefully after each swap to avoid overwriting unsorted values?

warning

常见陷阱

外企场景

error
Swapping a 0 or 2 without updating the current index can skip elements or cause infinite loops.
error
Failing to maintain the invariant partitions correctly can mix colors and require multiple passes.
error
Edge cases like single-element arrays or arrays with only one color may break naive implementations if not handled.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Sort Colors II: Extend the problem to k colors represented by integers 0 to k-1, still requiring in-place ordering.
arrow_right_alt
Dutch National Flag Variant: Separate an array into three partitions based on a pivot value, testing invariant tracking under different rules.
arrow_right_alt
Sort Colors with Stability: Sort the array while preserving the relative order of 1s to test the effect on two-pointer swaps.

help

常见问题

外企场景

继续练习

#88 合并两个有序数组 #18 四数之和 #16 最接近的三数之和