Beat 100% Fast Elegant Java Index-Based Solution with Explanation


  • 19
    M

    The basic idea is to traversal and try to move the current value to position whose index is exactly the value (swap them). Then travelsal again to find the first unusal value, which can not be corresponding to its index.

    public int firstMissingPositive(int[] nums) {
    
    	int i = 0, n = nums.length;
    	while (i < n) {
            // If the current value is in the range of (0,length) and it's not at its correct position, 
            // swap it to its correct position.
            // Else just continue;
    		if (nums[i] >= 0 && nums[i] < n && nums[nums[i]] != nums[i])
    			swap(nums, i, nums[i]);
    		else
    			i++;
    	}
    	int k = 1;
    
        // Check from k=1 to see whether each index and value can be corresponding.
    	while (k < n && nums[k] == k)
    		k++;
    
        // If it breaks because of empty array or reaching the end. K must be the first missing number.
    	if (n == 0 || k < n)
    		return k;
    	else   // If k is hiding at position 0, K+1 is the number. 
    		return nums[0] == k ? k + 1 : k;
    
    }
    
    private void swap(int[] nums, int i, int j) {
    	int temp = nums[i];
    	nums[i] = nums[j];
    	nums[j] = temp;
    }

  • -2
    R

    If the follow up is that please output the first two positive value, how to modify the code based on what you have done right now. This is a question of an interview for one company. Please help us think about it. Thanks


  • 3
    S

    @mo10
    Can you just give an example, when 'K' will be hiding in position 0. And the following 'else' part is invoked? Thanks!

    else   // If k is hiding at position 0, K+1 is the number. 
    		return nums[0] == k ? k + 1 : k;
    
    

    Edit: - I got it. It is either when array is [0], or [1].
    Thanks. Beautiful Solution.


  • 0
    I

    like 4,1,2,3, acturally I think nums index 0 stores value 1 is better.


  • 0
    E

    Why it's not nums[nums[i]-1] != nums[i-1]?
    This match your explanation better, doesn't it?


Log in to reply
 

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