Problem statement

https://leetcode.com/problems/design-phone-directory/

Solution

One of the solutions is to keep set of avaliable numbers. When we asked to get number, just return any number from this set, to check availability of number we check if it is in our set and to release number we just need to add it to set. Time complexity is $(1)$, however space complexity is $O(n)$, where $n$ is range of our numbers.

We can optimize this for memory: let us keep current number of numbers used, and extend it if it becomes full. For example self.max_curr = 5 and self.avaliable = [2, 4] means that numbers 1, 3, 5 are occupied. If we want to add new number we fill 2: remove it from set, then 4. If we want to add more, but self.available set is empty, just add $1$ to our self.max_curr, so it is equal to $6$ now.

Complexity

Time complexity is still $O(1)$ for all operations and space complexity is $O(k)$, where $k$ is the largest number of phones used at one moment of time.

Code

class PhoneDirectory:
    def __init__(self, maxNumbers):
        self.max_nums = maxNumbers
        self.max_curr = 0
        self.avaliable = set()
        
    def get(self):
        if len(self.avaliable) == 0:
            if self.max_curr == self.max_nums:
                return -1
            out = self.max_curr
            self.max_curr += 1
        else:
            out = self.avaliable.pop()
            
        return out
        
    def check(self, number):
        return number in self.avaliable or number >= self.max_curr    

    def release(self, number):
        print(self.max_curr, self.avaliable)
        if number < self.max_curr:
            self.avaliable.add(number)

Remark

It can be solved with linked lists as well.