Katkat
Back

Find Smallest Missing Positive Integer in O(n) Time

AppleData Scientist · Onsite
MediumData ScientistOnsiteCoding & Algorithms

Last updated

This question evaluates a candidate's skill in array algorithms and in-place algorithm design, emphasizing understanding of time and space complexity and handling edge cases when identifying the smallest missing positive integer.

Scenario

LeetCode-style algorithm phone interview

Question

Implement a function that returns the smallest missing positive integer in an unsorted integer array in O(n) time and O(

  1. space, then explain the complexity trade-offs.
Hints

Use index placement/cyclic sort to achieve constant extra space.