Sort Colors Medium 0 attempts
LeetCode ↗

Sort Colors

Medium ArrayTwo Pointers LeetCode

You're given an array nums representing n objects, each colored red, white, or blue and encoded as the integers 0, 1, and 2 respectively. Rearrange the array in-place so objects of the same color end up next to each other, with the groups ordered red, then white, then blue.

Input Format
Implement sortColors(nums). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Modify argument 1 in place. The editor compares its final value; the function return value is ignored.

Sample Input and Output

Example 1 · Run Sample

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

Example 2

Input
nums = [2,0]
Output
[0,2]
Constraints
  • 1 <= nums.length <= 300
  • nums[i] is 0, 1, or 2
Test Cases (2)
Case 1
Args: [[2,0,2,1,1,0]] Expected: [0,0,1,1,2,2]
Case 2
Args: [[2,0]] Expected: [0,2]
Topics
ArrayTwo 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.

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

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

Saved in this browser only. Private to you.

JavaScript