One pass constant space Java solution of sort colors


  • 0
    A

    Very simple solution
    Start from the left with 2 pointers
    Operate only if the index is greater than left pointer and less than right pointer
    When element is 0 swap it with the left most non zero element, else keep moving right untill you find an element that is not 0
    When element is 2 swap it with the right most non zero element, else keep moving left untill you find an element that is not 2
    Also keep checking the exit condition if index > left and index < right also left < right
    Please do correct me if I am wrong or suggest any improvements possible. I'd greatly appreciate it.

        public void sortColors(int[] nums) 
        {
            //start from the end and start with 2 pointers fill the rest with 1's
            int len = nums.length;
            int i = 0;
            
            int left = 0;
            int right = len-1;
            
            if(len == 1 || len == 0)
                return;
            
            while(i<len && i<=right)
            {
                if(nums[i] == 2)
                {
                    while(nums[right] == 2 && right > left)
                    {
                        right--;
                    }
                    //swap(i,right); only if right has value other than 2 
                    //else move right to its 
                    //left by one position
                    if(i < right)
                    {
                        nums[i] = nums[right];
                        nums[right] = 2;
                        right--;
                        
                        if(nums[i] == 0)
                        {
                            nums[i] = nums[left];
                            nums[left] = 0;
                            left++;
                        }
                        i++;
                        continue;
                    }
                }
                if(nums[i] == 0)
                {
                    while(nums[left] == 0 && left < right)
                    {
                        left++;
                    }
                    
                    if(i > left)
                    {
                        nums[i] = nums[left];
                        nums[left] = 0;
                        left++;
                        if(nums[i] == 2)
                        {
                            nums[i] = nums[right];
                            nums[right] = 2;
                            right--;
                        }
                        i++;
                        continue;
                    }
                }
                i++;
            }
        }
    

Log in to reply
 

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