FOR FREE MATERIALS

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

Input: [1, 2, 0]

O/P: 3

Input: [3, 4, -1, 1]

Output: 2

Example 3:

Input: [7, 8, 9, 11, 12]

Output: 1

Positive integer starts from 1, 2, 3, …………… ∞

Here in the question it is asked that return the smallest positive integer which is not present in the array.

Checkings

If the array is empty → smallest positive →1

Using the concept of dictionary (hashing), we will implement the logic.

Step 1: First check whether the array is empty if empty return 1

Step 2: Convert the array to a set uses the concept of dictionary

Step 3:

Step 4: Run a loop from1 to len(num) + 2

             Why len(num) + 2

            Suppose array has element that is 1 so we know the loop will upto len(num) + 2 – 1 i.e. len(num) + 1 to get the minimum                 first missing positive.

Step 5: Check whether the value present in the set if not return the value. Which in turn is the first missing positive.

             Example: [1, 2, 0] → set → [0, 1, 2]

            Loop pulls from (1 to 4)         / len(num) + 2

            1, 2, are present but 3 is not present

             So, 3 is the 1st missing positive integer