Sort Colors | Leetcode 75 | Brute, Better and Optimal

LeetCode “Sort Colors” (#75) asks you to sort an array that contains only three distinct values—0, 1, and 2—so that all 0s come first, then all 1s, and finally all 2s.
The trick: do it entirely in-place and, ideally, in a single pass.

The problem is famously solved by the Dutch National Flag algorithm—but we’ll walk through three escalating solutions to see how you reach that “optimal” idea.

Here’s the [Problem Link] to begin with.

Brute Force Solution (Built-in Sort)

Intuition & Approach

Why overthink? Python’s list.sort() already arranges numbers in non-decreasing order. Because the array has only three distinct values, simply calling sort() achieves the goal—though it doesn’t respect the spirit of the challenge.

Code Implementation

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        nums.sort()  # use Python’s Timsort (O(n log n))

Code Explanation

• nums.sort() uses Timsort (O(n log n)) and extra space for recursion overhead.
• Passes LeetCode but isn’t linear and feels like cheating.

Dry Run

Input [2, 0, 1] → after sort() → [0, 1, 2].

Time & Space Complexity

• Time: O(n log n) – general-purpose sorting.
• Space: O(1) extra (in-place operations only).

Conclusion

Quick and dirty, fine for production if constraints are tiny, but interviewers expect a linear-time answer.

Better Solution (Counting Sort)

Intuition & Approach

With only three distinct values you can:

1. Count occurrences of 0, 1, and 2.
2. Overwrite the array: first count(0) zeros, then count(1) ones, then count(2) twos.

Code Implementation

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        # Counters for each color
        cnt1 = 0  # number of 0s
        cnt2 = 0  # number of 1s
        cnt3 = 0  # number of 2s

        # First pass – count frequencies
        for i in range(0, n):
            if nums[i] == 0:
                cnt1 += 1
            elif nums[i] == 1:
                cnt2 += 1
            else:
                cnt3 += 1

        # Second pass – overwrite array based on counts
        for i in range(0, cnt1):
            nums[i] = 0
        for i in range(cnt1, cnt1 + cnt2):
            nums[i] = 1
        for i in range(cnt1 + cnt2, cnt1 + cnt2 + cnt3):
            nums[i] = 2

Code Explanation

• Two passes: the first tallies colors, the second rewrites positions.
• Still linear, but touches the array twice and allocates three extra counters.

Dry Run ([2, 0, 2, 1, 1, 0])

• Counts → cnt1=2, cnt2=2, cnt3=2.
• Rewrite → [0, 0, 1, 1, 2, 2].

Time & Space Complexity

• Time: O(n) – two linear scans.
• Space: O(1) – only three integer counters.

Conclusion

Solid and simple. Yet we can squeeze to one pass with the Dutch National Flag trick.

Optimal Solution (Dutch National Flag / One-Pass, Three Pointers)

Intuition & Approach

Maintain three regions within the array:

• 0 … low-1 → all 0s
• low … mid-1 → all 1s
• mid … high → unknown / unprocessed
• high+1 … end → all 2s

Process the mid pointer:

• If nums[mid] == 0 → swap with low, increment both low & mid.
• If nums[mid] == 1 → correct spot, just increment mid.
• If nums[mid] == 2 → swap with high, decrement high (don’t move mid yet).

Code Implementation

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        low = 0                # boundary for 0s
        mid = 0                # current element
        high = len(nums) - 1   # boundary for 2s

        while mid <= high:
            if nums[mid] == 0:
                # swap current 0 into 0s region
                nums[low], nums[mid] = nums[mid], nums[low]
                low += 1
                mid += 1
            elif nums[mid] == 1:
                # 1 is already in correct middle region
                mid += 1
            else:
                # swap current 2 into 2s region
                nums[mid], nums[high] = nums[high], nums[mid]
                high -= 1

Code Explanation

• Three pointers partition the array dynamically.
• Each swap places a 0 or 2 into its definitive region, so every element is handled at most once.
• Only one full sweep needed.

Dry Run ([2, 0, 2, 1, 1, 0])

Time & Space Complexity

• Time: O(n) – exactly one pass.
• Space: O(1) – only three indices.

Conclusion

The Dutch National Flag algorithm is the interview-ready, optimal solution:

• Single pass
• Constant space
• Elegant pointer dance

Final Thoughts

• Brute (sort): quickest to code, but O(n log n) and conceptually boring.
• Counting Sort: two linear passes, fine space, but still touches data twice.
• Dutch National Flag: one-pass, one-swap perfection, always aim for this in interviews.

Master these three tiers and you’ll be prepared for any “multi-value partition” problem that comes your way. Happy sorting!

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.