Sponsored
Sponsored
This approach utilizes the cyclic sort algorithm to place numbers in their corresponding indices. For example, 1 should be at index 0, 2 should be at index 1, etc. While rearranging, we ignore numbers outside the range [1, n], where n is the length of the array.
After rearranging, the first index i that doesn’t have a number i+1 indicates the smallest missing positive integer.
Time Complexity: O(n), as each number is swapped at most once.
Space Complexity: O(1), as no additional space is used apart from variables.
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6int firstMissingPositive(vector<int>& nums) {
7 int n = nums.size();
8 for (int i = 0; i < n; ++i) {
9 while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
10 swap(nums[i], nums[nums[i] - 1]);
11 }
12 }
13 for (int i = 0; i < n; ++i) {
14 if (nums[i] != i + 1) {
15 return i + 1;
16 }
17 }
18 return n + 1;
19}
20
21int main() {
22 vector<int> nums = {3, 4, -1, 1};
23 cout << "The first missing positive is " << firstMissingPositive(nums) << endl;
24 return 0;
25}Similar to the C solution, the algorithm rearranges numbers within the range in-place and identifies the first non-matching index.
By assuming the input array itself can act like a hash map, this approach assigns each index with a corresponding positive value within the range. If out of range, we fill that index with a placeholder number like the array size + 1.
We then use index signs to mark present numbers and deduce the missing positive from the invalid marked position.
Time Complexity: O(n)
Space Complexity: O(1)
1
class FirstMissingPositiveSolution {
public static int FirstMissingPositive(int[] nums) {
int n = nums.Length;
for (int i = 0; i < n; i++) {
if (nums[i] <= 0 || nums[i] > n) {
nums[i] = n + 1;
}
}
for (int i = 0; i < n; i++) {
int num = Math.Abs(nums[i]);
if (num <= n) {
nums[num - 1] = -Math.Abs(nums[num - 1]);
}
}
for (int i = 0; i < n; i++) {
if (nums[i] > 0) {
return i + 1;
}
}
return n + 1;
}
static void Main() {
int[] nums = {3, 4, -1, 1};
Console.WriteLine("The first missing positive is " + FirstMissingPositive(nums));
}
}Through C#, it uses similar logic of invalidating out of range values, then marking valid index during the second pass, ultimately seeking for first positive unmarked index.