Simple Accepted O(n) Java Solution - Only two boundary conditions are extra


  • 0
    B
    • list itemOnly two counters, lindex tracking 0's and hindex tracking 2's.
    • Important boundary conditions are i <= hindex and lindex !=i. I figured them using brute force testing and not intuitively.
    • I increments, only when the current number is 1. If its 0, we move it to left, and if its 2, we move it to right.
      Hope this is simple enough and helps people to understand.
    public class Solution {
        public void sortColors(int[] nums){
            int lindex = 0;
            int hindex = nums.length - 1;
            for(int i=0;i<nums.length && i <= hindex ;i++)
            {
                if(nums[i] == 0 && lindex != i){
                    swap(nums,i,lindex);
                    lindex++;
                    i--;
                }
                else if(nums[i] == 2){
                    swap(nums,i,hindex);
                    hindex--;
                    i--;
                }
            }
        }
        public void swap(int[] nums, int i, int j){
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }
    

Log in to reply
 

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