Simple Java Solution, O(N) time and O(1) space with Explanation


  • 1
    H

    The main idea is that put number n to the index of n - 1. e.g. if n == 5, then let nums[4] = 5. After the linear scan process, then scan the nums again and find the first element that nums[i] != i + 1, the first missing element is i + 1. Corner cases are handled in the code.

    public class Solution {
        public int firstMissingPositive(int[] nums) {
            if(nums.length == 0) return 1;
            int n = nums.length;
            int i = 0;
            while(i < nums.length){
                while(i < nums.length && nums[i] > 0 && nums[i] <= n && nums[i] != i + 1 && nums[nums[i] - 1] != nums[i]){
                    swap(nums, i, nums[i] - 1);
                }
                ++i;
            }
            for(i = 0;i < n;i++){
                if(nums[i] != i + 1)
                    return i + 1;
            }
            return n + 1;
            
        }
        private void swap(int[] nums, int a, int b){
            int tmp = nums[a];
            nums[a] = nums[b];
            nums[b] = tmp;
        }
    }

Log in to reply
 

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