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

First Missing Positive

Explore how to efficiently find the first missing positive integer from an unsorted array using a cyclic sort pattern. Understand how to design an O(n) time and O(1) space solution, improving your coding interview skills and problem-solving approach.

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.go in the following coding playground. We have provided useful code templates in the other files, that you may build on to solve this problem.

Go
usercode > main.go
package main



func smallestMissingPositiveInteger(nums []int) int {



  // Replace this placeholder return statement with your code

  return -1 

}
First Missing Positive