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.
1function firstMissingPositive(nums) {
2 const n = nums.length;
3 for (let i = 0; i < n; i++) {
4 while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] !== nums[i]) {
5 [nums[i], nums[nums[i] - 1]] = [nums[nums[i] - 1], nums[i]];
6 }
7 }
8 for (let i = 0; i < n; i++) {
9 if (nums[i] !== i + 1) {
10 return i + 1;
11 }
12 }
13 return n + 1;
14}
15
16const nums = [3, 4, -1, 1];
17console.log(`The first missing positive is ${firstMissingPositive(nums)}`);JavaScript code uses array destructuring to swap elements, ensuring numbers match their positions before checking for the 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
Java implementation makes use of marking the index with negative values for numbers in range, then checks which index remains unmarked positively for smallest missing.