Arrays - First Missing Positive

Given an unsorted integer array nums, return the smallest missing positive integer.

You must implement an algorithm that runs in O(n) time and uses O(1) auxiliary space.

Input: nums = [1,2,0]
Output: 3
Explanation: The numbers in the range [1,2] are all in the array.

Input: nums = [3,4,-1,1]
Output: 2
Explanation: 1 is in the array but 2 is missing.

Input: nums = [7,8,9,11,12]
Output: 1
Explanation: The smallest positive integer 1 is missing.

Constraints:

1 <= nums.length <= 10⁵
-2³¹ <= nums[i] <= 2³¹ - 1

Solution 1 - Use the hint of lowest possible positive is 1 and highest possible positive is N+1, use a marking process to identify the smallest one

In this approach, we will use the hint from problem statement, that is smallest positive value possible is 1 and the highest positive value possible is N+1. For example if the array has values from [1, 2, 3, 4, ....N] with N array length, then the highest positive value possible is N+1, or if input array elements which are greater than N, for example in [1, 2, 3, 10] smallest positive value possible is 4. Let's take another example with input array as [-1,4,3,9,10] and the smallest positive will be 1.

So, we can conclude that the smallest positive values must be in the range of 1 and N + 1. Using this hint we will implement below logic to find the smallest positive value.

Implementation steps:

In the first step, loop through input array nums, and mark out-of-bounds numbers, such as 0, negative integers, or number that are greater than N with N + 1.
In the next step, take nums[i] as index and if that is within the range of array length, change the number at that index to negative. By doing so we are marking that the number does exist in the array between 1 and N. For example, say if the array is [4, -1, 9, 6, 8], array length is 5, and the number at index 0 is 4, since 4 is within the bounds of array length, we will mark the corresponding indexed element to negative, i.e. 3^rd indexed element [4, -1, 9, -6 , 8].
Once we mark the array elements, now we will loop through the array one more time and when the first positive integer is found at index i, i+1 will be the smallest positive value possible.
If there is no smallest found after marking the elements, for example if the array has 1....N elements, then the smallest number will be N+1.

public class FirstMissingPositive { static int firstMissingPositive(int[] nums) { // Mark numbers that are out of range, anything less than 0 and greater than N (length of nums) with n+1 // because smallest positive number possible is 1, and if array has n-1 elements the // highest positive value possible is n (in case if array has 1....n), int n = nums.length; for(int i=0; i<n; i++) { if(nums[i] <=0 || nums[i]>n) { nums[i] = n + 1; } } // Mark the nums[i] as index in the array, to indicate that it present. for(int i=0; i<n; i++) { int index = Math.abs(nums[i]); if(index <= n) { nums[index -1] = - Math.abs(nums[index -1]); // abs, in case it was already marked previously } } for(int i=0; i<n; i++) { if(nums[i] >0) { return i+1; } } return n+1; // if all numbers of present in array [0....n-1] } public static void main(String[] args) { System.out.println(firstMissingPositive(new int[] {1,2,0})); System.out.println(firstMissingPositive(new int[] {3,4,-1,1})); } }

Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the length of nums array.
Space complexity: O(1), since we are modifying input array itself and not using any extra data type.

Above implementations source code can be found at GitHub link for Java code

Constraints:

Contents

Implementation steps:

Complexity Analysis: