Problem Description

Given an unsorted integer array nums. Return the smallest positive integer that is not present in nums.

You must implement an algorithm that runs in O(n) time and uses O(1) auxiliary space.****

Problem Link

Solution 1: Brute Force

we could use a map, array or sorting the original array to solve this issue, but apparently, it can’t meet the requirement of this issue. It requires O(n) time and O(1) auxiliary space.

Time Complexity: O(n)

Space Complexity: O(n)

Solution 2 : In-place Hashing

We can utilize nums itself to track which positive integers occur in the array since the range of numbers we have now is the same as the length of the array. We can use the index as a hash key for a positive number, and the sign of the element as a presence indicator. But we need to handle the element which less than 0 or larger than n.

Code

func firstMissingPositive(nums []int) int {
	n := len(nums)
	contains1 := false
	for i, v := range nums {
		if v == 1 {
			contains1 = true
		}
		if v <= 0 || v > n {
			nums[i] = 1
		}
	}
	if !contains1 {
		return 1
	}
	for i := 0; i < n; i++ {
		a := int(math.Abs(float64(nums[i])))
		if a == n {
			nums[0] = -int(math.Abs(float64(nums[0])))
		} else {
			nums[a] = -int(math.Abs(float64(nums[a])))
		}
	}
	for i := 1; i < n; i++ {
		if nums[i] > 0 {
			return i
		}
	}
	if nums[0] > 0 {
		return n
	}
	return n + 1
}

Time Complexity: O(n) Space Complexity: O(1)