Java solution O(1) O(n) with clear inline comment Explanation


  • 0
    A
    // O(2n) Two-pass
    public int firstMissingPositive(int[] nums) {
        if (nums.length == 0) { return 1; }
        
        for (int i = 0; i < nums.length; ) {
            int realIndex = nums[i]-1;
            
            // Not in its correct position and within bound,
            // put num into its correct position
            if (realIndex != i && 0 <= realIndex && realIndex < nums.length 
                && nums[realIndex] != nums[i]) {    // And not Duplicate
                    
                int tmp = nums[realIndex];
                nums[realIndex] = nums[i];
                nums[i] = tmp;
                
            } else {
                // Only keep on going if no swaps; 
                // Otherwise stay in place until newcomers are handled. Once max!
                i++;
            }
        }
        
        // First int != index, missing int
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != (i+1)) {
                return i+1;
            }
        }
        return nums.length + 1;     // All are in sequence, next biggest
    }

Log in to reply
 

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