Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns in C#

Solution: First Missing Positive

Explore how to efficiently find the smallest missing positive integer in an unsorted array by using the cyclic sort technique. Learn to implement an algorithm that operates in linear time with constant space, by placing elements in their correct indexes and identifying the first mismatch to determine the missing number.

We'll cover the following...

Statement

Given an unsorted integer array, nums, return the smallest missing positive integer. Create an algorithm that runs with an O(n)O(n) time complexity and utilizes a constant amount of space.

Note: The smallest missing positive isn’t the first positive number that’s missing in the range of elements in the input, but the first positive number that’s missing if we start from 11.

Constraints:

  • 1≤1 \leq nums.length ≤105\leq 10^5 ...