#75MediumDutch National Flag

Sort Colors

Dutch National Flag — partition into 3 groups with one pass.

MicrosoftAmazonFacebookPocket Gems

Problem Statement

Given an array nums containing only 0, 1, and 2, sort it in-place so that objects of the same color are adjacent (0s, then 1s, then 2s). Do not use the library sort function.

Examples

Example 1

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

Example 2

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

Constraints

  • n == nums.length
  • 1 ≤ n ≤ 300
  • nums[i] is 0, 1, or 2.

Solutions

1
Count Sort (Two-Pass)
TimeO(n)SpaceO(1)

Count occurrences of 0, 1, 2. Then overwrite the array with the correct count of each. Simple and O(n) but requires two passes.

Visual Animation
def sortColors(nums: list[int]) -> None:
    c = [0, 0, 0]
    for n in nums: c[n] += 1
    i = 0
    for val in range(3):
        for _ in range(c[val]):
            nums[i] = val; i += 1

Related Concepts

Deepen your understanding with these related topics from our AI Glossary:

Machine LearningBrowse all 190+ concepts →
Deepen your understanding

Want to master the core concepts?

Our free AI Glossary covers 190+ topics — from Dutch National Flag to Dynamic Programming, Machine Learning, SQL, and more. Structured learning tracks for every level.

Browse AI Glossary All Problems
39+
AI Models
₹69
Per day used
4
Languages

Stuck? Ask AI to explain it step by step.

Ask Claude, GPT-4o, or Gemini to debug your code, generate test cases, or walk through the intuition. 39+ models. Pay only on days you use it — no subscription required.

Free to start · No credit card required to explore

Get Started Free
Back to all problems