King Of Interviews

First Missing Positive: 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
Explanation: The numbers in the range [1,2] are all in the array.

Example 2:

Input: nums = [3,4,-1,1]
Output: 2
Explanation: 1 is in the array but 2 is missing.

Example 3:

Input: nums = [7,8,9,11,12]
Output: 1
Explanation: The smallest positive integer 1 is missing.

Constraints:

1 <= nums.length <= 10^5
-2^31 <= nums[i] <= 2^31 - 1

Try this Problem on your own or check similar problems:

Solution:

public int firstMissingPositive(int[] nums) {
    int n = nums.length, firstPositive = 0;
    for(int i = 0; i < n; ++i){
        if(nums[i] > 0){
            firstPositive = nums[i];
            break;
        }
    }

    if(firstPositive == 0) return 1;

    for(int i = 0; i < n; ++i){
        if(nums[i] <= 0) nums[i] = firstPositive;
    }
    for(int i = 0; i < n; ++i){
        if(Math.abs(nums[i]) - 1 < n && nums[Math.abs(nums[i]) - 1] > 0) nums[Math.abs(nums[i]) - 1] *= -1;
    }
    for(int i = 0; i < n; ++i){
        if(nums[i] > 0) return i + 1;
    }
    return n + 1;
}

Time/Space Complexity:

Time Complexity: O(n)
Space Complexity: O(1)

Explanation:

Yeah I know a lot of short for loops, so let’s break them down:

The input array has negative and positive numbers, so it’s hard to implement the trick where we make the number negative at certain index to mark that we found corresponding index + 1 element somewhere in the array, to cope with this we use the first loop to find the first positive, and then in the second loop we mark all the numbers which we aren’t interested in (nums[i] <= 0) with the first positive number we found. Note that if we didn’t find any, the first missing positive would be of course 1.
Then we iterate through array and mark the element (by making it negative) at the corresponding index for each of the found numbers (if we find for example 2 we will make the element at index 1 negative)
We loop over the modified array and search for the first element that’s non-negative (we haven’t found the number corresponding to the index anywhere in the array), and we return index + 1 as our first missing positive.

Another solution is to loop over elements and for elements of interest (only positive number) we would keep on swapping the elements until we find the right number to place at current index (e.g. 2 goes to index 1 and so on) or we go out of boundary of array or reach a negative number:

class Solution {
  public int firstMissingPositive(int[] nums) {
      int n = nums.length;
      for (int i = 0; i < n; i++) {
          while (nums[i] > 0 && nums[i] <= n && nums[nums[i]-1] != nums[i]) {
              swap(nums, i, nums[i] - 1);
          }
      }

      for(int i = 0; i < n; ++i) {
          if (nums[i] != i + 1) return i + 1;
      }
      return n + 1;
  }

  private void swap(int[] nums, int i, int j) {
      int tmp = nums[i];
      nums[i] = nums[j];
      nums[j] = tmp;
  }
}

To check if the number is already in the correct slot we use nums[nums[i]-1] != nums[i]. In both of our implementations we have a linear time complexity while maintaining constant space complexity.

First Missing Positive