Leetcode-41 first missing positive number

 

Problem Statement

Given an unsorted integer array nums, return the smallest missing positive integer.

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

Follow-up: Can you implement an algorithm that runs in O(n) time and uses constant extra space?

🔗 LeetCode Problem Link

Approach and Intuition

1. Observation:

   • The smallest missing positive number will always lie between 1 and n+1 (where n is the size of the array).
   • Negative numbers and numbers greater than n are irrelevant.

2. Optimal Approach:

   • Use the input array itself to track which numbers exist, achieving O(1) space complexity.
   • Place each number in its "correct" position (e.g., 1 should be at index 0, 2 at index 1).

3. Steps:

• Iterate through the array and "swap" elements to their correct positions if possible.
• In a second pass, find the first index i where nums[i] != i + 1. The missing positive is i + 1.
• If all indices are correct, return n + 1.

Code Implementation

def firstMissingPositive(nums):
    n = len(nums)
    
    # Step 1: Place numbers in the correct position
    for i in range(n):
        while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
            nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
    
    # Step 2: Find the first missing positive
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1
    
    return n + 1

Time and Space Complexity

• Time Complexity: O(n)

• Each element is swapped at most once, resulting in linear time complexity.

• Space Complexity: O(1)

• The algorithm uses constant extra space.

Edge Cases

1. Array contains only negative numbers: nums = [-1, -2] → Output: 1.

1. Array is already in correct order: nums = [1, 2, 3] → Output: 4.

1. Array has duplicates: nums = [1, 1, 3] → Output: 2

Alternate Approach: Using an Unordered Map

Another way to solve this problem is by leveraging an unordered_map (or hash map) to track the presence of numbers. This approach is simple to implement but requires O(n) additional space, which doesn’t satisfy the problem's space constraint but is still useful for understanding the problem conceptually.

Steps:

1. Create an empty unordered_map to store the frequency of elements in the array.
2. Iterate through the array and populate the map with the numbers.
3. Check for the smallest missing positive integer by iterating from 1 to 2n (or until you find the missing integer).

Code Implementation

class Solution {

public:

    int firstMissingPositive(vector<int>& nums) {

        unordered_map<int, int> map; // Map to store the presence of numbers

        int n = nums.size();

        // Step 1: Populate the map with elements in the array

        for (int i = 0; i < n; i++) {

            map[nums[i]]++;

        }

        // Step 2: Check for the first missing positive integer

        for (int i = 1; i <= n + 1; i++) { // Iterate from 1 upwards

            if (map.find(i) == map.end()) { // If `i` is not found in the map

                return i;

            }

        }

        return 0; // This case won't be hit because a missing positive will always be found

    }

};

Time and Space Complexity

• Time Complexity: O(n)
  • Iterating through the array to populate the map takes O(n).
  • Checking for the missing positive integer also takes O(n).
  • Overall complexity is linear.
• Space Complexity: O(n)
  • The unordered_map requires additional space proportional to the size of the input array.

Resources

• 📝 Problem Link: First Missing Positive
• 💻 GitHub Repository for Code
• 🎥 Video Explanation on YouTube