Leetcode 41: First Missing Positive

There are a few different ways to solve this including some ways that destroy some of the (out of bounds) values. My favoured solution keeps all the values but just rearranges them. I iterate through all the numbers and at each I do a loop to swap the value with the value at the index of the value if it is in bounds and is not equal to this number. Finally we do another pass to see which index contains a number different from index+1.

Different solution using clearing out of bounds values and marking index positions with negatives:

As we know that we don’t need to consider negative numbers, we can use negatives as switches for each element position. A negative will mark that we have a number equal to the element’s index. As we sequentially read through the element values, we will mark them off by looking up indexes by using the values, so for value a[i] we will look up a[a[i]]. We then do another pass to find the first non-negative value, which marks the first missing positive. Here are my whiteboard notes:

Code for this solution:

This entry was posted in programming and tagged , , . Bookmark the permalink.

Leave a Reply

Your email address will not be published.