Every ad shown on Twitch has a unique integer ad_id, starting at 0, 1, 2, 3...
Each user on Twitch has an array of ad_ids that they have seen, in the order that they viewed them (unsorted, can
have duplicates).
The product team has requested that we update the algorithm that decides which ad to show to a user. They would
like to always show the lowest ad_id that the user has NOT already seen.
Write a function that, given the user's array of seen ad_ids, returns the correct ad_id. Assume valid input.

Examples:
[6,2,1,4,0] = return 3
[2,5,3] = return 0
[] = return 0

Answer: Iterate through the input array, keep state for the max integer. For every i from 0 to the max, for the first i not contained in the set, return this i. In the event that every i is contained in the set, return i + 1.

Follow-up: Do this using an array.
Answer: Counting sort, whereby the counting sort array is a primitive array of booleans. Find the max integer as in the first answer, but this time allocate an array of size max + 1. Iterate through this counting sort array and for the first value that is false, return the corresponding index.

Follow-up: Do this using an array, using at most n space, whereby n is the size of the input array.
Answer: Allocate the array of size n + 1. For every value in the input array, if it is less than or equal to n, then mark this in the counting sort array as true. Then, iterate through your counting sort array and for the first element not equal to true, return this index. In the event that one is not found, return n. Note that there is no notion of finding a max in this solution.

Edit: A siimilar question is First Missing Positive.