First Missing Positive Solution - The Coding Shala

Home >> Interview Prep >> First missing positive

 In this post, we will learn how to solve the First Missing Positive problem and will implement its solution in Java.

First Missing Positive Problem

Given an unsorted integer array nums, find the smallest missing positive integer. You must implement an algorithm that runs in O(n) time and uses constant extra space.

Example 1:

Input: nums = [1,2,0]

Output: 3

Example 2:

Input: nums = [3,4,-1,1]

Output: 2

First Missing Positive Java Solution

Approach 1

Time Complexity: O(n)
Space Complexity: O(1)

The steps are below to solve this problem:

Step 1: The first missing positive number will be in the range of 1 to N+1, where N is the length of the array. So Other than these numbers we can ignore, make this change in the array.

Step 2: Now we will take the array elements as the index(their original position), and at the numbers' original position will make the array element negative so later we can check this number is available in the array.

Step 3: now find the first non-negative number in the array that is our first missing positive number.

Step 4: if we couldn't find the non-negative number then return N+1.

for example:

array => [3,4,-1,1]

after step 1:  array => [3,4,5,1]   N = 4

in step 2:    array[0] = 3 so array is => [3,4,-5,1]

                   array[1] = 4 so array is => [3,4,-5, -1]

                   array[2] = 5 skip

                   array[3] = 1 so array is => [-3, 4, -5, -1]

In step 3, we have the first non-negative number is 4 at index 1 to return index+1 = 2

Java Program: 

class Solution {
    public int firstMissingPositive(int[] nums) {
        int N = nums.length;
        // fist positive number range is 1 to N+1
        // ignore other numbers
        for (int i = 0; i < N; i++) {
            if (nums[i] <= 0 || nums[i] > N) nums[i] = N + 1;
        }
        
        // make numbers negative at their original index
        for (int i = 0; i < N; i++) {
            // take num as index now
            // -1 because numbers are started with 1
            int index = Math.abs(nums[i]) - 1; 
            
            // make negative at index
            if (index >= 0 && index < N && nums[index] > 0) {
                // number is available in array
                nums[index] = -1 * nums[index];
            }
        }
        
        // now find first non-negative number that is our first missing positive number
        for (int i = 0; i < N; i++) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        
        // if non-negative number is not there
        return N + 1;
    }
}

Approach 2

Using HashSet.

Time Complexity: O(n)

Space Complexity: O(n)

Java Program: 

class Solution {
    public int firstMissingPositive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        
        for (int i = 0; i < nums.length; i++) {
            set.add(nums[i]);
        }
        
        int i = 1;
        int res = -1;
        while (true) {
            if (!set.contains(i)) {
                res = i;
                break;
            }
            i++;
        }
        
        return res;
    }
}

Other Posts You May Like

• Find the first and the last position of an element in a sorted array
• Two Sum Problem
• Minimum Size Subarray Sum
• Repeat and Missing Number Array
• Add one to Number

Please leave a comment below if you like this post or found some errors, it will help me to improve my content.