Introduction

The First Missing Positive problem involves finding the smallest positive integer that is missing from the array.

Given an unsorted integer array arr[], the task is to find the first missing positive number.

The solution should work efficiently in:

  • linear time
  • constant extra space

This is one of the most important advanced Hashing and Array Manipulation problems and helps in understanding index mapping, cyclic placement, and in-place hashing techniques.

Example
Input: arr[] = [1, 2, 0]Output: 3
Explanation:
Positive numbers present are:
1, 2
The smallest missing positive number is 3.

Input: arr[] = [3, 4, -1, 1]
Output: 2
Explanation:
Positive numbers present are:
1, 3, 4
The smallest missing positive number is 2.

Constraints

     1 <= n <= 10^5 -10^9 <= arr[i] <= 10^9

Approach 1 : Brute Force (HashSet)

Explanation

The simplest way to solve this problem is:

  1. Store all positive elements in a HashSet
  2. Start checking numbers from 1.
  3. The first missing number is the answer

This approach is easy to understand but uses extra space.

Steps

  1.  Create a HashSet.
  2. Store all positive numbers.
  3. Start checking integers from 1.
  4. If a number is missing:
    • return it
  5. Continue until missing number is found.

Dry Run:

Input Array: [3, 4, -1, 1]Store positive numbers:
{1, 3, 4}
Check 1:
Present
Check 2:
Missing
Return 2

Brute Force Code

Complexity Analysis

Time Complexity: O(n)
Explanation:
Each element is inserted and checked once.

Space Complexity: O(n)
Explanation:
HashSet stores positive numbers.

Approach 2 : Optimized Solution (Cyclic Placement)

Explanation

Instead of using extra space, we can place every positive number at its correct index.

The idea is:

 Value x should be placed at index (x - 1)
For example:

1 should be at index 02 should be at index 1
3 should be at index 2

After placing elements correctly:

  • the first index where:
    • arr[i] != i + 1
  • gives the missing positive number

This technique is called:

  •  cyclic sort
  • index mapping
  • in-place hashing

Steps

  1.  Traverse the array.
  2. While current element is:
    • positive
    • within range
    • not already at correct position
    • swap it to correct index
  3. Traverse again.
  4. First incorrect index gives answer.
  5. If all positions are correct:
    • return n+1

Dry Run

Input Array: [3, 4, -1, 1]Traverse 3:
Correct index for 3 = 2
Swap 3 and -1
Array:
[-1, 4, 3, 1]
Traverse 4:
Correct index for 4 = 3
Swap 4 and 1
Array:
[-1, 1, 3, 4]
Traverse 1:
Correct index for 1 = 0
Swap 1 and -1
Array:
[1, -1, 3, 4]
Traverse array again:
Index 0 → correct
Index 1 → arr[1] != 2
First Missing Positive = 2

Optimized Code

Complexity Analysis

Time Complexity: O(n)
Explanation:
Each element is placed at correct position at most once checked once.

Space Complexity: O(1)
Explanation:No extra data structures are used.
Array is modified in-place.

Edge Cases

  1. Array contains negative numbers
  2. Array contains duplicates
  3. Array contains all positive consecutive numbers
  4. Array contains only one element
  5. Array contains zeros

Why This Problem is Important

This problem helps in understanding:

  1. In-place hashing
  2. Cyclic sort technique
  3. Index mapping
  4. Constant space optimization
  5. Advanced array manipulation

It is one of the most important advanced array and hashing interview problems.

Real-World Applications

Index mapping techniques are used in:

  1. Memory management systems
  2. Database indexing
  3. Data validation systems
  4. Scheduling algorithms
  5. Resource allocation systems

Common Mistakes

  1. Infinite swapping loops
  2. Incorrect index calculations
  3. Ignoring invalid values
  4. Incorrect swap conditions

Interview Tips

Interviewers often expect:

  1. O(n) solution
  2. O(1) extra space
  3. In-place placement explanation

Always explain why each number is placed at its correct index position.

Related Questions

  1. Missing Number
  2. Cyclic Sort
  3. Find Duplicate Number
  4. Set Mismatch
  5. Contains Duplicate

Final Takeaway

The First Missing Positive problem is a fundamental advanced array and hashing problem that teaches cyclic placement, index mapping, and in-place hashing techniques. Understanding this problem builds a strong foundation for advanced optimization and constant-space interview problems.