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.
1using System;
2
3class FirstMissingPositiveSolution {
4 public static int FirstMissingPositive(int[] nums) {
5 int n = nums.Length;
6 for (int i = 0; i < n; i++) {
7 while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
8 int temp = nums[nums[i] - 1];
9 nums[nums[i] - 1] = nums[i];
10 nums[i] = temp;
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
21 static void Main() {
22 int[] nums = {3, 4, -1, 1};
23 Console.WriteLine("The first missing positive is " + FirstMissingPositive(nums));
24 }
25}Using cyclic sorting, C# solutions rearrange elements based on index positions based on their value; first incorrect position gives the answer.
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#include <vector>
#include <cmath>
using namespace std;
int firstMissingPositive(vector<int>& nums) {
int n = nums.size();
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 = abs(nums[i]);
if (num <= n) {
nums[num - 1] = -abs(nums[num - 1]);
}
}
for (int i = 0; i < n; ++i) {
if (nums[i] > 0) {
return i + 1;
}
}
return n + 1;
}
int main() {
vector<int> nums = {3, 4, -1, 1};
cout << "The first missing positive is " << firstMissingPositive(nums) << endl;
return 0;
}In effect, this C++ method filters out non-relevant entries and marks seen within-range numbers as negative, identifying the first absent positive via sign checking.