This is a new series where I document my struggles of leetcode questions hoping seeing however small of an audience I get gives me the motivation to continue.
Saw this on another site, don't think the site have NDA at all ... if it does then I'll take this down. I am probably too nobody for them to care anyways lol
the question is given an array of 0 and positive integers, find the smallest number not in the array.
The array is not sorted and the numbers in it can be anything.
[5,3,19,4,1,0], or [0,888,22,1111,1,2,777,9999], or [1,2,3,4,5,6,7], or [0,1,2,3,4,5] are all valid possible inputs.
The first thing to notice is in [0,1,2,3,4,5] example
1.) if the array is full correct continuous array, then the missing number is the length
2.) if the continuous array just misses one number, [0,1,2,3,5,6] then then there is a point where array[index] != index.
In other words most indexes should be array[index] == index.
This is an important key point to keep in mind, something I did not do while I was solving this and ultimately failed because I can't switch my mind onto this point albeit knowing this.
There are SEVERAL ways of solving this, this is also why I am writing about this. There is also a pretty dang cleaver algorithm at the end.
the first super brute force way to solve it is
1.) loop array to find max
2.) create newArray with length === max
3.) loop newArray and put array[value] = true
4.) loop newArray again to find the first missing value
this is O(N) time complexity but has O(max_num_in_array) space required, could be terribly bad for like [0,99999999] lol ...
a small improvement is to sort the array first, probably first thing that came into your mind
1.) sort
2.) from 0 to array.lenght-1, check if array[index] === [index]
3.) if not, return index
the next thing you could do, this is probably the optimal interview solution:
1.) loop elements and add to a hashmap/hashset/map
2.) for i = 0 to length-1, check if hashmap[i] exists
3.) return i if hashmap doesn't have value
the best you can do is:
1.) loop through the array index, if array[index] != index then you
swap like:
const temp = array[array[index]];
array[array[index]] = array[index];
array[index] = temp;
2.) then the while loop runs until the array[index] === index
(the swap algorithm is trivial, but you need to understand what is swap with what, and why the while loop would continue running)
*in the while condition, you also checks if array[index] < length, if it is not we don't need to consider swapping it. Its value will either be overwritten or rightfully fail at step 4.
3.) then you can continue the for loop until all index=length-1;
4.) you run through the elements again and see if there is any missing index value in the array.
Note one thing, if there is a missing value, then it means that some integer in array is >= length, so you'll check against that and discard that value
[dang it I closed the window and have no access to the question and the code I wrote loooool.... fuck me... but I think my explanation is close enough and just knowing there is this sorting trick is probably more than enough for us all. Sorry!]
Let me know anything on your mind after reading through this, THANKS!
Top comments (0)