41. First Missing Positive

Hello, reader 👋🏽 ! Welcome to day 31 of the series on Problem Solving. Through this series, I aim to pick up at least one question everyday and share my approach for solving it.

Today, I will be picking up LeetCode's daily challenge problem: 41. First Missing Positive.

🤔 Problem Statement

Given an unsorted integer array nums, return the smallest missing positive integer.

Note: The algorithm must run in constant space and linear time.

💬 Thought Process - Brute Force

We could use two loops, one that checks for all positive integers from 1 to n+1 and another inner loop which checks the existence of each of these in the array.
This is quite costly and takes O(n^2) in the worst case.
We can do better by saving all the values in a set.

💬 Thought Process - Hash Set (Enhanced Brute Force)

The approach uses a set to cache all the positive integers in the array.
Then we can iterate through numbers from 1 to n+1 to figure out which is the smallest positive integer.
This is pretty straightforward, and run in linear time as well. Let's look into the code now.

👩🏽‍💻 Solution - Hash Set (Enhanced Brute Force)

class Solution {
    public int firstMissingPositive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        int n = nums.length;
        for(int num: nums) {
            if(num > 0) {
                set.add(num);
            }
        }

        int i = 1;
        for(; i<=n+1; i++) {
            if(!set.contains(i)) break;
        }

        return i;
    }
}

Time Complexity: O(n)
    - n = number of elements in the array
Space Complexity: O(n) 
    - n = number of elements in the array

💬 Thought Process - Count Sort

We can do much better and use the fact that we care about only the positive integers in the array.
We can try sorting in place such that if a number num, is greater than 0, num > 0, then it should be placed at index num-1.
That means we place number 1 at index 0, 2 at 1, 3 at 2 and so on.
If we encounter any negative numbers or numbers greater than the length of array, we simply ignore them.
This will help us to look for the first mismatch such that nums[i] != i+1.
Let's walk through an example: nums = [3,5,0,-1,1]. After applying count sort all the elements that are in the range: 1 <= num <= n will be in their correct indices.
The mismatches will occupy the places of the missing numbers. So it would be like this: [1, 0, 3, -1, 5].
Now the first mismatch is at index 1, where i+1 != 2. So we return 2 as the answer.
The corner case is when none of the indices have a mismatch. For e.g. [1,2,3]. In such cases we return n+1 = 4 as that's the first missing positive integer.
Another corner case is to handle duplicates. We need to ignore duplicate values as well. Hence, instead of checking if num != i+1, we will check if the position at num-1 is already occupied by num or not. If it was, then we ignore this number and the index as well.
Let's look into the code now.

👩🏽‍💻 Solution - Count Sort

class Solution {
    public int firstMissingPositive(int[] nums) {
        if(nums == null || nums.length == 0) return 0;

        int n = nums.length;
        int i = 0;
        while(i < n) {
            int num = nums[i];
            // Ignore negative numbers, zero, numbers > n+1 and duplicates
            if(num <= 0 || num > n || nums[num-1] == num) {
                i++;
                continue;
            } 
            int newIndex = num-1;
            int temp = nums[newIndex];
            nums[newIndex] = num;
            nums[i] = temp;
        }

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

        return n+1;
    }
}

Time Complexity: O(n)
    - n = number of elements in the array
Space Complexity: O(1)

You can find the code for this question in the GitHub repo here: 41. First Missing Positive.

Conclusion

That's a wrap for today's problem. If you liked my explanation then please do drop a like/ comment. Also, please correct me if I've made any mistakes or if you want me to improve something!

Thank you for reading!