41. First Missing Positive #

Problem #

Given an unsorted integer array, find the smallest missing positive integer.

Example 1:

Input: [1,2,0]  
Output: 3  

Example 2:

Input: [3,4,-1,1]  
Output: 2  

Example 3:

Input: [7,8,9,11,12]  
Output: 1  

Note:

Your algorithm should run in O(n) time and uses constant extra space.

Problem Summary #

Find the first missing positive integer.

Solution Approach #

To reduce time complexity, you can put all elements of the input array into a map, then loop i starting from 1, checking in order whether i exists in the map. As soon as i does not exist, immediately return the result, which is the answer.

Code #

package leetcode

func firstMissingPositive(nums []int) int {
	numMap := make(map[int]int, len(nums))
	for _, v := range nums {
		numMap[v] = v
	}
	for index := 1; index < len(nums)+1; index++ {
		if _, ok := numMap[index]; !ok {
			return index
		}
	}
	return len(nums) + 1
}