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

• 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--;
}
}
}
``````

• 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).

• @StefanPochmann

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;
int size;
int count;
public PhoneDirectory(int maxNumbers) {
max = maxNumbers;
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) ){
count--;
}
}
}
``````

• @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;
Set<Integer> available;
int size;
int count;
public PhoneDirectory(int maxNumbers) {
max = maxNumbers;
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) ){
count--;
}
}
}
``````

• 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)) {