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
Please leave a comment below if you like this post or found some errors, it will help me to improve my content.

Comments

  1. Hi people
    I have created a small video trying to explain the O(n) time and O(1) space complexity approach, please check this out :)

    https://www.youtube.com/watch?v=aWsoJLCXJNo

    ReplyDelete

Post a Comment

Popular Posts from this Blog

Shell Script to find sum, product and average of given numbers - The Coding Shala

Shell Script to Create a Simple Calculator - The Coding Shala

Add two numbers in Scala - The Coding Shala

LeetCode - Number of Good Pairs Solution - The Coding Shala

Richest Customer Wealth LeetCode Solution - The Coding Shala