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
}