What is the best approach to solve First Missing Positive?

The optimal approach for First Missing Positive is the "Optimal — Cyclic Sort (In-Place Hashing)" technique. It runs in O(n) time and uses O(1) space. Place each number n at index n-1 (if 1 ≤ n ≤ len). Then scan: the first index where nums[i] ≠ i+1 gives the answer. The array itself becomes the hash map.

What is the time complexity of First Missing Positive?

The optimal solution for First Missing Positive has a time complexity of O(n) and a space complexity of O(1), achieved using the Cyclic Sort pattern.

Is First Missing Positive a Hard LeetCode problem?

Yes, LeetCode #41 (First Missing Positive) is rated Hard. It uses the Cyclic Sort pattern and is commonly asked in interviews at Amazon, Google, Microsoft.

How to solve First Missing Positive in Python, Java, C++, and JavaScript?

LumiChats provides complete solutions for First Missing Positive in Python, Java, C++, and JavaScript, along with step-by-step visual animations and time/space complexity analysis. All solutions are free to view.

#41HardCyclic Sort

First Missing Positive

Use the array itself as a hash map — place each number at its correct index.

AmazonGoogleMicrosoftByteDance

Problem Statement

Given an unsorted integer array nums, return the smallest missing positive integer. You must implement an algorithm that runs in O(n) time and uses O(1) auxiliary space.

Examples

Example 1

Input:nums = [1,2,0]

Output:3

Example 2

Input:nums = [3,4,-1,1]

Output:2

Example 3

Input:nums = [7,8,9,11,12]

Output:1

Constraints

1 ≤ nums.length ≤ 10⁵
-2³¹ ≤ nums[i] ≤ 2³¹-1

Solutions

Hash Set

TimeO(n)SpaceO(n)

Add all numbers to a set. Starting from 1, find the first positive not in the set. O(n) time and space.

Visual Animation

def firstMissingPositive(nums: list[int]) -> int:
    seen = set(nums)
    i = 1
    while i in seen:
        i += 1
    return i

Related Concepts

Deepen your understanding with these related topics from our AI Glossary:

Machine Learning Browse all 190+ concepts →

Deepen your understanding

Want to master the core concepts?

Our free AI Glossary covers 190+ topics — from Cyclic Sort to Dynamic Programming, Machine Learning, SQL, and more. Structured learning tracks for every level.

Browse AI Glossary All Problems

39+

AI Models

₹69

Per day used

Languages

Stuck? Ask AI to explain it step by step.

Ask Claude, GPT-4o, or Gemini to debug your code, generate test cases, or walk through the intuition. 39+ models. Pay only on days you use it — no subscription required.

Free to start · No credit card required to explore

Get Started Free

Back to all problems