Master Sort Colors (LeetCode 75): Dutch National Flag 3-Way Partition | Day 5 of 180

Master Sort Colors (LeetCode 75): Dutch National Flag 3-Way Partition | Day 5 of 180

by 

================================================================================
BLOG ARTICLE CONTENT (Markdown / HTML)
================================================================================

# 180-Day DSA Roadmap | Day 5: Sort Colors (LeetCode #75)

* **Topic:** Arrays & Strings  
* **Pattern:** Dutch National Flag (3-Way Partitioning)  
* **Difficulty:** Medium  
* **LeetCode Problem:** LeetCode #75 - Sort Colors  
* **Target Companies:** Amazon, Microsoft, Adobe, Apple, Salesforce, Google  

---

## 1. Problem Overview

Given an array `nums` with `n` objects colored red, white, or blue, sort them **in-place** so that objects of the same color are adjacent, with the colors in the order red (0), white (1), and blue (2).

We use the integers `0`, `1`, and `2` to represent the color red, white, and blue, respectively.

### Constraints & Requirements
* `n == nums.length`
* `1 <= n <= 300`
* `nums[i]` is either `0`, `1`, or `2`.
* You must solve this problem **without** using the library's sort function.
* **Follow-up:** Could you come up with a **one-pass** algorithm using only constant extra space?

### Example Walkthrough
```text
Input: nums = [2, 0, 2, 1, 1, 0]
Output: [0, 0, 1, 1, 2, 2]

Explanation:
All 0s are partitioned to the beginning, followed by all 1s, and all 2s are pushed to the end.

2. Pattern Recognition: Why Dutch National Flag?

In standard two-pointer partitioning (such as in QuickSort), you partition elements into two categories: smaller than pivot and greater than pivot.

However, when a problem involves exactly three distinct categories (like 0, 1, 2, negative/zero/positive, or < pivot, == pivot, > pivot), a 2-way split requires multiple passes.

Edsger W. Dijkstra formulated the Dutch National Flag (DNF) algorithm to divide an array into 3 partitions in a single pass with strictly $O(1)$ auxiliary space.

The technique maintains 3 pointers dividing the array into 4 distinct regions:

  • nums[0 ... low - 1]: Processed 0s (Red)
  • nums[low ... mid - 1]: Processed 1s (White)
  • nums[mid ... high]: Unknown / Unprocessed elements
  • nums[high + 1 ... n - 1]: Processed 2s (Blue)

3. Algorithmic Approaches

Approach 1: Two-Pass Counting Sort (Suboptimal)

  • Count frequencies of 0, 1, and 2 during a first pass. Overwrite nums during a second pass.
  • Time Complexity: $O(N)$
  • Space Complexity: $O(1)$
  • Verdict: Passes test cases, but interviewers explicitly ask for a single pass to evaluate your pointer partitioning skills.

Approach 2: Optimal Dijkstra’s 3-Way Partition (MNC Standard)

  • Initialize: low = 0, mid = 0, and high = nums.length - 1.
  • Process the element at nums[mid] until mid > high:
    • Case 1: nums[mid] == 0
      Belongs in the 0s section. Swap nums[low] and nums[mid].
      Advance both low++ and mid++.
    • Case 2: nums[mid] == 1
      Already in the correct middle bucket. Simply advance mid++.
    • Case 3: nums[mid] == 2
      Belongs in the 2s section. Swap nums[mid] and nums[high].
      Shrink high--. (Do not advance mid! See explanation below).

Plaintext

Visual Execution Trace:
Input: nums = [2, 0, 2, 1, 1, 0]
Pointers: low = 0, mid = 0, high = 5

Step 1: nums[mid] is 2
  Swap nums[mid] & nums[high] (index 0 & 5), high--
  [0, 0, 2, 1, 1, 2] | low = 0, mid = 0, high = 4

Step 2: nums[mid] is 0
  Swap nums[low] & nums[mid] (index 0 & 0), low++, mid++
  [0, 0, 2, 1, 1, 2] | low = 1, mid = 1, high = 4

Step 3: nums[mid] is 0
  Swap nums[low] & nums[mid] (index 1 & 1), low++, mid++
  [0, 0, 2, 1, 1, 2] | low = 2, mid = 2, high = 4

Step 4: nums[mid] is 2
  Swap nums[mid] & nums[high] (index 2 & 4), high--
  [0, 0, 1, 1, 2, 2] | low = 2, mid = 2, high = 3

Step 5: nums[mid] is 1
  mid++
  [0, 0, 1, 1, 2, 2] | low = 2, mid = 3, high = 3

Step 6: nums[mid] is 1
  mid++
  [0, 0, 1, 1, 2, 2] | low = 2, mid = 4, high = 3 (mid > high: LOOP TERMINATES)

Result: [0, 0, 1, 1, 2, 2]

4. Production-Ready Code Implementations

Java Solution

Java

class Solution {
    public void sortColors(int[] nums) {
        int low = 0;
        int mid = 0;
        int high = nums.length - 1;

        while (mid <= high) {
            if (nums[mid] == 0) {
                swap(nums, low, mid);
                low++;
                mid++;
            } else if (nums[mid] == 1) {
                mid++;
            } else { // nums[mid] == 2
                swap(nums, mid, high);
                high--;
            }
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

Python 3 Solution

Python

class Solution:
    def sortColors(self, nums: list[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        low, mid, high = 0, 0, len(nums) - 1

        while mid <= high:
            if nums[mid] == 0:
                nums[low], nums[mid] = nums[mid], nums[low]
                low += 1
                mid += 1
            elif nums[mid] == 1:
                mid += 1
            else: # nums[mid] == 2
                nums[mid], nums[high] = nums[high], nums[mid]
                high -= 1

C++ Solution

C++

#include <vector>
#include <algorithm>

class Solution {
public:
    void sortColors(std::vector<int>& nums) {
        int low = 0;
        int mid = 0;
        int high = nums.size() - 1;

        while (mid <= high) {
            if (nums[mid] == 0) {
                std::swap(nums[low], nums[mid]);
                low++;
                mid++;
            } else if (nums[mid] == 1) {
                mid++;
            } else { // nums[mid] == 2
                std::swap(nums[mid], nums[high]);
                high--;
            }
        }
    }
};

5. Complexity Analysis

  • Time Complexity: $O(N)$
    In every iteration of the while loop, either mid increments or high decrements. Because mid and high start at opposite ends and move toward each other, the loop runs at most $N$ times.
  • Space Complexity: $O(1)$
    The algorithm operates directly on the input array in-place, maintaining only three scalar pointers (low, mid, high).

6. Key Takeaways & Common Interview Traps

  • The high Swap Trap: Why does mid NOT increment when nums[mid] == 2?
    When you swap nums[mid] with nums[high], the value originally sitting at high was in the unexplored region. It could be a 0, 1, or 2. If you increment mid, you would skip checking this swapped-in value. You must inspect nums[mid] again in the next iteration.
  • Loop Termination: The condition must be while (mid <= high), not mid < high. If mid == high, that final element is still unprocessed and must be partitioned into its correct bucket.

Master Sort Colors (LeetCode 75): Dutch National Flag 3-Way Partition | Day 5 of 180


Master LeetCode 75 (Sort Colors) using Dijkstra’s Dutch National Flag algorithm. Learn 3-way partitioning in a single pass with clean Java, Python, and C++ code.

Sort Colors LeetCode 75, Dutch National Flag Algorithm, 3 Way Partitioning In Place, LeetCode 75 Java Python Cpp

leetcode 75, sort colors, dutch national flag algorithm, 3 way partitioning, dijkstra algorithm, dsa roadmap, dsa interview questions, coding interview preparation, data structures and algorithms, leetcode solutions, two pointers pattern, three pointers pattern, leetcode medium, faang interview preparation, mnc coding questions, amazon coding interview, google coding interview, microsoft interview questions, meta coding interview, adobe coding questions, apple interview questions, leetcode 75 java, leetcode 75 python, leetcode 75 cpp, java dsa, python dsa, cpp dsa, time complexity o n, space complexity o 1, array interview questions, inplace sorting, array partition, top dsa patterns, software engineer jobs, campus placement preparation, competitive programming, vs coding academy, 180 days dsa, dsa cheat sheet, cracking the coding interview, tech interview prep, leetcode patterns, software development engineer, sde 1 preparation, array algorithms, single pass algorithm, coding questions for freshers, dsa placement series, engineering placements, leetcode practice, data structures roadmap

Follow our YouTube Channels:
Trendy VS Vlogs: https://youtube.com/@trendyvsvlogs?si=Xd3L31p5zPXggomY
WhatsApp Channel: https://whatsapp.com/channel/0029Vb9H4vC545v2HaoKk735

Leave a Comment