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

First Missing Positive

Understand how to identify the smallest missing positive integer in an unsorted array by applying the cyclic sort pattern. Learn to develop an efficient algorithm with O(n) time and constant space usage, enhancing your problem-solving skills for coding interviews.

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

  • −231≤-2^{31} \leq nums[i] ≤231−1\leq 2^{31} - 1

Examples

Understand the problem

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Find the Smallest Missing Positive Number

1.

What is the output if the following array is given as input?

[7, 8, 9, 11, 12]

A.

1

B.

10

C.

13

D.

14

1 / 2

Figure it out!

We have a game for you to play: re-arrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Sequence - Vertical
Drag and drop the cards to re-arrange them in the correct sequence
1
2
3
4

Try it yourself

Implement your solution in the following coding playground:

Java
usercode > FirstMissing.java
import java.util.*;
public class FirstMissing{
   public static int firstMissingPositiveInteger(int[] nums) {
      // Replace this placeholder return statement with your code
      return -1;
   }
}
First Missing Positive