All O(1) operations but still getting TLE :(


  • 0
    A

    My methodology is to use two LinkedLists, one for storing assignedNumbers, and one for storing free Numbers. Also using a hashtable to store the index of a number in assignedNumbers. All operations are O(1) but I'm still getting a TLE :/

    public class PhoneDirectory {

    int maxNumbers;
    LinkedList assignedNumbers;
    LinkedList freeNumbers;
    
    HashMap<Integer, Integer> pos;
    public PhoneDirectory(int maxNumbers) {
        this.maxNumbers = maxNumbers;
        assignedNumbers = new LinkedList<Integer>();
        freeNumbers = new LinkedList<Integer>();
        pos = new HashMap<Integer, Integer>();
    
    }
    
    public int get() {
        if(freeNumbers.size() > 0) {
            int number = (Integer)freeNumbers.pollFirst();
            assignedNumbers.add(number);
            pos.put(number, assignedNumbers.size()-1);
            return number;
        } else {
            if(assignedNumbers.size() < maxNumbers) {
                int number = assignedNumbers.size();
                assignedNumbers.add(number);
                pos.put(number, assignedNumbers.size()-1);
                return number;
            } else {
                return -1;
            }
        }
    }
    
    public boolean check(int number) {
        return !pos.containsKey(number);
    }
    
    public void release(int number) {
        if(pos.containsKey(number)) {
            int index = pos.get(number);
            
            if(index == assignedNumbers.size()-1) {
                assignedNumbers.remove(index);
            } else {
                int lastNumber = (Integer)assignedNumbers.pollLast();
                assignedNumbers.set(index, lastNumber);
                pos.put(lastNumber, pos.get(number));
            }
            pos.remove(number);
            freeNumbers.add(number);
        }
    }
    

    }


  • 0

    How do you think assignedNumbers.set(index, lastNumber); is O(1)?


  • 0
    A

    Didn't think of that ... thanks :p


Log in to reply
 

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