OVERVIEW

Final result

Runtime: 50 ms (top 26%)
Memory: 48.37 MB (top 7%)

Problem Statement

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.

You must solve this problem without using the library's sort function.

Follow up: Could you come up with a one-pass algorithm using only constant extra space?

Example

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

Step 1. Two pointers

My initial idea was to use a bubble sort, but seeing two pointers in the tags and having a one-pass algorith challenge I decided to implement a two pointer solution. From the LeetCode article: "One pointer starts from the beginning while the other pointer starts from the end. They move toward each other until they both meet."

Since there are only 3 values possible, 0's can be swapped with the left pointer, 2's with the right pointer, allowing for an iterator making a single pass possible.

function sortColors(nums) {
  let left = 0;
  let right = nums.length - 1;
  let current = 0;

  while (current <= right) {
      if (nums[current] === 0) {
          [nums[left], nums[current]] = [nums[current], nums[left]];
          left++;
          current++;
      } else if (nums[current] === 1) {
          current++;
      } else {
          [nums[current], nums[right]] = [nums[right], nums[current]];
          right--;
      }
  }
}