Home First Missing Positive
Post
Cancel

LeetCode #41: First Missing Positive (C/C++).

hard

source: https://leetcode.com/problems/first-missing-positive/
C/C++ Solution to LeetCode problem 41. First Missing Positive.

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.

Examples


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

Solution


  • Because we are looking for a positive integer, we can “remove” all the negative numbers (We set them to 0).
  • If we have an array of size n with numbers from 2 to n+1 we know that the value missing is 1; if the array has all the values [1,n], then the first missing integer is n+1. So, we are looking for an integer in the range [1, n+1].
  • For each number, we verify if its absolute is a number in the range [1,n].
  • If so, we can verify the value present at the index that should be for that number if the array was sorted (with values from 1 to n).
    • If the value at that position is > 0, we mark them as negative.
    • If the value is 0 we set it to -(n+1).
  • Once completed, we iterate through the array, and the first element with value >0 that’s the missing integer (index+1).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
  int firstMissingPositive(vector<int>& nums) {
    int n=nums.size();
    
    for (int i=0;i<n;++i)
      if (nums[i]<0) nums[i] = 0;
        
    for (int i=0;i<n;++i){
      int absv = abs(nums[i]);
      if (absv >= 1 && absv <= n) {
        if (nums[absv-1] > 0)
          nums[absv-1] *= -1;
        else if (nums[absv-1] == 0)
          nums[absv-1] = -1*(n+1);
      }
    }
        
    for (int i=1;i<n+1;++i)
      if (nums[i-1]>=0) return i;
        
    return n+1;
  }
};
This post is licensed under CC BY 4.0 by the author.

Reverse Nodes in k-Group

Remove Duplicates from Sorted Array