Search⌘ K
AI Features
Home
Courses
Coderust: Hacking the Coding Interview

First Missing Positive Integer

Understand how to solve the problem of finding the first missing positive integer in an unsorted array. Explore an efficient O(n) time and O(1) space solution using an index-as-key mapping technique. Learn to handle arrays by marking presence of elements within the array itself to quickly locate the missing positive integer.

We'll cover the following...

Statement

Given an unsorted integer array, nums, find the smallest positive integer that is missing from the array.

Implement a solution that takes O(n)O(n) time and constant space.

Examples

Let’s look at some arrays and the first missing positive integer in each:

Sample input

[1, 9, 14, 11, 7, 13]

Expected output

2

Try it yourself

#include <iostream>
#include <vector>
using namespace std;
int FirstMissingPositive(vector<int> nums) {
	// Write your code here
	return -1;
}

Solution

First, we check the base case. To verify that the first missing positive integer is not 1, we check for its presence in the array. We use the array below as an example. Since 1 exists in the array, it’s not our missing positive integer:

g array -1 2 0 37 4 1 3 -4 6 21

Our missing positive integer cannot be less than zero or greater than the length of array + 1. So, we need to clean up the input array.

To respect the ...