First Missing Positive Problem


Description

LeetCode Problem 41.

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:

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

Example 2:

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

Example 3:

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

Constraints:

  • 1 <= nums.length <= 5 * 10^5
  • -2^31 <= nums[i] <= 2^31 - 1


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int len = nums.size();
        
        for (int i = 0; i < len; i ++) {
            if (nums[i] < 0 || nums[i] > len || nums[i] == i+1) 
                continue;
            int nxt = nums[i] - 1;
            while (nxt >= 0 && nxt < len && nums[nxt] != nxt+1) {
                int nxt_nxt = nums[nxt] - 1;
                nums[nxt] = nxt + 1;
                nxt = nxt_nxt;
            }
        }
        
        for (int i = 0; i < len; i ++) {
            if (nums[i] != i + 1)
                return i + 1;
        }
        return len + 1;
    }
};




Related Posts

X Of A Kind In A Deck Of Cards Problem

LeetCode 914. In a deck of cards, each card has...

Word Subsets Problem

LeetCode 916. You are given two string arrays words1 and...

Unique Morse Code Words Problem

LeetCode 804. International Morse Code defines a standard encoding where...

Unique Email Addresses Problem

LeetCode 929. Every valid email consists of a local name...

Uncommon Words From Two Sentences Problem

LeetCode 884. A sentence is a string of single-space separated...

Triples With Bitwise And Equal To Zero Problem

LeetCode 982. Given an integer array nums, return the number...