LeetCode 41: First Missing Positive – O(n) Time and O(1) Space Java Solution

IntroductionFinding the smallest positive integer missing from an unsorted array appears simple at first, but the problem becomes significantly more interesting because of its strict constraints.Problem Link -: First Missing PositiveGiven an unsorted integer array nums, the task is to return the smallest positive integer that does not appear in the array.For example:nums = [1,2,0]The positive integers begin with:1, 2, 3, 4, ...Both 1 and 2 are present, while 3 is missing.Therefore, the answer is:3The challenge is that the solution must run in:O(n) timeO(1) auxiliary spaceThis rules out several common approaches such as sorting and using a HashSet.Problem StatementGiven an unsorted integer array nums, return the smallest positive integer that is not present in the array.ExampleInput: nums = [3,4,-1,1]Output: 2The positive integers are:1, 2, 3, 4, ...1 exists in the array, but 2 does not.Therefore:Answer = 2Another example:Input: nums = [7,8,9,11,12]Output: 1Since 1 itself is missing, the answer is immediately:1Understanding the Important ObservationFor an array of length n, the answer can never be greater than:n + 1Consider:nums = [1,2,3]The first three positive integers are present:1, 2, 3Therefore, the smallest missing positive integer is:4Since n = 3:answer <= n + 1This observation is the key to the optimal solution.Numbers that are:<= 0or> ncannot directly determine the smallest missing positive number.The useful values are only:1 ... nThe Submitted HashSet ApproachA straightforward approach is to store every value in a HashSet and then search for the first missing positive integer.The basic idea is:Store all numbers ↓Check 1 ↓Check 2 ↓Check 3 ↓...The submitted implementation follows this idea:class Solution { public int firstMissingPositive(int[] nums) { int max = Integer.MIN_VALUE; HashSet<Integer> ms = new HashSet<>(); for (int a : nums) { max = Math.max(a, max); ms.add(a); } for (int i = 1; i <= max; i++) { if (!ms.contains(i)) { return i; } } if (max < 0) { return 1; } return max + 1; }}This approach is logically valid for finding the answer, but it does not satisfy the required constraints.Space ComplexityThe HashSet can store up to n elements.Therefore:O(n) auxiliary spaceThe problem requires:O(1) auxiliary spaceSo a different technique is required.Why Sorting Is Also Not EnoughSorting the array might appear to solve the problem easily.For example:[3,4,-1,1]After sorting:[-1,1,3,4]The missing positive integer can then be identified by scanning the array.However, sorting requires:O(n log n)time in the general case.The problem specifically requires:O(n)time.Therefore, sorting does not satisfy the required complexity either.The Core Idea: Put Every Number in Its Correct PositionThe optimal solution uses an in-place cyclic placement technique.The important relationship is:value 1 → index 0value 2 → index 1value 3 → index 2value 4 → index 3...In general:value x → index x - 1Consider:nums = [3,4,-1,1]The desired arrangement for useful values is:index: 0 1 2 3value: 1 2 3 4After placing the valid values into their corresponding positions, the array can become:[1, -1, 3, 4]Index 1 should contain:2but it contains -1.Therefore:answer = index + 1 = 1 + 1 = 2This transforms the problem from:Search for a missing number.into:Place every useful number at the position where it belongs, then find the first incorrect position.Which Numbers Should Be Placed?For an array of length n, only values satisfying:1 <= nums[i] <= nneed to be placed.Why?Suppose:n = 5The answer can only be one of:1,2,3,4,5,6A value such as:-4cannot be the answer.Similarly:10cannot prevent 1...6 from determining the answer.Therefore, values outside the range [1,n] can safely remain where they are.The Cyclic Placement ProcessFor every index i, check the current value:nums[i]If it belongs to the range:1 <= nums[i] <= nits correct index is:nums[i] - 1So the value should be swapped into:nums[nums[i] - 1]The process continues until the current position contains a value that either:is outside the useful range, oris already in its correct position.Why the Duplicate Check Is NecessaryConsider:nums = [1,1]The value 1 belongs at index 0.The first element is already correct.At index 1, the value is again 1.Trying to swap it repeatedly would cause an infinite loop because another 1 already occupies its correct position.Therefore, the swap condition must also ensure:nums[nums[i] - 1] != nums[i]This duplicate check is extremely important.Optimized Java Solutionclass Solution { public int firstMissingPositive(int[] nums) { int n = nums.length; for (int i = 0; i < n; i++) { while ( nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i] ) { int correctIndex = nums[i] - 1; int temp = nums[i]; nums[i] = nums[correctIndex]; nums[correctIndex] = temp; } } for (int i = 0; i < n; i++) { if (nums[i] != i + 1) { return i + 1; } } return n + 1; }}Dry RunConsider:nums = [3,4,-1,1]Array length:n = 4Initial Array[3, 4, -1, 1]At index 0:nums[0] = 3The correct index for 3 is:3 - 1 = 2Swap:[3, 4, -1, 1] ↓[-1, 4, 3, 1]The value at index 0 is now -1.Since -1 is outside [1,4], no further placement is required for this index.At index 1:nums[1] = 4Correct index:4 - 1 = 3Swap:[-1, 4, 3, 1] ↓[-1, 1, 3, 4]Now:nums[1] = 1The correct index of 1 is 0.Swap:[-1, 1, 3, 4] ↓[1, -1, 3, 4]Now index 1 contains -1, so placement stops.Final Arrangement[1, -1, 3, 4]The expected value at each index is:index 0 → 1 ✓index 1 → 2 ✗index 2 → 3 ✓index 3 → 4 ✓The first incorrect position is:index = 1Therefore:answer = index + 1 = 2Another ExampleConsider:nums = [1,2,0]The values 1 and 2 are already in their correct positions:[1,2,0]Expected arrangement:index 0 → 1 ✓index 1 → 2 ✓index 2 → 3 ✗The first incorrect position is index 2.Therefore:answer = 2 + 1 = 3Edge Case: All Positive Numbers Are PresentConsider:nums = [1,2,3]Every position contains the expected value:index 0 → 1index 1 → 2index 2 → 3No missing value exists between 1 and n.Therefore, the smallest missing positive integer is:n + 1So:answer = 4Edge Case: The Answer Is 1Consider:nums = [7,8,9,11,12]All values are greater than 1.After the placement phase, there is no 1 at index 0.Therefore:answer = 1Complexity AnalysisThe algorithm uses the array itself to store values in their correct positions.Time ComplexityAlthough the algorithm contains a nested while loop, the total number of swaps is bounded by O(n) because every successful swap places a useful value into its correct position.Therefore:Time Complexity: O(n)Space ComplexityNo additional data structure proportional to the input size is used.Only a few variables are required:Space Complexity: O(1)This satisfies the required constraints.Why the Algorithm WorksThe central invariant is:Whenever a value x lies in the range [1,n], the algorithm attempts to place it at index x-1.After the placement phase, every value that can occupy a meaningful position is either:at its correct indexorabsent from the arrayTherefore, scanning from left to right provides a direct answer.If:nums[i] != i + 1then i + 1 is missing.If every position is correct, then all values from:1 ... nexist, making:n + 1the smallest missing positive integer.Interview InsightThis problem is an important example of in-place array positioning.The key pattern is:Value x ↓Correct index = x - 1Whenever an array problem asks for a missing, duplicate, or misplaced number within a known range, it is worth checking whether the values themselves can be mapped directly to indices.This technique appears in several interview problems involving:Missing numbersDuplicate numbersCyclic sortIn-place rearrangementFrequency representation without extra memoryThe biggest clue in this problem is the combination of:Unsorted array+O(n) time+O(1) space+Positive integersThat combination strongly suggests an in-place index/value mapping strategy.ConclusionLeetCode 41, First Missing Positive, is a classic example of turning the array itself into auxiliary storage.A HashSet provides an easy solution but requires O(n) extra space. Sorting simplifies the search but requires O(n log n) time. The optimal solution instead uses the relationship:value x → index x - 1to rearrange useful values directly inside the input array.After this placement, the first index whose value does not match index + 1 identifies the smallest missing positive integer.The final complexity is:O(n) timeO(1) auxiliary spacemaking the approach suitable for the strict constraints and an important pattern to recognize in technical interviews.