75. Sort Colors

Given an array of 0s (red), 1s (white) and 2s (blue), sort it in place so equal colors are adjacent, in the order red, white, blue. Don't use the library sort.

Keep three regions: [0, lo) are 0s, [lo, mid) are 1s, (hi, end] are 2s. Look at nums[mid]: send 0s left, 2s right, and step over 1s.

1function sortColors(nums: number[]): void {
2  let lo = 0, mid = 0, hi = nums.length - 1;
3  while (mid <= hi) {
4    if (nums[mid] === 0) { [nums[lo], nums[mid]] = [nums[mid], nums[lo]]; lo++; mid++; }
5    else if (nums[mid] === 1) mid++;
6    else { [nums[mid], nums[hi]] = [nums[hi], nums[mid]]; hi--; }
7  }
8}

nums[mid] = 2

nums

lo,mid

Everything is unsorted: lo = mid = 0, hi = end.

1 / 0

Space: play/pause · ←/→: step