Faster to use a heap than to sort the whole array. Then just keep popping the minimum element and looking for a gap to the next element. Gets the cost down to O(N). int lowestUnassigned(const vector &ints) { // Toss them all in a min heap priority_queue pq; for (auto i : ints) { pq.emplace(i); } // Look for a gap int lowerBound = 0; while (!pq.empty()) { lowerBound = pq.top(); pq.pop(); if (pq.empty() || pq.top() - lowerBound > 1) { break; } } return lowerBound + 1; }

@Lurker, I feel like PriorityQueue for this question is overkill. you can simply use the given array and sort it right?

@AlienOnEarth The priority queue is not overkill. Interviewers mostly want to know if you can find the solution with the best worst time complexity. Sorting can't be smaller than Omega(n*logn) VS Omega(2n) -> Omega(n) for the heap version.

Ok two things. @Lurker Pushing and popping to a min heap takes O(logn) time so already that is incorrect. You would take O(nlogn) to add all the items into the heap, same time it takes to sort the list. @Marc The only way to get O(n) time and "O(1)" space is to modify the passed in list. When you modify the input you have to consider that as memory used in the algorithm. I can't pass a list with massive amounts of extra space, use that for tracking and computation, and then claim that I only used O(1) space because I didn't allocate any extra memory.

I think there is a better solution with O(n) running time and an extra O(n) space. You could have a HashSet and remove N[i] if it is in the set and add N[i]+1 if there is no N[i]+2 elements in the set, than you result will be a min value in this set. Plus keep tracking for the min N[i] to confirm that is it smaller than result or result -1 (5,2,3 case) but grater than 1. So for an input 5,3,1 ->6,4,2->2 5,2,1,3->6,3,4->3 5,2,3->6,4->1 In the worst case scenario we would have an extra set of the same size as our input array and would perform 2N iterations, N through the original array and N to find min in the HashSet.

Instead of sorting the whole array at once and then checking the difference between consequent items in array, should we not run the difference check along with sorting? Like, when two items are sorted, check the difference and if it is >1 then, result is minimum+1 and no more sorting and traversing is required. Just a thought.

You can just check servers allocations using HashMap>. This is a map with "Prefix" as key and allocated numbers "Suffix numbers"added to a HashSet. Each time "allocate" is called, you iterate through the integers from 1 to INTEGER_MAX; if the integer is not found in the HashSet, this is the new allocated server name... For "deallocate" you need to implement a function that extracts the server name prefix and suffix (by iterating on the string characters from length()-1 till you find non digit character. Then you will have the prefix (key you search the map with, and also the suffix to remove from the HashSet with O(1)). So, complexity will be, for allocation worst case of O(N), where N is number of allocated servers with this prefix. and deallocation is always O(1) (removing from HashSet) + O(n) which is size of the servername string.

Such an easy question, but somehow I blew it and floundered about while searching for the correct implementation. Looks so simple, like it shouldn't even require practice, but do so anyway.

Yup - this was one of my questions. A note on that: I encourage you to share with your interviewer if they have asked you a problem that you have already encountered (even if you haven't fully written out the solution). Whether or not they change the question they're asking you, you are communicating one of the most important meta-skills the company is looking for: that you are clear, forthright and trustworthy!

Nevermind the prevous comment. Sorting and using a heap they are both the same since removing all items from the heap is same because, on worst case, they have the same complexity. It is possible to get this one in O(n) time and O(1) space. The intuition is: you know the length of the list of ids. If you find a number which is bigger than the size of the list, you know that the id you are looking for is smaller than the number of items in the list. If all the items in the list are smaller or equal to the number of items, then you know that the smallest available id is one more than the size of the list. Not to give the answer out, based on this intuition, you'll find the solution with aforementioned complexity.