First Missing Positive Leetcode Solution

In this post, you will know how to solve the First Missing Positive Leetcode Solution of Leetcode. This Leetcode problem is done in many programming languages like C++, Java, and Python.

First Missing Positive Leetcode Solution
First Missing Positive Leetcode Solutions

One more thing to add, don’t directly look for the solutions, first try to solve the problems of Leetcode by yourself. If you find any difficulty after trying several times, then you can look for solutions.

Problem

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

First Missing Positive Leetcode Solutions in Python

class Solution:
  def firstMissingPositive(self, nums: List[int]) -> int:
    n = len(nums)
    # Correct slot:
    # nums[i] = i + 1
    # nums[i] - 1 = i
    # nums[nums[i] - 1] = nums[i]
    for i in range(n):
      while nums[i] > 0 and nums[i] <= n and nums[nums[i] - 1] != nums[i]:
        nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
    for i, num in enumerate(nums):
      if num != i + 1:
        return i + 1
    return n + 1

First Missing Positive Leetcode Solutions in CPP

class Solution {
 public:
  int firstMissingPositive(vector<int>& nums) {
    const int n = nums.size();
    // Correct slot:
    // nums[i] = i + 1
    // nums[i] - 1 = i
    // nums[nums[i] - 1] = nums[i]
    for (int i = 0; i < n; ++i)
      while (nums[i] > 0 && nums[i] <= n && nums[i] != nums[nums[i] - 1])
        swap(nums[i], nums[nums[i] - 1]);
    for (int i = 0; i < n; ++i)
      if (nums[i] != i + 1)
        return i + 1;
    return n + 1;
  }
};

First Missing Positive Leetcode Solutions in Java

class Solution {
  public int firstMissingPositive(int[] nums) {
    final int n = nums.length;
    // Correct slot:
    // nums[i] = i + 1
    // nums[i] - 1 = i
    // nums[nums[i] - 1] = nums[i]
    for (int i = 0; i < n; ++i)
      while (nums[i] > 0 && nums[i] <= n && nums[i] != nums[nums[i] - 1])
        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) {
    final int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
  }
}

Note: This problem First Missing Positive is is generated by Leetcode but the solution is provided by  BrokenProgrammers. This tutorial is only for Educational and Learning purposes.

Next: Search in Rotated Sorted Array Leetcode Solution

Leave a Reply

Your email address will not be published. Required fields are marked *