Programming Challenge: Smallest Missing Integer

Problem Statement: Given an unsorted integer array, find the smallest missing positive integer.

Function Signature:

public int firstMissingPositive(int[] nums);

Examples:

• Input: [1,2,0]
  Output: 3
• Input: [3,4,-1,1]
  Output: 2

Solution Code

public class MissingPositiveFinder {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        
        // Mark numbers that are out of range
        for (int i = 0; i < n; i++) {
            if (nums[i] <= 0 || nums[i] > n) {
                nums[i] = n + 1;
            }
        }
        
        // Mark indices as negative
        for (int i = 0; i < n; i++) {
            int num = Math.abs(nums[i]);
            if (num <= n) {
                nums[num - 1] = -Math.abs(nums[num - 1]);
            }
        }
        
        // Find first positive index
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        
        return n + 1;
    }
}

Complexity Analysis

Approach	Time Complexity	Space Complexity
Index Marking	O(n)	O(1)