Java O(n) time O(1) space 3 simple steps


  • 0
    S
    class Solution {
        public int firstMissingPositive(int[] nums) {
            //special cases
            if(nums.length == 0) return 1;
            if(nums.length == 1) return nums[0] == 1 ? 2 : 1;
            
            //move all negative integers to left
            int curr = 0;
            for(int i=0; i<nums.length; i++) {
                if(nums[i] <= 0) {
                    swap(nums, i, curr);
                    nums[curr++] = 1;
                }
            }
            
            //mark indexes corresponding to positive integers negative
            for(int i=curr; i<nums.length; i++) {
                int num = Math.abs(nums[i]);
                if(num-1 < nums.length) if(nums[num-1] > 0) nums[num-1] = -nums[num-1];
            }
            
            //scan again to see first non negative index
            for(int i=0; i<nums.length; i++) {
                if(nums[i] > 0) return i+1;
            }
            return nums.length+1;
        }
        
        private void swap(int[] nums, int i, int j) {
            if(i == j) return;
            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.