75. Sort Colors

Description

Given an array 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.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Intuition: The problem is known as Dutch National Flag Problem and first was proposed by Edsger W. Dijkstra. The idea is to attribute a color to each number and then to arrange them following the order of colors on the Dutch flag.

Note: You are not suppose to use the library's sort function for this problem.

Constraints

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

Examples

Example 1

Input: [2, 0, 2, 1, 1, 0]

Output: [0, 0, 1, 1, 2, 2]

Solutions

Solution 1

/**
 * Time complexity : O(N) since it's one pass along the array of length N.
 * Space complexity : O(1) since it's a constant space solution.
 */

class Solution {
    public void sortColors(int[] nums) {
        int left = 0, right = nums.length-1;
        int curr = 0, tmp;
        while(curr <= right) {
            if(nums[curr] == 0) {
                tmp = nums[left];
                nums[left++] = nums[curr];
                nums[curr++] = tmp;
            } else if(nums[curr] == 2) {
                tmp = nums[right];
                nums[right--] = nums[curr];
                nums[curr] = tmp;
            } else {
                curr++;
            }
        }
    }
}

Follow up

• A rather straight forward solution is a two-pass algorithm using counting sort. First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.

• Could you come up with a one-pass algorithm using only constant space?