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.
1import java.util.*;
2
3class FirstMissingPositive {
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 public static void main(String[] args) {
22 int[] nums = {3, 4, -1, 1};
23 System.out.println("The first missing positive is " + firstMissingPositive(nums));
24 }
25}The Java implementation also focuses on using cyclic sort to reposition values and looks for the first mismatch index for 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
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.