First Missing Positive - LeetCode Daily Challenge

Problem Statement

Given an unsorted integer array nums. Return the smallest positive integer that is not present in nums.

You must implement an algorithm that runs in O(n) time and uses O(1) auxiliary 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.

Try here before watching the video.

Video Solution

Java Code

class Solution {

    private void swap(int[] nums, int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }

    public int firstMissingPositive(int[] nums) {
        int i = 0;
        while(i < nums.length) {
            int index = nums[i] - 1;
            if(index >= 0 && index < nums.length && nums[index] != nums[i]) {
                swap(nums, index, i);
            } else {
                i += 1;
            }
        }
        for(i = 0; i < nums.length; i++) {
            if((i + 1) != nums[i]) {
                return i + 1;
            }
        }

        return nums.length + 1;
    }
}

C++ Code

class Solution {
public:

    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                swap(nums[nums[i] - 1], nums[i]);
            }
        }
        for (int i = 0; i < n; ++i) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return n + 1;
    }
};

Python Code

class Solution:
    def swap(self, nums, a, b):
        nums[a], nums[b] = nums[b], nums[a]

    def firstMissingPositive(self, nums):
        i = 0
        while i < len(nums):
            index = nums[i] - 1
            if 0 <= index < len(nums) and nums[index] != nums[i]:
                self.swap(nums, index, i)
            else:
                i += 1
        for i in range(len(nums)):
            if (i + 1) != nums[i]:
                return i + 1
        return len(nums) + 1

Javascript Code

var firstMissingPositive = function(nums) {
    const swap = (nums, a, b) => {
        [nums[a], nums[b]] = [nums[b], nums[a]];
    };

    let i = 0;
    while (i < nums.length) {
        const index = nums[i] - 1;
        if (index >= 0 && index < nums.length && nums[index] !== nums[i]) {
            swap(nums, index, i);
        } else {
            i += 1;
        }
    }
    for (i = 0; i < nums.length; i++) {
        if ((i + 1) !== nums[i]) {
            return i + 1;
        }
    }
    return nums.length + 1;
};

Go Code

func firstMissingPositive(nums []int) int {
    swap := func(nums []int, a, b int) {
        nums[a], nums[b] = nums[b], nums[a]
    }

    i := 0
    for i < len(nums) {
        index := nums[i] - 1
        if index >= 0 && index < len(nums) && nums[index] != nums[i] {
            swap(nums, index, i)
        } else {
            i++
        }
    }
    for i := 0; i < len(nums); i++ {
        if i+1 != nums[i] {
            return i + 1
        }
    }
    return len(nums) + 1
}

Complexity Analysis:

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