@meta
title: Sort Colors
questionNo: 5
totalQuestions: 191
sheetLabel: Striver SDE Sheet
sourceLabel: TakeUForward
@endmeta

@page
tag: A
pageNo: 1 / 1
totalPages: 1
@endpage

@section
region: full
title: Problem Statement
content:
Given an array nums containing only 0, 1, and 2, sort it in-place so that same colors are adjacent.
Do not use the library sort for the intended interview solution.
This is the Dutch National Flag problem.
@endsection

@section
region: left
title: Examples
content:
Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
Explanation: All 0s move left, 1s stay in the middle, and 2s move right.
---
Input: nums = [2,0,1]
Output: [0,1,2]
Explanation: A single linear scan is enough with three pointers.
@endsection

@section
region: right
title: Custom Notes
content:
- low marks the next place for 0.
- mid scans the unknown region.
- high marks the next place for 2.
- When swapping with high, do not increment mid yet.
- Memory hook: left 0s, middle 1s, right 2s.
@endsection

@section
region: full
title: Brute Force Approach : TC: SC:
badge: 1 / 3
content:
Algorithm: Use built-in sort or any comparison sort.
Pseudo:
- Call sort(nums.begin(), nums.end()) or equivalent.
Time: O(n log n)
Space: Depends on sort implementation
Why mention it: It is correct but ignores the structure of the problem where values are only 0, 1, and 2.
@endsection

@section
region: full
title: Better Approach : TC: SC:
badge: 2 / 3
content:
Algorithm: Count the number of 0s, 1s, and 2s, then overwrite the array.
Pseudo:
- First pass: count zeros, ones, twos.
- Second pass: fill the array with that many 0s, then 1s, then 2s.
Time: O(n)
Space: O(1)
Interview line: Easy and valid, but not the most elegant one-pass in-place partitioning answer.
@endsection

@section
region: full
title: Optimal Approach : TC: SC:
badge: 3 / 3
content:
Algorithm: Maintain three pointers low, mid, and high.
Pseudo:
- If nums[mid] == 0, swap nums[low] and nums[mid], then low++ and mid++.
- If nums[mid] == 1, just mid++.
- If nums[mid] == 2, swap nums[mid] and nums[high], then high-- only.
- Continue while mid <= high.
Time: O(n)
Space: O(1)
Key insight: After swapping with high, the incoming value at mid is still unprocessed, so mid must stay.
@endsection

@section
region: grid
title: PCode
badge: 1 / 3
codeLang: pseudo
content:
sort nums using any standard comparison sort
RETURN nums
@endsection

@section
region: grid
title: PCode
badge: 2 / 3
codeLang: pseudo
content:
zeros = 0
ones = 0
twos = 0

FOR each value in nums
    increment zeros or ones or twos

rewrite nums with zeros copies of 0
then ones copies of 1
then twos copies of 2

RETURN nums
@endsection

@section
region: grid
title: PCode
badge: 3 / 3
codeLang: pseudo
content:
low = 0
mid = 0
high = n - 1

WHILE mid <= high
    IF nums[mid] == 0
        swap nums[low] and nums[mid]
        low = low + 1
        mid = mid + 1
    ELSE IF nums[mid] == 1
        mid = mid + 1
    ELSE
        swap nums[mid] and nums[high]
        high = high - 1

RETURN nums
@endsection