Check this out. Little more time but a simple logic :-)


  • -1
    D

    //The number cannot be something greater than nums.length + 2 - (no. of -ve and zeroes)
    //Why this is true?
    //because even if all the numbers are >0 an array of size x can hold x elements at maximum.
    //If all the elements from 1 to x are present then x+1 must be the missing element. Any number >=2 cannot be a candidate.
    //Therefore, we can safely take the size of the tracker array to be nums.length + 1

    public class Solution {
    public int firstMissingPositive(int[] nums){

        boolean[] tracker = new boolean[nums.length+1];
        for(int i=0;i<nums.length;i++){
            if(nums[i]>0 && nums[i]<=nums.length+1){
               tracker[nums[i]-1] = true;
            }
        }
        for(int i=0;i<tracker.length;i++){
            if(!tracker[i]){
                return i+1;
            }
        }
        return 0;
    }
    

    }


  • 0
    D

    @StefanPochmann : When you are giving anybody a down vote, you should also let him know where is the error. The code which I have given, passes all the test cases and takes 11 ms only.
    I hope you will explain what is the reason of the Down Vote. If you have nothing to to say, then it is unethical.


  • 0

    @dparthade-gmail.com Sure I have something to say, I just didn't say it. Takes extra time. And if it's as obvious as in this case, I don't think it's necessary. Pointing out that there's something bad should be helpful enough then.

    But ok... the problem says you should use constant space, and you don't. You use linear space. So that's not ok. This is not a valid solution. At least not without mentioning the issue.

    The poor formatting might've been a small additional reason, don't remember.


Log in to reply
 

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