Question

Formatted question description: https://leetcode.ca/all/75.html

Given an array with n objects colored red, white or blue,
sort them 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.

Example:

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


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

click to show follow up.

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 an one-pass algorithm using only constant space?

@tag-array

Algorithm

Freq stats

The essence of this question is still a sorting question. The question gives a hint that it can be sorted by counting. You need to traverse the array twice. Then let’s look at this method first. Because there are only three different elements in the array, it is very easy to implement. easy.

  1. First traverse the original array and record the numbers of 0, 1, and 2 respectively.
  2. Then update the original array and assign 0, 1, 2 according to the number.

Two pointers

In the problem, it is necessary to traverse the array only once to solve it, so you need to use a double pointer to do it, and move from the beginning and the end of the original array to the center.

  1. Define the red pointer to point to the beginning and the blue pointer to point to the end.
  2. Traverse the original array from the beginning,
    • if it encounters 0, exchange the value and the value pointed to by the red pointer, and move the red pointer one bit backward.
    • If it encounters 2, exchange the value and the value pointed to by the blue pointer, and move the blue pointer forward one bit. If it encounters 1, continue to traverse.

Code

Java

  • import java.util.Arrays;
    
    public class Sort_Colors {
    
    	public static void main(String[] args) {
    		Sort_Colors out = new Sort_Colors();
    		Solution s = out.new Solution();
    
    		s.sortColors(new int[]{0, 0});
    	}
    
    	public class Solution {
    	    public void sortColors(int[] nums) {
    	        if (nums == null || nums.length == 0) {
    	            return;
    	        }
    
    	        // idea is: move all "2" to end, all "0" front, then 1 is done itself
    	        // 3 pointers, last-0, current scan, first-2
    
    	        int p0 = 0; // last-0
    	        int p2 = nums.length - 1;
    	        int p = 0; // scan pointer
    
    	        while (p <= p2) {
    
    	            if (nums[p] == 0) {
    
    	                // swap 0 to front. eg: 0,1,1,1,1,1,1,0.      or: 0,0,0,0,0,1
    
    	                int tmp = nums[p0];
    	                nums[p0] = nums[p];
    	                nums[p] = tmp;
    
    	                p0++;
    	                p++;
    
    	            } else if (nums[p] == 2) {
    	                // swap "2" to end
    	                int tmp = nums[p2];
    	                nums[p2] = nums[p];
    	                nums[p] = tmp;
    
    	                p2--;
    	            } else { // assumption: only 0,1,2, so here nums[p]==1
    	                p++;
    	            }
    	        }
    	    }
    	}
    
    	public void sortColors(int[] A) {
    	    if(A==null || A.length==0)
    	        return;
    	    int idx0 = 0;
    	    int idx1 = 0;
    	    for(int i=0;i<A.length;i++)
    	    {
    	        if(A[i]==0)
    	        {
    	            A[i] = 2;
    	            A[idx1++] = 1;
    	            A[idx0++] = 0;
    	        }
    	        else if(A[i]==1)
    	        {
    	            A[i] = 2;
    	            A[idx1++] = 1;
    	        }
    	    }
    	}
    
    }
    
  • // OJ: https://leetcode.com/problems/sort-colors/
    // Time: O(N)
    // Space: O(1)
    class Solution {
    public:
        void sortColors(vector<int>& nums) {
            vector<int> cnt(3, 0);
            for (int n : nums) cnt[n]++;
            int i = 0;
            for (int j = 0; j < 3; ++j) {
                while (cnt[j]--) nums[i++] = j;
            }
        }
    };
    
  • class Solution(object):
      def sortColors(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        x = y = z = -1
        for i in range(0, len(nums)):
          if nums[i] == 0:
            x += 1
            y += 1
            z += 1
            if z != -1:
              nums[z] = 2
            if y != -1:
              nums[y] = 1
            nums[x] = 0
          elif nums[i] == 1:
            y += 1
            z += 1
            nums[z] = 2
            if x != -1:
              nums[x] = 0
            if y != -1:
              nums[y] = 1
          elif nums[i] == 2:
            z += 1
            if y != -1:
              nums[y] = 1
            if x != -1:
              nums[x] = 0
            nums[z] = 2
    
    

All Problems

All Solutions