Finding the First Missing Positive Integer

Given an unsorted array of integers, your task is to find the smallest positive integer that is not present in the array. This is a fundamental problem in algorithm design with applications in data validation, duplicate detection, and set manipulation.

Problem Description

You are given an array of integers. Your goal is to find the smallest positive integer (greater than 0) that does not exist within this array.

Requirements:

• The solution must identify the first missing positive integer.
• The solution should handle arrays containing negative numbers, zeros, and duplicates.
• The solution should ideally be efficient in terms of time and space complexity.

Expected Behavior:

• If the array contains [1, 2, 0], the smallest missing positive integer is 3.
• If the array contains [3, 4, -1, 1], the smallest missing positive integer is 2.
• If the array contains [7, 8, 9, 11, 12], the smallest missing positive integer is 1.

Edge Cases to Consider:

• An empty array.
• An array containing only negative numbers or zeros.
• An array containing all positive integers from 1 up to its length.

Examples

Example 1:

Input: [1, 2, 0]
Output: 3
Explanation: The positive integers present are 1 and 2. The smallest positive integer not present is 3.

Example 2:

Input: [3, 4, -1, 1]
Output: 2
Explanation: The positive integers present are 1, 3, and 4. The smallest positive integer not present is 2.

Example 3:

Input: [7, 8, 9, 11, 12]
Output: 1
Explanation: The smallest positive integer is 1, and it is not present in the array.

Example 4 (Edge Case):

Input: []
Output: 1
Explanation: An empty array does not contain any positive integers, so the smallest missing positive is 1.

Constraints

• The array can contain between 0 and 500,000 elements, inclusive.
• The values within the array can range from -2,147,483,648 to 2,147,483,647.
• Your algorithm should aim for a time complexity of O(n) and a space complexity of O(1) (excluding the input array itself).

Notes

• Consider how you can use the array's indices to your advantage.
• Think about ways to mark the presence of positive integers without using additional data structures like hash maps or sets.
• The goal is to find the smallest missing positive integer.