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.
1def first_missing_positive(nums):
2 n = len(nums)
3 for i in range(n):
4 while 0 < nums[i] <= n and nums[nums[i] - 1] != nums[i]:
5 nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
6 for i in range(n):
7 if nums[i] != i + 1:
8 return i + 1
9 return n + 1
10
11nums = [3, 4, -1, 1]
12print(f"The first missing positive is {first_missing_positive(nums)}")In Python, the code swaps elements to their rightful indexes if they fall within the bounds, then searches for the first missing number.
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
Remove out of range numbers by filling them with the max possible value. Using negative marking helps identify seen numbers within the range, returning the first positive marked index.