41. First Missing Positive
First Missing Positive (LeetCode 41) is a Hard Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Array/Matrix Manipulation Patterns pattern, in the Array - Cyclic Sort subpattern.
How to solve First Missing Positive
First Missing Positive is a Cyclic Sort Algorithm problem, part of Array/Matrix Manipulation Patterns. Master cyclic sort pattern to find missing, duplicate, or misplaced numbers in arrays with O(n) time and O(1) space.
Work towards the solution in these steps:
- Think about how you would solve the problem in non-constant space. Can you apply that logic to the existing space?
- We don't care about duplicates or non-positive integers
- Remember that O(2n) = O(n)
The reference solution runs in O(n) time and O(1) space.
The First Missing Positive solution and editorial walks through the full approach with reference code.
Problem statement
Given an unsorted integer array nums. Return the smallest positive integer that is not present in nums.
You must implement an algorithm that runs in O(n) time and uses O(1) auxiliary space.
Example 1:
Input: nums = [1,2,0] Output: 3 Explanation: The numbers in the range [1,2] are all in the array.
Example 2:
Input: nums = [3,4,-1,1] Output: 2 Explanation: 1 is in the array but 2 is missing.
Example 3:
Input: nums = [7,8,9,11,12] Output: 1 Explanation: The smallest positive integer 1 is missing.
Constraints:
- 1 <= nums.length <= 10^5
- -2^31 <= nums[i] <= 2^31 - 1
Topics and companies
Topics: Array, Hash Table.
Reported in interviews at Microsoft, Amazon, Facebook, Google, Oracle, Adobe, Bloomberg, Wish, Uber, Apple, Walmart Labs, Tesla and others.
How to practise First Missing Positive on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(1) space.
Open First Missing Positive in the code editor, or read the First Missing Positive editorial for a worked solution with its approach and complexity analysis.
Where First Missing Positive sits in the DSA pattern sheet
- Array/Matrix Manipulation Patterns pattern guide
- Array - Cyclic Sort subpattern
- The full DSA patterns sheet
Problems related to First Missing Positive
Other problems that use the same Array - Cyclic Sort and Array/Matrix Manipulation Patterns techniques:
- Find All Duplicates in an Array — Medium, same subpattern
- Find All Numbers Disappeared in an Array — Easy, same subpattern
- Add Binary — Easy, same pattern
- Add to Array-Form of Integer — Easy, same pattern
- Concatenation of Array — Easy, same pattern
- Contains Duplicate — Easy, same pattern
First Missing Positive FAQ
What is the LeetCode number of First Missing Positive?
First Missing Positive is LeetCode problem 41, rated Hard.
What pattern is used to solve First Missing Positive?
First Missing Positive is a Cyclic Sort Algorithm problem. It belongs to the Array/Matrix Manipulation Patterns pattern, in the Array - Cyclic Sort subpattern.
What is the time complexity of First Missing Positive?
The reference solution runs in O(n) time and O(1) space.
Which companies ask First Missing Positive?
First Missing Positive has been reported in interviews at Microsoft, Amazon, Facebook, Google, Oracle, Adobe, Bloomberg, Wish, Uber, Apple, Walmart Labs, Tesla and others.