To find the first missing positive integer in an unsorted integer array, you can use a clever approach that utilizes the properties of array indices. Here’s a concise implementation in C# along with an explanation:
C# Implementation
public class Solution {
public int FirstMissingPositive(int[] nums) {
int n = nums.Length;
// Step 1: Place each number in its right place, e.g., 1 at index 0, 2 at index 1, etc.
for (int i = 0; i < n; i++) {
while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
// Swap nums[i] with nums[nums[i] - 1]
int temp = nums[i];
nums[i] = nums[temp - 1];
nums[temp - 1] = temp;
}
}
// Step 2: Identify the first missing positive
for (int i = 0; i < n; i++) {
if (nums[i] != i + 1) {
return i + 1; // Missing positive is i + 1
}
}
// If all positions are filled correctly, return n + 1
return n + 1;
}
}
Explanation
-
Rearrangement Phase:
- The idea is to rearrange the array such that each positive integer
x
(where1 ≤ x ≤ n
) is placed at the indexx - 1
. - We loop through the array and, for each element
nums[i]
, we check if it is in the correct range (i.e.,> 0
and<= n
). If it is, and it is not already in the correct position, we swap it with the value at its target position. This continues until all possible swaps are made. - The inner
while
loop ensures that we keep swapping until the current number is either out of the valid range or already in its correct position.
- The idea is to rearrange the array such that each positive integer
-
Finding the Missing Positive:
- After rearranging, we perform a second pass through the array to find the first index
i
wherenums[i]
is not equal toi + 1
. - The first index where this condition is true indicates that the number
i + 1
is missing from the array. - If all indices are filled correctly, then the missing positive integer would be
n + 1
(since all numbers from1
ton
are present).
- After rearranging, we perform a second pass through the array to find the first index
Complexity
- Time Complexity: O(n), since we essentially make two passes over the array.
- Space Complexity: O(1), as we modify the array in place without using extra space.
This method is efficient and leverages the properties of indices and values effectively, making it a popular solution for the problem.