Simple Solution Based on Set


  • 0
    A

    Keep a Set that always contains the free numbers

    1. Initially every number is free, so add them all to Set
    2. On get operation, use an Iterator to pick a free number from the Set. Then, remove this number from the Set and return
    3. On check operation, just check if the input number is present in the Set or not
    4. On release operation, add the input number to the Set
    class PhoneDirectory {
    
        /** Initialize your data structure here
            @param maxNumbers - The maximum numbers that can be stored in the phone directory. */
        
        Set<Integer> freeNums = new HashSet<Integer>();
        public PhoneDirectory(int maxNumbers) {
                
            for(int i=0;i<maxNumbers; i++)
                freeNums.add(i);
        }
        
        /** Provide a number which is not assigned to anyone.
            @return - Return an available number. Return -1 if none is available. */
        public int get() {
            
            Iterator<Integer> it = freeNums.iterator();
            if(it.hasNext())
            {
                int n = it.next();
                freeNums.remove(n);
                return n;
            }
            
            return -1;
        }
        
        /** Check if a number is available or not. */
        public boolean check(int number) {
            
            return freeNums.contains(number);
        }
        
        /** Recycle or release a number. */
        public void release(int number) {
            
            freeNums.add(number);
        }
    }
    

    Space Complexity : O(n)
    Time Complexity : O(n) for initializing and O(1) thereafter for all operations


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.