Problem

Problem ID: 41

Title: First Missing Positive

Difficulty: Hard

Description:

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

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

 

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 <= 5 * 105
• -231 <= nums[i] <= 231 - 1

Thoughts

This is an interesting problem that utilises discreet math.

Solution

General Idea

Key Observations:

• By pigeon hole principal, the answer must be 1 <= Ans <= N + 1. Each positive number is assigned the element num - 1. In the worst case scenario all elements in the vector are assigned a number and Ans = N+1 otherwise the answer is the first element that does not have a corresponding number.
• All non-positive numbers will not affect the answer and can be modified to any number that is non-positive or already in the set (can set as a flag).

Intuition: each valid number (1 <= num <= N) will be assigned to the element num - 1. For each element, if there is a corresponding number then the value is < 0. Finally iterate through all the elements, if any of the element is not < 0 then return the index as the answer.

Algorithm:

1. Sanitize non-positive number: set all non-positive number to 0 so that they would not falsely represent an element with corresponding number.
2. For each absolute value of the number that is valid (!= 0 && <= N), set the value to negative.
   • Absolute: the number could be negative when a separate number that corresponding to that element it is on is present
3. Iterate through all elements and find the first element that is negative. That index represent the answer.

Implementation

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        for (int& num : nums) {
            num = max(num, 0);
        }
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            int num = abs(nums[i]);
            if (num <= 0 || num > n) continue;
            if (nums[num - 1] == 0) {
                nums[num - 1] = -(n+1);
            } else {
                nums[num - 1] = -abs(nums[num - 1]);
            }
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] >= 0) return i + 1;
        }
        return n + 1;
    }
};