LeetCode #41: First Missing Positive — Solved in Java

Flag Array Marking and In-Place Index Placement

Image Source

LeetCode 41, First Missing Positive, asks you to scan an unsorted integer array and return the smallest positive integer that does not appear in it. The input can contain negatives, zero, and large positive values, and the problem statement requires an O(n) time solution with only O(1) auxiliary space, so extra structures like hash sets or large helper arrays do not fit the official constraints.

When thinking about this problem in Java, it helps to focus on the limited range where the answer can live and how array indices can represent that range directly. For an array of length n, the smallest missing positive is always somewhere between 1 and n plus 1, so the logic can concentrate on that band of values and either record their presence in a helper structure or rearrange the input so value v tries to sit at index v minus 1. That point of view turns the array into a compact map from indices to candidate values, which fits naturally with Java’s zero based indexing and keeps every check and swap in constant time.

LeetCode: First Missing Positive

Given an unsorted integer array nums. Return the smallest positive integer that is not present in nums.

You must implement an algorithm that runs in O(n) time and uses O(1) auxiliary space.

Example 1:

Input: nums = [1,2,0]
Output: 3
Explanation: The numbers in the range [1,2] are all in the array.

Example 2:

Input: nums = [3,4,-1,1]
Output: 2
Explanation: 1 is in the array but 2 is missing.

Example 3:

Input: nums = [7,8,9,11,12]
Output: 1
Explanation: The smallest positive integer 1 is missing.

Constraints:

• 1 <= nums.length <= 10⁵
-2³¹ <= nums[i] <= 2³¹ - 1

Solution 1: Flag Array Marking for Present Positives

This method creates a small helper array of boolean flags indexed by value. Any positive value between 1 and n, where n is the length of the original array, can be a candidate for the answer. Numbers outside that range do not matter for the smallest missing positive, because the answer for an array of length n always lies between 1 and n + 1.