### First Missing Positive Solution - The Coding Shala

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

**Example 1:**

**Example 2:**

## First Missing Positive Java Solution

### Approach 1

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.

**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

**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

Hi people

ReplyDeleteI 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