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

First Missing Positive

Explore how to find the smallest missing positive integer in an unsorted array by applying cyclic sort principles. This lesson helps you understand problem constraints, develop an O(n) time complexity solution, and implement an in-place algorithm using constant space.

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. Rearrange 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 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
usercode > main.py
def smallest_missing_positive_integer(nums):



    # Replace this placeholder return statement with your code

    return -1
First Missing Positive