First Missing Positive

LeetCode 41 | Difficulty: Hard

Hard

Problem Description

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

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

Example 1:

Input: nums = [1,2,0]
Output: 3
Explanation: The numbers in the range [1,2] are all in the array.

Example 2:

Input: nums = [3,4,-1,1]
Output: 2
Explanation: 1 is in the array but 2 is missing.

Example 3:

Input: nums = [7,8,9,11,12]
Output: 1
Explanation: The smallest positive integer 1 is missing.

Constraints:

- `1 <= nums.length <= 10^5`

- `-2^31 <= nums[i] <= 2^31 - 1`

Topics: Array, Hash Table

---

Approach

Hash Map

Use a hash map for O(1) average lookups. Store seen values, frequencies, or indices. The key question: what should I store as key, and what as value?

When to use

Need fast lookups, counting frequencies, finding complements/pairs.

---

Solutions

Solution 1: C# (Best: 378 ms)

Metric	Value
Runtime	378 ms
Memory	61.3 MB
Date	2021-11-28

Solution

public class Solution {
    public int FirstMissingPositive(int[] nums) {
            int n = nums.Length;
    for (int i = 0; i < nums.Length; i++)
    {
        if (nums[i] <= 0 || nums[i] > n)
        {
            nums[i] = n + 1;
        }
    }
    for (int i = 0; i < nums.Length; i++)
    {
        int value = Math.Abs(nums[i]);
        if (value > n) continue;
        value--;
        if (nums[value] > 0)
        {
            nums[value] = -1 * nums[value];
        }
    }
    for (int i = 0; i < nums.Length; i++)
    {
        if (nums[i] >= 0)
        {
            return i + 1;
        }
    }

    return n + 1;
    }
}

---

Complexity Analysis

Approach	Time	Space
Hash Map	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Break the problem into smaller subproblems. Communicate your approach before coding.
• Hash map gives O(1) lookup — think about what to use as key vs value.
• LeetCode provides 3 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: Think about how you would solve the problem in non-constant space. Can you apply that logic to the existing space?

Hint 2: We don't care about duplicates or non-positive integers

Hint 3: Remember that O(2n) = O(n)