First Missing Positive in Array

Finding the first missing positive number in an array is a common question in coding interviews. The goal is to identify the smallest positive number that does not appear in the array. The challenge is to solve this efficiently without sorting the array or using extra space. This problem helps improve your skills in array manipulation and logical thinking. Want to learn how to solve it step by step? Let’s begin!

Steps to Solve First Missing Positive in Array

• Understand the Problem:
  • You need to find the smallest positive number that is missing from the array.
• Clean the Array:
  • Replace numbers that are negative or greater than the length of the array with a placeholder, like 0 or n+1.
• Mark Numbers in Place:
  • Use the array itself to mark the presence of numbers:
    • For every number, mark its corresponding index (e.g., for number 3, mark index 2) by making the value at that index negative.
• Find the Missing Positive:
  • Loop through the array. The first index with a positive value shows the missing number (index + 1).
• Handle Edge Cases:
  • If all numbers from 1 to n are present, the missing number will be n + 1.
  • Handle arrays with only negatives or zeros.
• Test Your Code:
  • Try examples like [3, 4, -1, 1] (output: 2) or [1, 2, 3] (output: 4).

The First Missing Positive problem is a common coding challenge where you need to find the smallest missing positive integer from an unsorted list of integers. This problem tests your ability to manipulate arrays and use optimal algorithms to solve problems efficiently.

Problem statement

Given an unsorted array of integers, find the smallest missing positive integer.

Example

1nums = [1, 2, 0]
2# Output: 3

Explanation: The smallest missing positive integer in the array is 3.

How to solve

To solve the First Missing Positive problem efficiently, we can use an algorithm with O(n) time complexity and O(1) space complexity (excluding the input array). The idea is to place each number in its corresponding index position (i.e., 1 should be at index 0, 2 should be at index 1, and so on). After this arrangement, the first index that does not match its value will give the smallest missing positive integer.

Pseudo code

Here is the pseudo code to solve the First Missing Positive problem:

• Iterate through the array.
• For each number, place it in its correct index position.
• Iterate through the array again to find the first incorrect position.
• Return the missing positive integer.

Full code in Python

Here's the complete Python code to solve the First Missing Positive problem:

1def firstMissingPositive(nums):
2    n = len(nums)
3    
4    # Place each number in its correct position
5    for i in range(n):
6        while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
7            nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
8    
9    # Find the first missing positive
10    for i in range(n):
11        if nums[i] != i + 1:
12            return i + 1
13    
14    return n + 1
15
16# Example usage
17print(firstMissingPositive([1, 2, 0]))  # Output: 3
18print(firstMissingPositive([3, 4, -1, 1]))  # Output: 2
19print(firstMissingPositive([7, 8, 9, 11, 12]))  # Output: 1

Time complexity

The time complexity of this solution is O(n), where n is the number of elements in the array. This is because each element is placed in its correct position at most once.