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

First Missing Positive

Understand how to efficiently identify the first missing positive integer in an unsorted array by applying cyclic sort. This lesson helps you create an O(n) time and O(1) space algorithm that addresses problem constraints and edge cases. Practice implementing this solution to improve your problem-solving skills for technical 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 main.js in the following coding playground. We have provided useful code templates in the other files, that you may build on to solve this problem.

JavaScript
usercode > main.js
import {cyclicSort} from './cyclic_sort.js'



export function smallestMissingPositiveInteger(nums){



    // Replace this placeholder return statement with your code

    return -1

}
First Missing Positive