How to Solve First Missing Positive

Ian Grubb
Ian Grubb
Oct 19, 2020 · 6 min read
Photo by Andrew Buchanan on Unsplash

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

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

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

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

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?

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

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!

The Startup

Get smarter at building your thing. Join The Startup’s +800K followers.

Ian Grubb

Written by

Ian Grubb

Full stack web developer and educator. Former software engineering coach at Flatiron School and adjunct professor in philosophy at NYU.

The Startup

Get smarter at building your thing. Follow to join The Startup’s +8 million monthly readers & +800K followers.

Ian Grubb

Written by

Ian Grubb

Full stack web developer and educator. Former software engineering coach at Flatiron School and adjunct professor in philosophy at NYU.

The Startup

Get smarter at building your thing. Follow to join The Startup’s +8 million monthly readers & +800K followers.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store