My 3ms Java solution


  • 0
    D
    import java.util.*;
    
    public class Solution {
        public int firstMissingPositive(int[] nums) {
            int n = nums.length;
            // 1 is the first positive integer not in an empty list
            if (n == 0)
                return 1;
            // We use a hash set to reduce the problem of determining if an integer is in nums to O(1) time
            HashSet<Integer> numsSet = new HashSet<Integer>();
            for (int i : nums) {
                numsSet.add(i);
            }
            
            // There can be no more than n integers in nums, so iterate through the first integers,
            // returning the first one not found in nums
            for (int potential = 1; potential <= n; potential++) {
                if (!numsSet.contains(potential))
                    return potential;
            }
            
            // The first n integers are in there, so n+1 must be the first missing positive integer
            return n+1;
        }
    }
    

Log in to reply
 

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