=============
== Lroolle ==
=============

0041. First Missing Positive

Hard Array Sort

Problem

Hard U:3696 D:813

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
Follow up:

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

Problem Insights

At first, we may came up with an idea to sort the array, then loop through to find the missing positive. However, as the NOTE mentioned, it’s obviously impossible to run in O(n) time and O(1) space if we’re going to sort the array. Because, for whom familiar with the sort algorithms, the best sort time at least take O(log n) time.

Other ideas may came up with HashTable etc…but also impossible to keep an O(1) space.

Let’s take a look at the example 2 [3,4,-1,1] and example 3 [7,8,9,11,12],

Imaging there are no missing positive, then example 2 should be [1, 2, 3, 4], and example 3 should be [1, 2, 3, 4, 5].

Considering the positives, in conclusion, for any nums with length nlen, the first missing positive must be within 1-nlen.

To find the missing positive, first of all we can ignore the 0 and non-positive values, then the values which are greater than nlen are also useless.

First idea, we may think about how to put the right number to the right index. which for example 2, if by some way to swap the items to array like this: [1, x, 3, 4] (ignore negative -1), then it’s not hard to iterate and find the missing positive is 2. (-> See Solution Ⅰ)

The second idea is, if we can use each index of numbers as a hash to record the “frequency” of each number, then by iterate the array, the zero frequency number is the missing one. (-> See Solution Ⅱ)

This idea comes from: @asones post

Solutions

Solution Ⅰ

func firstMissingPositive2(nums []int) int {
	for i := 0; i < len(nums); i++ {
		for nums[i] > 0 && nums[i] < len(nums) && nums[nums[i]-1] != nums[i] {
			nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]
		}
	}

	for i := 0; i < len(nums); i++ {
		if nums[i] != i+1 {
			return i + 1
		}
	}
	return len(nums) + 1
}

Solution Ⅱ

func firstMissingPositive3(nums []int) int {
	nums = append(nums, 0)
	nlen := len(nums)
	// Reset those useless elements
	for i, n := range nums {
		if n < 0 || n >= nlen {
			nums[i] = 0
		}
	}
	//
	for i := range nums {
		nums[nums[i]%nlen] += nlen
	}
	for i := 1; i < nlen; i++ {
		if nums[i]/nlen == 0 {
			return i
		}
	}
	return nlen
}