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
In JavaScript, the solution invalidates and negates numbers in valid positions, allowing determination of the missing positive by simple iteration for positive rest values.