First Missing Positive - Practice Coding Problems

First Missing Positive - Problem

Given an unsorted integer array nums, return the smallest positive integer that is not present in nums.

Important: You must implement an algorithm that runs in O(n) time and uses O(1) auxiliary space.

The problem asks you to find the first missing positive number from 1, 2, 3, ... that doesn't exist in the array.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,2,0]

› Output: 3

💡 Note: The numbers 1 and 2 are present, but 3 is the first missing positive integer.

Example 2 — Negative and Large Numbers

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

› Output: 2

💡 Note: We have 1, 3, and 4, but 2 is missing. Negative numbers don't affect the result.

Example 3 — All Numbers Present

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

› Output: 1

💡 Note: The smallest positive integer 1 is not present in the array.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Array

Unsorted array with positive, negative, and zero values

Process

Identify which positive integers 1,2,3... are missing

Output

Return the smallest missing positive integer

Key Takeaway

🎯 Key Insight: Use the array itself as a hash table by placing number n at index n-1, then scan for the first gap

Asked in

A Amazon 45 M Microsoft 38 G Google 32 F Facebook 28

The key insight is to use the array itself as a hash table by placing each number n at index n-1. The optimal Cyclic Sort approach achieves O(n) time and O(1) space by rearranging elements in-place, then finding the first position where the expected value is missing.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Linear Search	O(n²)	O(1)	Check each positive integer 1, 2, 3... until we find one not in the array
Hash Set Lookup	O(n)	O(n)	Store all numbers in a hash set, then check candidates 1, 2, 3... for O(1) lookup
Cyclic Sort (In-Place)	O(n)	O(1)	Use the array itself as a hash table by placing each number at its correct index

Brute Force - Linear Search — Algorithm Steps

Start with candidate = 1
For each candidate, scan entire array to check if it exists
If not found, return candidate
If found, increment candidate and repeat

Visualization

Tap to expand

Step-by-Step Walkthrough

Check 1

Scan array for 1

Check 2

Scan array for 2

Found Missing

First number not in array

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int solution(int* nums, int numsSize) {
    int candidate = 1;
    while (true) {
        bool found = false;
        for (int i = 0; i < numsSize; i++) {
            if (nums[i] == candidate) {
                found = true;
                break;
            }
        }
        if (!found) {
            return candidate;
        }
        candidate++;
    }
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse JSON array
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(nums, numsSize);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of potentially n candidates, we scan the entire array of size n

⚠ Quadratic Growth

Space Complexity

O(1)

Only using a few variables, no extra data structures

✓ Linear Space

289.0K Views

High Frequency

~25 min Avg. Time

8.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Linear Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler