Simple two pass O(n) time and O(1) space solution in Java


  • 0
    A

    Approach:
    Here the array contains 3 numbers 0,1 and 2, each representing a color. Since we have exactly 3 colors in our sample space, all we need to do is to count the number of occurrences of each color in the first pass and refill the array with numbers based on the counts in the next pass.
    Eg: MyArray = [1,0,2,2,0,1]
    In the first pass, we make note of the number of occurrences of each color ( or number ) in the array. In our case, each number exists exactly twice in the array.
    So in the second pass, we fill the array with colors in order as per the number of occurrence of each color. Hence we fill the array as
    2 0's, 2 1's followed by 2 2's since each number occurs twice in the array.

    class Solution {
        public void sortColors(int[] nums) {
            int zero_count = 0,one_count=0;
            for(int i:nums){
                if(i==0)
                    zero_count++;
                else if(i==1)
                    one_count++;
                else
                    continue;
            }
            for(int i=0;i<nums.length;i++){
                if(zero_count-- > 0)
                    nums[i]=0;
                else if(one_count-- > 0)
                    nums[i]=1;
                else
                    nums[i]=2;
            }
        }
    }
    

  • 0
    M
    class Solution {
        public void sortColors(int[] nums) {
              int [] c = new int[3];
             // store counts for respective index
             for(int n:nums) {
                 c[n] =c[n] + 1;
             } 
             //track offset
             int k=0;  
            for(int i=0; i<c.length; i++) {
                 for(int j=0; j< c[i]; j++) {
                     // overwrite location from offset
                     nums[k+j] = i; 
                 }
                 // set new offset
                 k += c[i];
             }
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.