41. First Missing Positive

Problem Statement

link: https://leetcode.com/problems/first-missing-positive/ https://leetcode.cn/problems/first-missing-positive/

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 O(1) auxiliary space.

Example:

Input: [1,2,0] Output: 3

Input: [3,4,-1,1] Output: 2

Input: [7,8,9,11,12] Output: 1

Solution Approach

The solution leverages the fact that the smallest missing positive integer will be in the range 1, n + 1, where n is the size of the array.

Algorithm

1. Pre-processing: First, replace all non-positive values and numbers greater than n with a dummy value (n+1).
2. Place-Marking: For each number i in the modified list, if it is between 1 to n, we mark its presence by setting the value at index i-1 as negative. This effectively maps the value with its respective index.
3. Search for Missing Value: Traverse the modified list, and the first index with a positive value will indicate the first missing positive integer, which is index + 1.

This approach ensures an O(n) runtime and utilizes the given space effectively without the need for extra space.

Implement

    class Solution:
      def firstMissingPositive(self, nums: List[int]) -> int:
          n = len(nums)
          for i in range(n):
              if nums[i] <= 0:
                  nums[i] = n + 1
          for i in range(n):
              num = abs(nums[i])
              if num <= n:
                  nums[num - 1] = -abs(nums[num - 1])
          
          for i in range(n):
              if nums[i] > 0:
                  return i + 1
          
          return n + 1

    
    

Twitter  facebook  Email