Easy understand java solution. O(1) space, and O(n) time


  • 0
    C
    public int firstMissingPositive(int[] nums) {
            int len = nums.length;
            //token should be less then 0 or greater then len
            int token = len + 1;
    
            //clean all token equal elements
            for(int i=0; i<len; ++i) {
                if(nums[i] == token) nums[i] = -1;
            }
    
            //circulate marking element. 
            //nums[i] == token after modified means Integer i+1 exists
            for(int i=0; i<len; ++i) {
                if (nums[i] > 0 && nums[i] < len + 1) {
                    int next = nums[i] - 1;
                    while (next >= 0 && next < len && nums[next] != token) {
                        int t = nums[next] -1;
                        nums[next] = token;
                        next = t;
                    }
                }
    
            }
    
            //check first missing element
            int i=0;
            for(; i<len; ++i) {
                if(nums[i] != token) break;
            }
            return i+1;
        }
    

Log in to reply
 

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