2Brute2Best
🔥0

Sort Colors

Medium·LeetCode #75 Pro OnlyBasic Reinforcement
LeetCode
01

Problem Statement

You are given an array nums where every value is 0, 1 or 2 (think of them as red, white and blue).

Rearrange the array in place so that all the 0s come first, then all the 1s, then all the 2s.

You may not use the library sort function. The follow-up asks for a single pass with only constant extra space.

Input

An integer array nums containing only 0, 1 and 2.

Output

Nothing is returned. nums itself must end up as all 0s, then all 1s, then all 2s.

Example 1
Input: nums = [2, 0, 2, 1, 1, 0]
Output: [0, 0, 1, 1, 2, 2]

Two 0s, two 1s and two 2s, grouped in that order.

Example 2
Input: nums = [2, 0, 1]
Output: [0, 1, 2]
Constraints
  • • 1 ≤ nums.length ≤ 300
  • • nums[i] is 0, 1 or 2
  • • Follow-up: one pass, O(1) extra space
02

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“values are only 0, 1 and 2”
→ Three fixed categories with a fixed order → partition into three regions, not general sorting.
“in place, one pass, constant space”
→ No counting pass first. Keep each finished region behind its own pointer and place values as you see them.
“sort (no stability needed)”
→ Equal values are identical, so swapping freely is fine.
03

Approach Complexity Ladder

Brute Force — just sortO(N log N)O(log N)

Call a general sort; ignores that there are only 3 values

Better — count, then rewrite (two passes)O(N)O(1)

Count the 0s, 1s and 2s, then overwrite the array

Optimal — Dutch National Flag (one pass)O(N)O(1)

low / mid / high: send 0s left, 2s right, leave 1s in the middle

Brute Force Intuition

The task says "sort", so sort the array with a normal comparison sort. It works, but it does not use the fact that there are only three possible values. (The problem forbids the library sort, so this is only the starting point.)

Recognition rule for this sub-pattern:

A few fixed categories (0/1/2, even/odd, <pivot/=pivot/>pivot). Keep each finished region behind its own pointer.
Remember this · Two Pointers
Trigger
Sorted array, pairs/triplets with a target, comparing from both ends, compacting an array in place.
Think
If I compare the elements at two positions, can I safely discard one side?
Key question
Which pointer moves, and why can the skipped elements never be the answer?
Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms
Interactive step-by-step playback with pointer & array state transitions
52 comprehensive LLD chapters
Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions
40 C++ basics labs & hardware memory models
Vtables, byte layouts, assembly insights, and multi-threading race conditions
Production-ready C++23 source code
Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways
Create Free AccountLog in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Two Pointers translate into production architectures and low-level memory mechanics.

LLD Architecture

Circular Buffer & Ring Queue

Two pointer read/write head synchronization in production memory pools.

Explore Track
C++ Internals

Pointers vs References Deep Dive

Pointer arithmetic, dereferencing semantics, and memory layout behind in-place array passes.

Explore Track
C++ Internals

const Correctness & East-Const

Passing read-only spans with const int* without copying buffers.

Explore Track
Sort Array By ParityPartition Array According to Given Pivot