Java O(n) solution with constant space utilization.


  • 0
    S
        public int firstMissingPositive(int[] nums) {
        if(nums == null || nums.length ==0)
            return 1;
        int last = Integer.MAX_VALUE;
        for(int i =0; i < nums.length; i++)
        {
            if(nums[i] < 1 || nums[i]== i)
                continue;
            if(nums[i] >= nums.length)
            {
                last = Math.min(last, nums[i]);
                continue;
            }
            int swap = nums[nums[i]];
            //handling duplicate values
            if(swap == nums[i])
            {
                nums[i]= -1;
                continue;
            }
            nums[nums[i]] = nums[i];
            nums[i] = swap;
            i--;
        }
        
        for(int i =1; i < nums.length; i++)
        {
            if(nums[i] != i)
                return i;
        }
        
        if(last != nums.length)
            return nums.length;
        else
            return last+1;
    }

  • 0
    S

    In worst case it will do O(2n) which is same as O(n).


Log in to reply
 

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