Finding the first k missing positives without cyclic sort

Courses
,
1

Can we solve this in optimal time and space without cyclic sort, in the stated optimal O(n) time and O(n) space? If so, it may help the course to swap in a problem that requires the pattern.

def first_k_missing_numbers(arr, k):
    nums = set(arr)
    result = []
    i = 1
    while len(result) < k:
        if i not in nums:
            result.append(i)
        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

1 Like
2

Hello @Isaac_Haseley,

You’re correct to say that the problem can be solved without using cyclic sort. However, it’s worth noting that cyclic sort relies on the fact that each element should ideally be at its correct index, so it can be used to find missing elements in an array by observing where elements deviate from their expected positions during the sorting process. Thus, making it a suitable approach for such problems. We really appreciate your suggestion and the code you’ve shared. Feel free to let me know if you’ve any other suggestions or feedback. Thanks!