Interview Questions — Find the First Missing Positive Integer

Photo by Tine Ivanič on Unsplash

Given an array, find the smallest missing positive integer in linear time and constant space with Javascript

Find the First Missing Positive

Challenge: Given an unsorted array of integers that may contain duplicates, negative numbers, and positive integers, efficiently determine the smallest missing positive integer in linear time (O(n)) using constant space (O(1)). You can modify the input array in place.

Example:

• Input: [2, 5, -2]
• Output: 1 (since 1 is the smallest missing positive integer)

Explanation:

1. Set for Tracking Seen Positives: We create a Set named seen to efficiently store and check for positive integers encountered in the array.
2. Iterating and Adding Positives: We loop through the array (arr). If the current element (arr[i]) is positive, we add it to the seen set. This allows us to keep track of all the positive numbers in the array.
3. Checking for Missing Positives: After processing the entire array, we iterate through a range from 1 to arr.length + 1. For each number (i) in this range:

• We check if the Set (seen) contains this number (i).
• If the Set does not contain i (meaning we haven't seen this positive number in the array), it signifies a missing positive integer.
• In that case, we immediately return i as the first missing positive integer.

Key Points:

• This approach focuses on directly tracking seen positive numbers using the Set.
• It avoids the index-based swapping technique.
• The loop from 1 to arr.length + 1 ensures we check for all potential missing positive integers within the relevant range.

This method effectively utilizes the Set for efficient lookups and avoids unnecessary modifications to the original array, achieving the desired time and space complexity.

Here’s the JavaScript code to find the first missing positive integer in linear time and constant space:

function findMissingPositive(arr) {
  const seen = new Set();
  
  // Loop through the array
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] > 0) {
      seen.add(arr[i]);
    }
  }
  
  // Check for missing positive integers from 1
  for (let i = 1; i <= arr.length + 1; i++) {
    if (!seen.has(i)) {
      return i;
    }
  }
}

// Example usage
const arr1 = [3, 4, -1, 1];
const arr2 = [1, 2, 0];
const arr3 = [2, 5, -2];
console.log(findMissingPositive(arr1)); // Output: 2
console.log(findMissingPositive(arr2)); // Output: 3
console.log(findMissingPositive(arr3)); // Output: 1

Follow me on Instagram, Facebook or Twitter if you like to keep posted about tutorials, tips and experiences from my side.

You can support me from Patreon, Github Sponsors, Ko-fi or Buy me a coffee