Leetcode 41: First Missing Positive

This is tricky and probably not typical of a real world problem, so I don’t know how useful it is know. Given the criteria of running it O(n) time and only using constant extra space, the only way we can solve this is by rearranging the array. 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:

And my c++ source code:

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

Leave a Reply

Your email address will not be published. Required fields are marked *