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 <stdio.h>
2
3int firstMissingPositive(int* nums, int numsSize) {
4 for (int i = 0; i < numsSize; i++) {
5 while (nums[i] > 0 && nums[i] <= numsSize && nums[nums[i] - 1] != nums[i]) {
6 int temp = nums[nums[i] - 1];
7 nums[nums[i] - 1] = nums[i];
8 nums[i] = temp;
9 }
10 }
11 for (int i = 0; i < numsSize; i++) {
12 if (nums[i] != i + 1) {
13 return i + 1;
14 }
15 }
16 return numsSize + 1;
17}
18
19int main() {
20 int nums[] = {3, 4, -1, 1};
21 int size = sizeof(nums) / sizeof(nums[0]);
22 int result = firstMissingPositive(nums, size);
23 printf("The first missing positive is %d\n", result);
24 return 0;
25}The function iterates over the array, swapping elements within the valid range to their correct positions. It then checks for the first missing positive by assessing incorrect positions.
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)
1def
This Python technique replaces invalid numbers with n+1, flips valid indexed numbers negatively, and uncovers the first sign-unflipped index as the missing positive.