Sort Colors

---

Sort Colors: 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.

Example 1:

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

---

Example 2:

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

---

Constraints:

• n == nums.length
• 1 <= n <= 300
• nums[i] is either 0, 1, or 2.

---

Try this Problem on your own or check similar problems:

1. Sort List
2. Wiggle Sort II

Solution:

Java

class Solution {
  public void sortColors(int[] nums) {
      int lower = 0, equal = 0, higher = nums.length - 1;
      while(equal <= higher){
          if(nums[equal] == 1){
            ++equal;
          }else if(nums[equal] == 0){
            swap(nums, lower++, equal++);
          }else{
            swap(nums, higher--, equal);
          }
      }
  }
  private void swap(int[] nums, int i, int j){
      int temp = nums[i];
      nums[i] = nums[j];
      nums[j] = temp;
  }
}

JavaScript

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var sortColors = function (nums) {
  let lower = 0;
  let equal = 0;
  let higher = nums.length - 1;
  while (equal <= higher) {
    if (nums[equal] === 1) {
      equal += 1;
    } else if (nums[equal] === 0) {
      [nums[lower], nums[equal]] = [nums[equal], nums[lower]];
      lower += 1;
      equal += 1;
    } else {
      [nums[equal], nums[higher]] = [nums[higher], nums[equal]];
      higher -= 1;
    }
  }
};

Python

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        lower = 0
        equal = 0
        higher = len(nums) - 1
        while equal <= higher:
            if nums[equal] == 1:
                equal += 1
            elif nums[equal] == 0:
                nums[lower], nums[equal] = nums[equal], nums[lower]
                lower += 1
                equal += 1
            else:
                nums[equal], nums[higher] = nums[higher], nums[equal]
                higher -= 1

C++

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int lower = 0;
        int equal = 0;
        int higher = nums.size() - 1;
        while (equal <= higher) {
            if (nums[equal] == 1) {
                equal += 1;
            } else if (nums[equal] == 0) {
                swap(nums[lower], nums[equal]);
                lower += 1;
                equal += 1;
            } else {
                swap(nums[equal], nums[higher]);
                higher -= 1;
            }
        }
    }
};

---

Time/Space Complexity:

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

---

Explanation:

The problem is also called Dutch National Flag Algorithm and can be solved in linear time using three pointers. In our solution we have an equal pointer which tries to collect 1 (the white color in the Dutch flag) and serves as iterator traversing the array, while we also have writer lower for the first color (red) and higher for the third color (blue). We have three situations while iterating through the array:

• Current number is 1 so we just increment the equal.
• Current number is 0, in that case we have swap the elements that lower and equal are pointing (in other words we place 0 on beginning of array, and push 1 to the middle), and we increment both writers.
• The last scenario is when we have 2, so we place it to the end of array where higher is currently pointing, but this time we can't increment the equal writer since we don’t know what the element was at the end of array. Note that this is not the case when we're getting the numbers from the beginning of the array since equal already knows about them (it already iterated over them).