First Missing Positive - Leetcode Solution

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

Approach: The approach is to use the given array as a hash table to mark the presence of the elements from 1 to n. In the array, we ignore all the negative numbers, as they cannot be part of the answer, and any number greater than n can be replaced with n, as we are only interested in the first missing positive integer. We traverse the array, and for every number in the array, we mark its presence in the hash table, placed at nums[nums[i] - 1]. Finally, we traverse the hash table, and the first index i, that does not contain i+1, is the answer.

Algorithm:

1. Traverse the given array, and place all the positive numbers, less than or equal to the length of the array, in their correct position. For any number greater than the length of the array, replace it with n+1, as we are only interested in the first missing positive integer.
2. Now, traverse the array and mark the presence of the elements in the hash table, placed at nums[nums[i] - 1].
3. Finally, traverse the hash table, and the first index i, that does not contain i+1, is the answer.
4. If no element is missing, return n+1.

Dry Run: Let's dry run the first example [1,2,0], for better understanding of the algorithm.

1. We traverse the array, and place all the positive numbers, less than or equal to the length of the array, in their correct position. The array becomes [1,2,0].
2. Now, we traverse the array and mark the presence of the elements in the hash table, placed at nums[nums[i] - 1]. The hash table becomes [1,1,0].
3. Finally, we traverse the hash table, and the first index i, that does not contain i+1, is the answer. Here, the answer is 3.

Solution:

class Solution { public: int firstMissingPositive(vector<int>& nums) { int n = nums.size(); //Step 1 for(int i=0;i<n;i++){ if(nums[i]>0 && nums[i]<=n){ int pos = nums[i]-1; if(nums[pos]!=nums[i]){ swap(nums[pos],nums[i]); i--; } } } //Step 2 for(int i=0;i<n;i++){ if(nums[i]!=i+1){ return i+1; } } //Step 3 return n+1; } };

1