Java 11ms Solution


  • 0
    N

    The idea is to iterate through the given array and bring all the positive integers towards the front of the array. Then iterate on the positive integers and manipulate their respective value locations to negative. Then iterate through the modified array to encounter the first non negative element.

    This solution takes O(n) asymptotic time complexity and no extra space.

    public class Solution {
        public int firstMissingPositive(int[] nums) {
            if(nums.length == 0)
                return 1;
    
            int j = 0;
            for(int i = 0; i < nums.length; i++){
                if(nums[i] > 0)
                    nums[j++] = nums[i];
            }
            
            for(int i = 0; i < j; i++){
                if(Math.abs(nums[i]) <= j && Math.abs(nums[i]) > 0){
                    nums[Math.abs(nums[i]) - 1] = Math.abs(nums[Math.abs(nums[i])  - 1]) * (-1);
                }
            }
            
            int k = 0;
            while(nums[k] < 0){
                k++;
                if(k >= j)
                    break;
            }
            return k+1;
        }
    }
    

Log in to reply
 

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