How to Solve First Missing Positive
I try to spend some time each week practicing algorithms. Lately, I’ve been challenging myself to find solutions that are optimized for readability and clarity, not just time or space complexity. A well-written solution should be organized in a way that makes its key ideas as explicit as possible. Approaching algorithms this way helps me understand my solutions and explain them to others.
Let me illustrate this approach by applying it to the LeetCode problem First Missing Positive. Figuring this one out was a fascinating challenge. I’ll share my thought process and how I approached writing my solution.
The Challenge
Before we get started, I encourage you to take a shot at First Missing Positive yourself. For those who want to get straight to the explanation, here’s the challenge: you’re given an unordered array of integers and your goal is to find the smallest positive integer that doesn’t appear in the array. For instance, for the input [3, 4, -1, 1] we should return 2, since there’s a 1 in the array but not a 2. This isn’t that difficult to do, but here’s the catch: you’re supposed to do this in linear time while only using a constant amount of extra space.
This rules out the natural solution of sorting the array and then iterating over it looking for the missing number. This would work as follows:
But this attempt violates the constraint, since sorting the array takes more than linear time.
Some Initial Observations
I find that before attempting to write a solution, it helps to make general observations about the nature of the problem. These observations will end up playing a role in the finished solution, so it helps to consider them first on their own.
First, some numbers in the input array might not be relevant to determining the right answer. Any non-positive number won’t make a difference to determining the smallest missing positive, so it can safely be ignored. Also, any number larger than the length of the array can’t make a difference either — a number can only make a difference if there’s a sequential chain between it and 1, but there aren’t enough numbers to form such a chain if the number is larger than the length of the array.
Second, although it’s possible for duplicate numbers to show up, they’ll never make a difference to the smallest missing positive either. Once we find one instance of a number, the existence of more instances of that same number can safely be ignored.
Third, we’re going to have to use some amount of memory to keep track of the numbers we’ve seen while iterating over the array, and since we’re only allowed constant additional space we’ll be forced to reorder the initial array in place. Doing so in general is risky, since it might throw away valuable information. However, in this case the problem explicitly tells us that the initial array is unordered, so let’s presume that we can safely reorder it as we see fit.
The Key Idea
Sorting the array was a promising idea, but turned out to be too slow. But why assume that we need a fully sorted array? The key idea to solving the problem is that there’s a rearrangement procedure that both: (1) results in an array that’s sorted enough for us to find the smallest missing positive and (2) only takes linear time to run.
Specifically, what we need is a rearrangement that ensures the following: for any index i, if there’s at least one instance of the number i + 1 in the array, then index i has that number. For instance, if there’s a 2 somewhere in the array, then after the rearrangement a 2 should be at index 1.
If we can rearrange the array in this manner, we can find the smallest missing positive. All we have to do is iterate over the array until we find an unexpected number, and the index of that number will correspond to the smallest missing number. If we don’t find an unexpected number, then the array must be like [1, 2, 3] and we should just return the length of the array plus one. Here’s the idea in code:
This iteration takes linear time with no additional space complexity, so all that’s left is figuring out how to rearrange the numbers.
Aligning Numbers with Indicies
Here’s the procedure: we’ll iterate over the array and whenever we find a number that belongs at some other index in the array, we’ll swap it with the number that’s currently at that index. We may have to keep swapping multiple times for one index, but eventually we’ll get a number that doesn’t have to be swapped and then we’ll move on to the next index. Once we do this for every index in the array, the procedure is complete.
To see how this works, let’s start writing out some code to give us something more concrete to reason about:
For each index, we swap numbers until a certain condition fails to be met. Each time, we consider the target number at that index and potentially move it to a new destination. Note that we have to reset the target number and potential destination at the end of each pass through the while loop.
The code to swap two elements in an array is straightforward: you just use a temporary variable to store the first value, change the first value, and then change the second value. Let’s add that to our code:
Okay, now what about the condition? First, we only want to swap a number if there’s a place in the array where that number belongs. This means we shouldn’t attempt to move a number that’s less than 1 or a number that’s greater than or equal the length of the array. Second, we only want to swap a number into a position if that position doesn’t already have the correct number in it. For instance, if we find a 5 but there’s already a 5 at index 4, then we should skip the extra 5 and leave it where it is.
All we have to do now is code up those conditions and use them. Here’s the function with everything added:
Although it would be possible to save marginal amounts of memory by cutting out some of the extra helper methods and variable declarations, I prefer the function as it is, since it reads in a way that reflects the thought process behind the algorithm.
Does Alignment take Linear Time?
There’s one last point we need to get clear on before we conclude. In order to satisfy the constraints of the original problem, the function we just wrote has to run in linear time. But does it?
On the face of it, it would seem like it takes longer than linear time. As a general heuristic, whenever you have one loop inside of another you likely have a function that runs in quadratic time. We have a while loop inside of a for loop, so maybe we don’t have the right kind of solution after all.
However, consider two facts about our conditions from above. First, we only swap when a number will get placed at the appropriate index in the array. Second, once a number is placed at the appropriate index in the array, there’s no way for it to get swapped out of that position. Putting these two points together, we can conclude that the maximum number of times we could go through the while loop is equal to the length of the array. This means that, at most, we might have n steps from the while loop and n steps from the for loop, but that’s still just linear time.
Conclusion
Now that that we have the helper function we needed, all we have to do is put everything together. Here’s the finished product:
This is a pretty verbose solution. Although you could rewrite it to be a bit more succinct, I prefer a more verbose solution when it’s self-documenting. All of the concepts that go into the solution are explicated as helper functions in the code itself. Because of this, reading the code gives you a summary of how it’s meant to work.
The first drafts of my algorithm solutions typically don’t come out this way. It definitely takes more work to find a solution that’s both correct and clear. I’ll admit that it can be hard to put in that work — practicing algorithms can feel like a game that you win by moving as quickly as you can. However, coding is a craft and I find that I get a lot more out of algorithm problems by slowing down and focusing on honing that craft. Give it a shot and see if it works for you too!
