This is our solution and implementation to problem #41: First Missing Positive on LeetCode.
Our code is written in Java. If you want to code your solution in a different language, no worries, as the core concepts will carry over from language to language. This page includes our analysis of the problem, our implementation strategy our video which outlines our analysis and implementation approach, a breakdown on the space and time complexity, and the full code implementation.
Note: the code and contents here might be slightly different than what is in the video. We've made some improvements to some of the code since recording.
If you would like to view the original problem and solve it, please visit: First Missing Positive on LeetCode.
Given a list of integers, we need to return the smallest positive integer which is missing in the input list. The list is not guaranteed to be sorted and each element in the list is not guaranteed to be unique. With that in mind, our implementation must handle the following types of cases:
- The missing number is smaller than all others included in the input.
- The missing number is larger than all others.
- The smallest number missing is larger than the smallest positive integer but smaller than largest positive integer.
- The list contains one or more instances of duplicate numbers.
- Is is not in sorted order or is in reverse sorted order.
We are given additional constraints that the time complexity must be O(n) and the space complexity must be O(1), which means that we must be careful not to use any type of quadratic, or otherwise nested, iteration and must be sure we don't use any lists, sets, or maps which grow in size as the input grows. We do not have any restrictions on changing the input itself once it comes in; in other words: we can manipulate the input list in any way we need so long as we output the correct answer.
We will take advantage of the fact that we can manipulate the input array in our implementation. This will provide us with O(n) "working space", while still complying with the O(1) auxiliary space. We will perform two iterations over the input: the first one to swap certain elements, and the second one to read the elements in swapped order and find the first "unexpected" element. The goal of the first iteration is to partially sort the input list, such that for each number 1..n, 1 appears in the 0th index, 2 appears in the 1st index, etc. If the input list has all numbers, all of them will appear in that order. If any are missing, that condition will be violated in one or more place. This partial sorting will take place by swapping items out based on the conditions below, where n is the input list and i is the current iterator index:
- If n[i] < 1 || n[i] >= n.length, ignore the steps below.
- If n[i] == i + 1, meaning that the item is already in its correct place, ignore the steps below.
- Store the value from n[i] - 1 into a temp variable.
- If n[tmp] == tmp + 1, or if the item at the position to swap (based on temp variable) is in its correct place, ignore the steps below.
- Swap the two items.
- Rewind the iterator, so we can perform this same action on the item we've just swapped.
The diagram below outlines this full process on an example input list. Once the partial ordering is complete, we will start a new iteration and move through until we find an "unexpected item". At each point, i should be equal to nums[i] - 1. If it is not, then the missing positive integer is i + 1. If we don't encounter this condition at all, then the input array does have all integers from 1...n, so we must return n+1.
Space and Time Complexity
The space complexity is O(1), as we are only using a constant number of variables outside of the initial input itself. The time complexity is O(n) as we are only iterating over the input twice.
If we were given a guarantee that each item in the input would be unique, we could solve this using one iteration instead of two. During the iteration, we can keep track of:
- The smallest positive integer in the list.
- The largest integer in the list.
- The sum of all positive integers in the list.
Once the iteration is concluded, we would calculate the triangle number of the largest positive integer, meaning the sum from 1 to that integer, and compare to the actual sum. If the two values are the same, then we have all integers from 1...n, so we can return n.length + 1. Otherwise, we can return triangleNumber - actualSum.
Our solution is given in the Java files below. This solution uses more than one code file. The Main.java file is used as a runner to test locally and includes a few test cases, some from the examples provided by LeetCode and some designed for our own test purposes. The Solution.java file contains the main logic for the solution.
All of our solutions are hosted on GitHub. The code on this page was pulled from the repo.