C# - no initialization - all operations O(1) - use counter and stack


  • 0

    seems many solutions are using a hash table or set and initializing the set with all available numbers. In fact you can avoid any initialization cost, you only need to store the numbers after they are recycled back to the collection, not initially.

    First use numbers from a simple counter, decrementing each time one is issued, as numbers are recycled back add them to a stack. Once the counter runs past zero start pulling from the stack. And if the stack is empty you have none to issue. Also note that a boolean array is faster lookup than a Set and if you expect to be using most of the values it's probably better memory wise as well.

    public class PhoneDirectory 
    {
        int counter = 0;
        Stack<int> stack = null;
        bool[] used = null;
        
        public PhoneDirectory(int maxNumbers) 
        {
            counter = maxNumbers - 1;
            stack = new Stack<int>();
            used = new bool[maxNumbers];
        }
        
        public int Get() 
        {
            int x = -1;
            if (counter >= 0) x = counter--; 
            else if (stack.Count > 0) x = stack.Pop();
            
            if (x != -1) used[x] = true;
            return x;
        }
        
        public bool Check(int number) 
        {
            return number >= 0 && number < used.Length && !used[number];
        }
        
        public void Release(int number) 
        {
            if (number >= 0 && number < used.Length && used[number])
            {
                used[number] = false;
                stack.Push(number);
            }
        }
    }
    

Log in to reply
 

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