First missing positive
Find the first missing positive integer in an array in O(array_length) time from LeetCode
Sat Mar 14 2020
Given an array full of integers, find the first missing positive integer in the list. This tutorial goes over how you can do this in O(n) without using any additional space for hashtables or anything. This is avaliable for practice on LeetCode.
Example lists
Example of missing 5
1,2,3,4,6Example of missing 1
-1,4,8,6,2Algorithm
If the array has 4 elements and we are looking for the first missing positive. We can look at it this way, we expect 1,2,3,4 to be there.
| index | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| expected values | 1 | 2 | 3 | 4 |
| actual values | -1 | 8 | 6 | 1 |
| values after algorithm | 1 | 0 | 0 | 0 |
You’ll have to scan the entire list once to find out that 1 is not missing of course and that 2 is the first missing positive.
-
Iterate the array once - O(n)
- Get the value of the slot and
-1from this value, so that it is in the same zero-index range as the slots - Throw away any value you encounter outside of the range of the indexes of the array
0 between len(array)-1 - If the value you find is the same as the expected value for the slot overwrite the slot value with
1to denote the value exists - If you find a value that is less than the index, set the index of that slot to
1and the current slot value to0 - If you find a value that is greater than the current index, then swap the value in the current slot with the value in the expected future slot as it will be evaluated later anyway. Repeat this iteration once without progressing to the next slot so that you can evaluate the new value in this slot.
- Get the value of the slot and
In the end, you’ll have an array of zeros and ones. Where 1 denotes the existence of the value and 0 means the value does not exist. The first occurrence of zero is your first positive missing value.
Python Code
This Python code passes all tests in Leetcode
"""
https://leetcode.com/problems/first-missing-positive/
"""
class Solution:
""" Wrapper for LeetCode solution """
def firstMissingPositive(self, nums: list) -> int:
"""
Finds the first MISSING positive value in an array
"""
# Simplify the problem so that the array is just full of 0 or 1
# Where 1 indicates the presence of the value
self._update_arr_to_just_flags(nums=nums)
# The first occurrence of 0 is the first missing value
try:
first_missing_positive_integer = nums.index(0) + 1
except ValueError:
first_missing_positive_integer = len(nums)+1
print(nums)
print(first_missing_positive_integer)
return first_missing_positive_integer
@classmethod
def _update_arr_to_just_flags(cls, nums: list):
"""
Updates an entire array so that instead of storing values it stores either 0 or 1
1 indicates the presence of a value, the index indicates the value
"""
last_index = len(nums)-1
i = 0
while i <= last_index:
print(f"\nRunning iteration index {i}")
print(f"Current state of array {nums}")
current_value_target_index = nums[i] - 1
target_index_out_of_bounds = (current_value_target_index < 0 or
current_value_target_index > last_index)
if target_index_out_of_bounds:
print(f"threw away value at {i} aka {nums[i]} as it was outside the range")
nums[i] = 0
elif current_value_target_index < i:
print((f"already visited value {current_value_target_index}"
"aka {nums[current_value_target_index]}"))
nums[current_value_target_index] = 1
nums[i] = 0
elif current_value_target_index == i:
nums[current_value_target_index] = 1
elif current_value_target_index > i:
# the value is ahead and has not been considered yet
# swap it with current and re-evaluate current
are_same = nums[current_value_target_index] == nums[i]
if not are_same:
cls._arr_swap(nums, current_value_target_index, i)
continue
# The current value will be evaluated later
nums[i] = 0
i += 1
@classmethod
def _arr_swap(cls, nums: list, i: int, j: int):
temp = nums[i]
nums[i] = nums[j]
nums[j] = temp
print(f"swapped slots {i} with {j} aka {nums[i]} with {nums[j]}")
Sample run code for experimentation and debugging
def main():
""" The entry point of the Python script """
sln = Solution()
sln.firstMissingPositive([2, 2])
if __name__ == "__main__":
main()