First Missing Positive

Try to solve the First Missing Positive problem.

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 ≤103\leq 10^3

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

Examples#

Created with Fabric.js 3.6.6 3 1 2 4 5 Input Output Sample example 1

1 of 4

Created with Fabric.js 3.6.6 Input Output 3 4 -1 2 1 Sample example 2

2 of 4

Created with Fabric.js 3.6.6 Input Output 3 4 2 1 5 Sample example 3

3 of 4

Created with Fabric.js 3.6.6 Input Output 7 8 9 10 1 Sample example 4

4 of 4

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

Question 1 of 20 attempted

Figure it out!#

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

Drag and drop the cards to re-arrange them in the correct sequence

Iterate over all the elements in nums and swap them with their correct position until all elements are in their correct positions.

Iterate over nums again and check if each element is equal to its index plus 1.

If an element is not in the correct position, return the index plus 1, of the element that is out of order, as the smallest missing positive number.

If all elements are in order, return the length of the array plus 1 as the smallest missing positive integer.

Try it yourself#

Implement your solution in main.py in the following coding playground. We have provided useful code templates in the other files, that you may build on to solve this problem.

Python
main.py
cyclic_sort.py
Input #1
%0 node_01 1 node_11 2 node_21 3 node_31 5
Visualization for Input #1
First Missing Positive

Solution: Find the Corrupt Pair

Solution: First Missing Positive