[Leetcode] First Missing Positive

Restore the array to a partially sorted state so the first element not consecutive with the previous suggests the missing value.

Description

Given an unsorted integer array nums, return the smallest missing positive integer.

You must implement an algorithm that runs in O(n) time and uses constant extra space.

Examples

Example 1:

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

Example 2:

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

Example 3:

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

Solution

A sorted array with positive ones would be [1, 2, 3, …..] where n is placed at index n-1. Swap elements to place nums[i] at index nums[i] - 1. What if the arr contains elements < 1 or > n-1 ? That doesn’t matter, we only care about placing eligible elements at the correct index. i.e. We partially sort the array in O(1). The first index without correctly placed elem implies the first missing positive.

#  3,  4, -1,  1 <->  1,  2,  3,  4
#  ^                  1, -1,  3,  4
#          ^
# -1,  4,  3,  1
#      ^
#              ^
# -1,  1,  3,  4
#      ^
#  ^
#  1, -1,  3,  4
#          ^
# 
#  1, -1,  3,  4
#              ^
# 

Eligible values v > 0 and v - 1 < n so v can be used as index to swap.

When iterating through index, the current round is only finished when the swapped one is no longer eligible to be an index to swap.

• code

ref: https://maxming0.github.io/2020/09/30/First-Missing-Positive/