LeetCode //C - 41. First Missing Positive

41. First Missing Positive

Given an unsorted integer array nums. Return the smallest positive integer that is not present in nums.

You must implement an algorithm that runs in O(n) time and uses O(1) auxiliary 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<=10^5$
• $-2^{31}<=nums[i]<=2^{31}-1$

From: LeetCode
Link: 41. First Missing Positive

---

Solution:

Ideas:

1. First, separate negative numbers and zeros from positive numbers because we’re only interested in the smallest positive missing integer. We can ignore numbers that are outside the range [1, numsSize] since the smallest missing positive integer must be within this range or just outside it (numsSize + 1).

2. Next, we iterate through the array, and for each positive integer nums[i] that is within the range [1, numsSize], we swap nums[i] with nums[nums[i] - 1] (the position it should be in). We repeat this process until all integers are in their correct positions or if swapping no longer changes the array.

3. Finally, we scan the array again. The first index i for which nums[i] != i + 1 indicates that i + 1 is the smallest missing positive integer. If all numbers are in their correct positions, the smallest missing positive integer is numsSize + 1.

Code:

int firstMissingPositive(int* nums, int numsSize) {
    for (int i = 0; i < numsSize; ++i) {
        while (nums[i] > 0 && nums[i] <= numsSize && nums[nums[i] - 1] != nums[i]) {
            // Swap nums[i] with nums[nums[i] - 1]
            int temp = nums[nums[i] - 1];
            nums[nums[i] - 1] = nums[i];
            nums[i] = temp;
        }
    }

    for (int i = 0; i < numsSize; ++i) {
        if (nums[i] != i + 1) {
            return i + 1; // Found the first missing positive
        }
    }

    return numsSize + 1; // All positive numbers [1, numsSize] are present
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18