Java two arrays solution 320 ms, O(1) for each operation.


  • 2

    The key idea is to cache and reuse the released numbers.
    Using a boolean array to indicate which numbers are used instead of using Set.
    Another array is served as a "stack" to cache the released numbers.
    The logic of my design is to give out all the numbers during the first round and then "recycle" from the stack afterward.

    public class PhoneDirectory {
        /** Initialize your data structure here
            @param maxNumbers - The maximum numbers that can be stored in the phone directory. */
        int max;
        int size;
        int cache_idx;
        int[] cache;
        boolean[] used;
        int count;
        public PhoneDirectory(int maxNumbers) {
            max = maxNumbers;
            size = 0;
            count = 0;
            used = new boolean[max];
            cache = new int[max];
            cache_idx = -1;
        }
        
        /** Provide a number which is not assigned to anyone.
            @return - Return an available number. Return -1 if none is available. */
        public int get() {
            int ret=-1;
            if ( count >= max ) return ret;
            if (size < max) {
                ret = size++;
            } else {
                ret = cache[cache_idx--];
            }
            used[ret]=true;
            count++;
            return ret;
        }
        
        /** Check if a number is available or not. */
        public boolean check(int number) {
            return ! used[number];
        }
        
        /** Recycle or release a number. */
        public void release(int number) {
            if (number < max && ! check(number) ){
                cache[++cache_idx]=number;
                used[number] = false;
                count--;
            }
        }
    }
    

  • 0

    I don't think the constructor is O(1). I tried this test:

    class Test {
        public static void main(String[] args) throws Exception {
            for (int n = 1 << 20; n > 0; n += n) {
                System.gc();
                long t0 = System.currentTimeMillis();
                int[] a = new int[n];
                long t = System.currentTimeMillis() - t0;
                System.out.println("new int[" + n + "]: " + t + " ms");
            }
        }
    }
    

    Here's the output:

    new int[1048576]: 0 ms
    new int[2097152]: 0 ms
    new int[4194304]: 0 ms
    new int[8388608]: 0 ms
    new int[16777216]: 25 ms
    new int[33554432]: 28 ms
    new int[67108864]: 31 ms
    new int[134217728]: 62 ms
    new int[268435456]: 123 ms
    new int[536870912]: 223 ms
    new int[1073741824]: 447 ms
    

    As expected, allocating and initializing arrays appears to take linear time. And since your constructor does that, it's not O(1).


  • 0

    @StefanPochmann

    How about the following code?
    Use LinkedHashSet to replace the two arrays.
    The construction time should be O(1) and the rest of operation is O(1) as well.
    However, the AC time was 668 ms, which is double than using arrays.

    public class PhoneDirectory {
    
        /** Initialize your data structure here
            @param maxNumbers - The maximum numbers that can be stored in the phone directory. */
        int max;
        LinkedHashSet<Integer> set;
        int size;
        int count;
        public PhoneDirectory(int maxNumbers) {
            max = maxNumbers;
            set = new LinkedHashSet<Integer>();
            size = 0;
            count = 0;
        }
        
        /** Provide a number which is not assigned to anyone.
            @return - Return an available number. Return -1 if none is available. */
        public int get() {
            int ret=-1;
            if ( count >= max ) return ret;
            if (size < max) {
                ret = size++;
            } else {
                ret = set.iterator().next();
            }
            set.remove(ret);
            count++;
            return ret;
        }
        
        /** Check if a number is available or not. */
        public boolean check(int number) {
            if (number < max && number >= size) return true;
            return set.contains(number);
        }
        
        /** Recycle or release a number. */
        public void release(int number) {
            if (number < max && ! check(number) ){
                set.add(number);
                count--;
            }
        }
    }
    

  • 0

    @StefanPochmann
    Another version, using LinkedList and Set separately.
    Initially, the construction should be O(1) as well.
    The AC time was 546 ms. Still slower than using two arrays.

    public class PhoneDirectory {
    
        /** Initialize your data structure here
            @param maxNumbers - The maximum numbers that can be stored in the phone directory. */
        int max;
        LinkedList<Integer> cache;
        Set<Integer> available;
        int size;
        int count;
        public PhoneDirectory(int maxNumbers) {
            max = maxNumbers;
            cache = new LinkedList<Integer>();
            available = new HashSet<Integer>(); 
            size = 0;
            count = 0;
        }
        
        /** Provide a number which is not assigned to anyone.
            @return - Return an available number. Return -1 if none is available. */
        public int get() {
            int ret=-1;
            if ( count >= max ) return ret;
            if (size < max) {
                ret = size++;
            } else {
                ret = cache.pollFirst();
            }
            available.remove(ret);
            count++;
            return ret;
        }
        
        /** Check if a number is available or not. */
        public boolean check(int number) {
            if (number < max && number >= size) return true;
            return available.contains(number);
        }
        
        /** Recycle or release a number. */
        public void release(int number) {
            if (number < max && ! check(number) ){
                available.add(number);
                cache.add(number);
                count--;
            }
        }
    }
    

  • 1

    Yeah, I agree with O(1) for those. Might be good to say what count and size mean.

    Here's one of mine, I submitted a few times, results were 571, 499, 546, MLE, 626, 604, MLE, 579.

    Apparently HashSet is actually implemented with a HashMap, so I used that directly. Variable future represents the never-gotten numbers 0 to future - 1. Other available numbers are stored both in list and map.

    public class PhoneDirectory {
    
        public PhoneDirectory(int maxNumbers) {
            future = maxNumbers;
        }
        
        public int get() {
            return future > 0 ? --future :
                   list.isEmpty() ? -1 :
                   map.remove(list.remove(list.size() - 1));
        }
        
        public boolean check(int number) {
            return number < future || map.containsKey(number);
        }
        
        public void release(int number) {
            if (!check(number)) {
                list.add(number);
                map.put(number, number);
            }
        }
        
        private int future;
        private ArrayList<Integer> list = new ArrayList<>();
        private Map<Integer, Integer> map = new HashMap<>();
    }
    

Log in to reply
 

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