Amazon Coding Interview Question - First Missing Positive (LeetCode)

Here is a step by step explanation of a hard array problem asked at Amazon!

►Support me on Patreon: https://www.patreon.com/michaelmuinos
Join the Discord channel by becoming a supporter on my Patreon!
In this Discord channel, you will be able to...
1. Contact me directly for interview prep advice, tech questions, project ideas, etc.
2. Discuss interview experiences with other members
3. Discuss technical questions with other members
4. Find mock interview partners & more!

►Follow me on Twitter: https://twitter.com/MichaelMuinos
►Follow me on Github: https://github.com/MichaelMuinos

In this video, I go over the problem "First Missing Positive". This is a hard problem asked at many tech companies including Amazon, Bloomberg, Google, and many more. This problem would be considered an easy/medium if there wasn't a restriction that we must have a solution with constant extra space.

In the brute force approach, we could add all of the numbers we have in our input to a set. Then, we perform a loop from 1 to N where N is the number of elements we have in our input and check if the number is present in the set. If the number we are on is not in the set, we found our first missing positive. The brute force approach involved a linear time AND space complexity.

Now, in the optimized approach, it takes 3 steps to solve this problem. For step 1, we must convert any negative numbers and numbers greater than N to a 1. This is done to restrict our range of numbers. For step 2, we use the range of numbers as indexes to our array and perform a lookup to swap the sign of the element at the index. This will signify we have seen the positive number without doing any sorting. In the final step, we look for the first non-negative number, if we find one, the index + 1 is the first missing positive; however, if we don't find it, we know the answer will be N + 1.

Видео Amazon Coding Interview Question - First Missing Positive (LeetCode) канала Michael Muinos