“The optimal solution to this problem runs in O(n) time and takes O(n) space.”
Can we get space down to O(1)?
def first_k_missing_numbers(arr, k):
n = len(arr)
i = 0
while i < n:
correct_spot = arr[i] - 1
if arr[i] < 1 or arr[i] > n or i == correct_spot or arr[i] == arr[correct_spot]:
i += 1
else:
arr[i], arr[correct_spot] = arr[correct_spot], arr[i]
result = []
i = 0
while len(result) < k:
if i < n:
if arr[i] != i + 1:
result.append(i + 1)
else:
result.append(i + 1)
i += 1
return result
Course: Grokking Coding Interview Patterns in Python - Learn Interactively
Lesson: Find the First K Missing Positive Numbers - Grokking Coding Interview Patterns in Python