Sort Colors

MEDIUM

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 01, and 2 to represent the color red, white, and blue, respectively.

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]

Example 3:

Input: nums = [0]
Output: [0]

Example 4:

Input: nums = [1]
Output: [1]

Constraints:

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

Follow up:

  • Could you solve this problem without using the library’s sort function?
  • Could you come up with a one-pass algorithm using only O(1) constant space?

The Dutch national flag problem is a computer science programming problem proposed by Edsger Dijkstra. The flag of the Netherlands consists of three colors: red, white and blue. Given balls of these three colors arranged randomly in a line (it does not matter how many balls there are), the task is to arrange them such that all balls of the same color are together and their collective color groups are in the correct order.

Following is an one pass constant space implementation:

class Solution {
    public void sortColors(int[] nums) {
        
        int l = 0;
        int r = nums.length - 1;
        int cur = 0;
        while(cur <= r){
            int current = nums[cur];
            if(current == 2){
                swap(nums, cur, r);
                r--;
            }else if(current == 0){
                swap(nums, l++, cur++);
            }else{
                cur++;
            }
        }
    }
    
    private void swap(int[] nums, int l, int r){
        int temp = nums[l];
        nums[l] = nums[r];
        nums[r] = temp;
    }
}

Categories: Array

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s