Sort Colors | Problems

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.

Sample Input

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

Sample Output

[0,0,1,1,2,2]

Constraints

1 <= nums.length <= 300
nums[i] is 0, 1, or 2

Test Cases

Case 1

Args: [[2,0,2,1,1,0]] Expected: [0,0,1,1,2,2]

Topics

Array Two Pointers

Use the Dutch National Flag algorithm with three pointers — low, mid, and high — to sort the array in a single pass. Swap 0s to the front, 2s to the back, and leave 1s in the middle.

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--;
    }
  }
}

Time: O(n) Space: O(1)

Saved in this browser only. Private to you.