Java Solution with O(n) time and O(1) space complexity


  • 0
    M

    The key idea is to rearrange the array so that value will be stored in the (value-1)th slot for positive values.

    e.g. [1,2,3,4, ...]

    After you rearrange the array, you scan the array to find the first missing positive number.

    class Solution {
        public int firstMissingPositive(int[] nums) {
            for (int i = 0; i < nums.length; i++) {
                while (nums[i] != i+1 && nums[i] < nums.length && 0 < nums[i] && nums[i] != nums[nums[i]-1]) {    
                    int tmp = nums[nums[i]-1];
                    nums[nums[i]-1] = nums[i];
                    nums[i] = tmp;
                }
            }
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] != i+1) {
                    return i+1;
                }
            }
            return nums.length+1;
        }
    }
    

Log in to reply
 

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