First Missing Positive number in an Array

HARD

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

Example 1:

 Input: [1,2,0]
 Output: 3

Example 2:

 Input: [1,4,5,6,4,2]
 Output: 3

Note: Your algorithm should run in O(n) time and uses constant extra space.

Data clean Up: 

As we are searching for the first missing positive number in the array so, let’s get rid of all negative numbers and zeros. We will also get rid of all numbers larger than n as well since the first missing positive is for sure smaller or equal to n+1. The case when the first missing positive is equal to n+1 will be treated separately. 

Note: n is the length of the input array.

To get rid of these numbers in O(N) time complexity we need to replace these numbers by 1s. But in that case, to ensure that the first missing positive is not 1, we need to verify the presence of 1 before proceeding with this operation.

How To Solve In Place:

Now there we have an array which contains only positive numbers in a range from 1 to n, and the problem is to find a first missing positive in O(N) time and constant space. That would be simple if one would be allowed to have a hash-map positive number -> its presence for the array. The idea is to use the index in the array as a hash key and sign of the element as a hash value which is a presence detector. Consider the input array is nums where we searching for the first missing positive number. For example, a negative sign of nums[2] element means that the number 2 is present in nums. The positive sign of nums[3] element means that number 3 is not present (missing) in nums. To achieve that let’s walk along with the array (which after clean up contains only positive numbers), check each element value elem and change the sign of element nums[elem] to negative to mark that number elem is present in nums. Be careful with duplicates and ensure that the sign was changed only once.

Algorithm:

Now everything is ready to write down the algorithm.

  • Check if 1 is present in the array. If 1 is missing from the array, then 1 is the first missing positive number.
  • If 1 is present in the array and the array is of length 1, then 2 is the first missing positive number.
  • Now replace negative numbers, zeros, and numbers larger than n by 1s.
  • Walk along with the array. Change the sign of ath element if you meet a number a. Be careful with duplicates: do sign change only once. Use index 0 to save information about the presence of a number n since index n is not available.
  • Walk again along with the array. Return the index of the first positive element.
  • If nums[0] > 0 return n.
  • If in all the previous step you didn’t find the positive element in nums, that means that the answer is n+1.
public int firstMissingPositive(int[] nums) {
 
     // Base case.
     if (nums == null || nums.length == 0) return 1;
     int n = nums.length;
     boolean isOnePresent = false;
     for (int i = 0; i < n; i++) {
         if (nums[i] == 1) {
             isOnePresent = true;
             break;
         }
     }
 
     if (!isOnePresent) return 1;
     // nums length is 1
     if (n == 1) return 2;
 
     // Replace negative numbers, zeros,
     // and numbers larger than n by 1s.
     // After this conversion nums will contain 
     // only positive numbers.
     for (int i = 0; i < n; i++) {
         if (nums[i] <= 0 || nums[i] > n) {
             nums[i] = 1;
         }
     }
 
     // Use index as a hash key and number sign as a presence detector.
     // For example, if nums[1] is negative that means that number `1`
     // is present in the array.If nums[2] is positive - number 2 is missing.
     for (int i = 0; i < n; i++) {
         int a = Math.abs(nums[i]);
         // If you meet number a in the array - change the sign of a-th element.
         // Be careful with duplicates : do it only once.
         if (a == n) {
             nums[0] = -Math.abs(nums[0]);
         } else {
             nums[a] = -Math.abs(nums[a]);
         }
     }
 
     // Now the index of the first positive number 
     // is equal to first missing positive.
     for (int i = 1; i < n; i++) {
         if (nums[i] > 0) {
             return i;
         }
     }
 
     if (nums[0] > 0) return n;
     return n + 1;
 }

Complexity Analysis:

  • Time Complexity: O(N) since all, we do here is four walks along with the array of length N.
  • Space Complexity: O(1) since this is a constant space solution.

Categories: Array

1 reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s