Explorer
Data Structures & Algorithms

Sort an array of 0's, 1's, and 2's in-place without using built-in sort (Dutch National Flag problem).

Problem Statement

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, white, and blue. We will use the integers `0`, `1`, and `2` to represent the color red, white, and blue, respectively. You must solve this problem without using the library's sort function and return the sorted array.

Examples

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

Output: [0, 0, 1, 1, 2, 2]

Explanation: The array sorted in ascending order of colors.

Input: nums = [2, 0, 1]

Output: [0, 1, 2]

Explanation: All 0s are placed first, followed by 1s, and then 2s.

Complexity

Time Complexity: O(N)

Space Complexity: O(1)

Hints

šŸ’” Hint 1: This is known as the Dutch National Flag problem. šŸ’” Hint 2: Use 3 pointers: low, mid, high. Invariant: [0...low-1] are 0s, [low...mid-1] are 1s, [high+1...n-1] are 2s. šŸ’” Hint 3: When nums[mid] === 0, swap with low and advance both. When 1, advance mid. When 2, swap with high and decrement high.

Editorial & Approach

Problem Overview & Intuition

The Dutch National Flag algorithm partitions the array into three sections using three pointers: low, mid, and high. By swapping elements into their designated partition in a single pass, we achieve O(N) time and O(1) space.

Step-by-Step Approach

  1. Set low = 0, mid = 0, high = nums.length - 1.
  2. While mid <= high:
  3. If nums[mid] === 0: swap nums[low] and nums[mid], then low++ and mid++.
  4. If nums[mid] === 1: mid++.
  5. If nums[mid] === 2: swap nums[mid] and nums[high], then high--.
  6. Return nums.

Optimal Implementation (JavaScript)

function sortColors(nums) {
  let low = 0, mid = 0, high = nums.length - 1;
  while (mid <= high) {
    if (nums[mid] === 0) {
      [nums[low], nums[mid]] = [nums[mid], nums[low]];
      low++;
      mid++;
    } else if (nums[mid] === 1) {
      mid++;
    } else {
      [nums[mid], nums[high]] = [nums[high], nums[mid]];
      high--;
    }
  }
  return nums;
}

Complexity Analysis

Time Complexity O(N) ā€” single pass with at most N pointer steps.
Space Complexity O(1) ā€” in-place three-way partition.

Edge Cases & Corner Traps Handled

  • Array with only one type of color (e.g. all 0s, all 1s, or all 2s).
  • Already sorted array.
  • Reverse sorted array [2, 2, 1, 1, 0, 0].

Sort an array of 0's 1's and 2's

Medium
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, white, and blue. We will use the integers `0`, `1`, and `2` to represent the color red, white, and blue, respectively. You must solve this problem without using the library's sort function and return the sorted array.
Example Scenarios
1Example 1
Input: nums = [2, 0, 2, 1, 1, 0]
Output: [0, 0, 1, 1, 2, 2]
Explanation:

The array sorted in ascending order of colors.

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

All 0s are placed first, followed by 1s, and then 2s.

Editor
Loading Editor...
nums =
[2, 0, 2, 1, 1, 0]
Output:Click "Run" above to execute and verify your code here.
[0,0,1,1,2,2]