Java AC solution with Bitset and efficient get() + comments


  • 18

    The idea is to use java's bitset and use smallestFreeIndex/max to keep track of the limit.
    Also, by keeping track of the updated smallestFreeIndex all the time, the run time of get()
    is spared from scanning the entire bitset every time.

    public class PhoneDirectory {
    
        BitSet bitset;
        int max; // max limit allowed
        int smallestFreeIndex; // current smallest index of the free bit
    
        public PhoneDirectory(int maxNumbers) {
            this.bitset = new BitSet(maxNumbers);
            this.max = maxNumbers;
        }
    
        public int get() {
            // handle bitset fully allocated
            if(smallestFreeIndex == max) {
                return -1;
            }
            int num = smallestFreeIndex;
            bitset.set(smallestFreeIndex);
            //Only scan for the next free bit, from the previously known smallest free index
            smallestFreeIndex = bitset.nextClearBit(smallestFreeIndex);
            return num;
        }
    
        public boolean check(int number) {
            return bitset.get(number) == false;
        }
    
        public void release(int number) {
            //handle release of unallocated ones
            if(bitset.get(number) == false)
                return;
            bitset.clear(number);
            if(number < smallestFreeIndex) {
                smallestFreeIndex = number;
            }
        }
    }
    

  • 2

    Cool! I was also using bits approach but I didn't know about Bitset before, and I took pains to write my own solution. It looks much easier to make use of this tool! I'm gonna read its apis. Thanks!


  • 4

    @johnyrufus16 said in Java AC solution with Bitset and efficient get() + comments:

    smallestFreeIndex = bitset.nextClearBit(smallestFreeIndex);

    Does nextClearBit() cost O(N)?


  • 0

    What is the initial value of "smallestFreeIndex"?


  • 1
    R

    I agree with yubad2000. If nextClearBit is O(N) then this solution is not very efficient.
    Instead, you can use a min-heap where you add the released numbers, and get the next available number in O(logN)


  • 1
    S

    smallestFreeIndex is unnecessary:

     public int get() {
            int index = bitset.nextClearBit(0);
            if (index>max-1) return -1;
            bitset.set(index);
            return index;
        }
    

Log in to reply
 

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