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

First Missing Positive

Explore how to identify the smallest missing positive integer in an unsorted array efficiently. This lesson teaches you to implement an O(n) time and constant space algorithm using cyclic sort to solve missing integer problems, improving your problem-solving skills in 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:

C++
usercode > main.cpp
#include <iostream>

#include <vector>



int SmallestMissingPositiveInteger(vector<int> nums)

{

    // Replace this placeholder return statement with your code

    return -1;

}
First Missing Positive