cswork / libraryOpen practice workspace

Coding questions · Apple

Find Smallest Missing Positive Integer in O(n) Time

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.

Find Smallest Missing Positive Integer in O(n) Time

Given an unsorted list of integers, return the smallest positive integer that does not appear in the list. Your algorithm must run in O(n) time and use O(1) extra space. You may modify the input list in place.

Constraints

  • 0 <= len(nums) <= 100000
  • -2147483648 <= nums[i] <= 2147483647
  • The solution must run in O(n) time.
  • The solution must use O(1) extra space, excluding the input array.

Examples

Example 1

Input: ([1, 2, 0],)
Output: 3

Explanation: The positive integers 1 and 2 are present, so the smallest missing positive integer is 3.

Example 2

Input: ([3, 4, -1, 1],)
Output: 2

Explanation: After ignoring non-positive values, 1 is present but 2 is missing.

Hints

  1. Only values in the range 1 to n can affect the answer, where n is the length of the array.
  2. Try placing each valid number x at index x - 1 using swaps, similar to cyclic sort.