Easy to understand O(n) Java solution with detailed comments


  • 0
    S
    public class Solution {
        public void sortColors(int[] nums) {
            int n = nums.length;
            // initialize left, right and arbitrary pointer i to below values
            int left = 0, right = n-1, i=0;
            
            while(i <= right){
                // increment the left pointer until it points to a non-zero value
                while(left <= right && nums[left] == 0){
                    left++;
                }
                // decrement the right pointer until it points to a  non-two value i.e. which is not equal to 2
                while(right >= left && nums[right] == 2){
                    right--;
                }
                // exit when left pointer crosses or points right pointer
                if(left >= right){
                    break;
                }
                //initialize arbitrary pointer 'i' with value of left pointer in below condition
                if(left > i){
                    i = left;
                }
                // if arbitrary pointer points to:
                // case i)    value 1 then increment pointer i
                // case ii)   value 0 then swap the values at indices i and left, followed by incrementing left pointer
                // case iii)  value 2 then swap the values at indices i and right, followed by decrementing right pointer
                if(nums[i] == 1){
                   i++; 
                }else if(nums[i] == 0){
                    swap(nums,i,left);
                    left++;
                }else if(nums[i] == 2){
                    swap(nums,i,right);
                    right--;
                }
            }
        }
        
        // helper method to swap values in an array
        public void swap(int[] nums, int i, int j){
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }
    

  • 0
    S

    @satya_shanmuka Nice ..and yeah ,easy to understand..


  • 0
    S

    @santoshgamini Thanks ;)


Log in to reply
 

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