How do you solve First Missing Positive on LeetCode?

First Missing Positive (LeetCode #41) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: We only care about positive integers, which simplifies our checks.

What is the brute force solution for First Missing Positive?

The brute force approach for First Missing Positive is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach checks each positive integer starting from 1 to see if it exists in the array. If it doesn't, that's our answer. It's straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve First Missing Positive?

First Missing Positive uses the following concepts: Array, Hash Table. The recommended patterns to study are: Array, In-place rearrangement.

What are the interview tips for First Missing Positive?

Always clarify the constraints and edge cases before diving into coding. Think about how you can use the existing array to store information instead of using extra space. Practice explaining your thought process as you code, as communication is key in interviews.

What are common mistakes when solving First Missing Positive?

Not handling negative numbers or zeros properly. Overlooking the need to rearrange the array in place.

#41

First Missing Positive

Hard

ArrayHash TableArrayIn-place rearrangement

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal solution uses the input array itself to track which positive integers are present. By rearranging the elements, we can find the first missing positive integer in linear time and constant space.

⚙️

Algorithm

4 steps

1Step 1: Iterate through the array and for each number, if it's in the range [1, n] (where n is the length of the array), place it in its correct position (i.e., nums[i] should be at index nums[i]-1).
2Step 2: After rearranging, iterate through the array again and check for the first index where the value is not equal to index + 1.
3Step 3: The first index that doesn't match gives us the missing positive integer, which is index + 1.
4Step 4: If all indices match, return n + 1.

solution.py9 lines

1def firstMissingPositive(nums):
2    n = len(nums)
3    for i in range(n):
4        while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
5            nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
6    for i in range(n):
7        if nums[i] != i + 1:
8            return i + 1
9    return n + 1

ℹ

Complexity note: The time complexity is O(n) because we make a constant number of passes through the array. The space complexity is O(1) since we are not using any additional data structures.

1We only care about positive integers, which simplifies our checks.
2The range of possible missing integers is limited to [1, n + 1], where n is the length of the array.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.