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

Solution: First Missing Positive

Understand how to solve the problem of finding the smallest missing positive integer in an unsorted array with a linear time, constant space solution. Explore the cyclic sort technique that places each number in its correct position to quickly detect the missing element. This lesson guides you through the algorithm, its optimizations, and complexities to help you master this common coding interview pattern.

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 ...