educative.io

Time complexity of finding first k missing positives

Courses
,
#1

“The optimal solution to this problem runs in O(n) time and takes O(n) space.”

From the constraints, it looks like k can exceed n. In this case, would our time complexity become a function of k? Should we adjust the optimal time complexity accordingly?

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

Hi @Isaac_Haseley,

You’re correct in stating that k can exceed n. Keeping this in check, an optimal solution to this problem can run in O(n + k) time. We’ll update the statements under the “Try it yourself” section. Thank you for taking time in reading our course and providing valuable feedback and suggestions.

Regards,
Dian Us Suqlain