Java iterative O(n) time O(1) solution


  • 0
    B
    public int firstMissingPositive(int[] nums) {
        int len = nums.length;
        
        for (int i = 1; i <= len; i++) {
            int val = nums[i - 1];
            while (val <= len && val >= 1 && nums[val - 1] != val) {
                int newVal = nums[val - 1];
                nums[val - 1] = val;
                val = newVal;
            }
        }
        
        for (int i = 1; i <= len; i++) {
            if (nums[i - 1] != i) return i;
        }
        
        return len + 1;
    }

Log in to reply
 

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