41. First Missing Positive

First Missing Positive

Problem Description

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 <= 105
• -231 <= nums[i] <= 231 - 1

Approach) Iterative

The loop nums[i]puts nums[nums[i] - 1]there, the last nums[i] !== i + 1is wrong

That is, for example, [3, 4, -2, 1]=> [1, -2, 3, 4], that is, the lack of2

/**
 * @param {number[]} nums
 * @return {number}
 */
var firstMissingPositive = function(nums) {
    var len = nums.length;
    var tmp = 0;
    var i = 0;
    while (i < len) {
        tmp = nums[i];
        if (tmp > 0 && tmp !== i + 1 && tmp !== nums[tmp - 1]) swap(nums, i, tmp - 1);
        else i++;
    }
    for (var j = 0; j < len; j++) {
        if (nums[j] !== j + 1) return j + 1;
    }
    return len + 1;
};

var swap = function (arr, i, j) {
    var tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
};

Approach) Brute Force

var firstMissingPositive = function(nums) {
    for(let i=1;true;i++){
        if (!nums.includes(i)) {
            return i
        }
    }
};

Approach) Using Hash

/**
 * @param {number[]} nums
 * @return {number}
 */
var firstMissingPositive = function(nums) {
    // Using hash
    let hash = {}
    nums.forEach(num => {
        hash[num] = true
    })
    for (let i =1; i<nums.length+1; i++){
        if (!hash[i]) return i 
    }
    return nums.length+1;
};

Approach) Using Sorting

/**
 * @param {number[]} nums
 * @return {number}
 */
var firstMissingPositive = function(nums) {
    nums.sort((a, b) => a - b);
    for (let i = 1; i <= nums[nums.length - 1] + 1; ++i) {
        if (nums.indexOf(i) == -1) return i;
    }
    return 1;
};

Conclusion

That’s all folks! In this post, we solved LeetCode problem 41. First Missing Positive

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!