Sort Colors

·#75·Medium·Two Pointers

Dutch flag · sort 0s, 1s, 2s in-place in a single pass

Asked at:MicrosoftFacebook

Practice mode

Try your own input

Change the array and replay the algorithm from step one.

Step

Current step

Dutch National Flag: sort 0s (red), 1s (white), 2s (blue) in one pass.

Array workspace

Dutch National Flag

Step 1 / 20init

100%

[0]

[1]

[2]

[3]

[4]

[5]

step 1 / 20

Space play← → stepHome reset

TimeO(n)·SpaceO(1)

Dutch National Flag

1function sortColors(nums) {//low: 0mid: 0high: 5
2  let low = 0, mid = 0, high = nums.length - 1;
3  while (mid <= high) {
4    if (nums[mid] === 0) {
5      [nums[low], nums[mid]] = [nums[mid], nums[low]];
6      low++; mid++;
7    } else if (nums[mid] === 1) {
8      mid++;
9    } else {
10      [nums[mid], nums[high]] = [nums[high], nums[mid]];
11      high--;
12    }
13  }
14}

low0

mid0

high5

Command Palette

Sort Colors

Sort Colors