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; } };