Sort colors (Dutch national flag)

Medium TimeO(n) SpaceO(1)

The array nums holds only 0s, 1s and 2s — red, white and blue, the Dutch national flag. Sort it in place and in a single pass, with no counting pass and no second array, so every 0 comes first, then the 1s, then the 2s. Equal values need no particular order among themselves.

Examples

Example 1

Input
nums = [2, 0, 2, 1, 1, 0]
Output
[0,0,1,1,2,2]
Two of each colour, gathered: the 0s, then the 1s, then the 2s.

Example 2

Input
nums = [2, 0]
Output
[0,2]
One of each, and the pair is exchanged.

The Code

function sortColors(nums) {
  let low = 0;
  let mid = 0;
  let high = nums.length - 1;
  while (mid <= high) {
    if (nums[mid] === 0) {
      const t = nums[low];
      nums[low] = nums[mid];
      nums[mid] = t;
      low++;
      mid++;
    } else if (nums[mid] === 1) {
      mid++;
    } else {
      const t = nums[mid];
      nums[mid] = nums[high];
      nums[high] = t;
      high--;
    }
  }
  return nums;
}
sortColors([2, 0, 2, 1, 1, 0]);
Done
Step through sortColors([2, 0, 2, 1, 1, 0]) call by call

More like this

All two pointers examples (9) →