Java solution using one pass and constant space


  • 0
    C

    I was asked this question in a interview, slightly different way. Given an input array of 1s and 0s, how will you sort it in linear time and in constant space.

        public void sortColors(int[] nums) {
            // using insertion sort logic
            for(int i=0,j=0,k=0; k<nums.length; k++){
                int temp = nums[k];
                
                //assigning the current as max
                nums[k] = 2;
                
                // if original is less than 2 then it should be 1
                if(temp < 2){
                    nums[j] = 1;
                    j +=1;
                }
                
                // if original is less than 1 then it should be 0. The above if statement ensures that 1 - index 
                // will always be greater than 0 - index
                if(temp < 1){
                    nums[i] = 0;
                    i += 1;
                }
            }
        }
    

Log in to reply
 

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