# Question

Formatted question description: https://leetcode.ca/all/379.html

Design a phone directory that initially has maxNumbers empty slots that can store numbers. The directory should store numbers, check if a certain slot is empty or not, and empty a given slot.

Implement the PhoneDirectory class:

• PhoneDirectory(int maxNumbers) Initializes the phone directory with the number of available slots maxNumbers.
• int get() Provides a number that is not assigned to anyone. Returns -1 if no number is available.
• bool check(int number) Returns true if the slot number is available and false otherwise.
• void release(int number) Recycles or releases the slot number.

Example 1:

Input
["PhoneDirectory", "get", "get", "check", "get", "check", "release", "check"]
[[3], [], [], [2], [], [2], [2], [2]]
Output
[null, 0, 1, true, 2, false, null, true]

Explanation
PhoneDirectory phoneDirectory = new PhoneDirectory(3);
phoneDirectory.get();      // It can return any available phone number. Here we assume it returns 0.
phoneDirectory.get();      // Assume it returns 1.
phoneDirectory.check(2);   // The number 2 is available, so return true.
phoneDirectory.get();      // It returns 2, the only number that is left.
phoneDirectory.check(2);   // The number 2 is no longer available, so return false.
phoneDirectory.release(2); // Release number 2 back to the pool.
phoneDirectory.check(2);   // Number 2 is available again, return true.


Constraints:

• 1 <= maxNumbers <= 104
• 0 <= number < maxNumbers
• At most 2 * 104 calls will be made to get, check, and release.

# Algorithm

To allocate numbers, an array nums is essential for storing all potential numbers. It’s important to initialize this array with distinct numbers. Additionally, use a parallel array used of the same length to track whether a number at a specific position has been allocated. A variable idx will indicate the currently allocated position.

### get() Function:

• No Number Available: If idx is less than 0, it signifies that no number can be allocated, so return -1.
• Allocate Number: Otherwise, retrieve nums[idx], mark the number as used (set used[idx] to true), decrement idx by 1, and return the fetched number.

### check() Function:

• Simply verify if the corresponding entry in used is false (indicating availability).

### release() Function:

• If the number is already unallocated (marked as false in used), return immediately.
• If the number is allocated (true in used), increment idx by 1, reassign the number to nums[idx], and mark it as unallocated (false) in used.

# Alternative Lightweight Algorithm

A phone directory can also be implemented using an array in tandem with a queue. The array tracks the availability of numbers, while the queue holds unassigned numbers.

### Initialization:

• In the constructor, initialize the array (all elements as true) and the queue (filled with numbers from 0 to maxNumbers - 1).

### get Operation:

• Queue Empty: If the queue is empty (no available numbers), return -1.
• Allocate Number: If not, dequeue a number, set its corresponding array status to false (indicating allocation), and return this number.

### check Operation:

• Directly inspect the array to determine if the number is available. Return false immediately if the number is out of bounds (less than 0 or greater or equal to maxNumbers).

### release Operation:

• Avoid Redundancy: Only release a number if it’s currently in use. If it’s already available, no action is needed.
• Releasing: If the number is in use, offer it back to the queue and update its status in the array to true.

# Code

• class PhoneDirectory {
int maxNumbers;
boolean[] available;
Queue<Integer> unused;

/** Initialize your data structure here
@param maxNumbers - The maximum numbers that can be stored in the phone directory. */
public PhoneDirectory(int maxNumbers) {
this.maxNumbers = maxNumbers;
available = new boolean[maxNumbers];
for (int i = 0; i < maxNumbers; i++) {
available[i] = true;
unused.offer(i);
}
}

/** Provide a number which is not assigned to anyone.
@return - Return an available number. Return -1 if none is available. */
public int get() {
if (unused.isEmpty())
return -1;
else {
int next = unused.poll();
available[next] = false;
return next;
}
}

/** Check if a number is available or not. */
public boolean check(int number) {
if (number < 0 || number >= maxNumbers)
return false;
else
return available[number];
}

/** Recycle or release a number. */
public void release(int number) {
if (!available[number]) {
unused.offer(number);
available[number] = true;
}
}
}

/**
* Your PhoneDirectory object will be instantiated and called as such:
* PhoneDirectory obj = new PhoneDirectory(maxNumbers);
* int param_1 = obj.get();
* boolean param_2 = obj.check(number);
* obj.release(number);
*/

//////

import java.util.HashSet;

public class Design_Phone_Directory {
public class PhoneDirectory {

int max;
HashSet<Integer> set; // assigned number

/**
* Initialize your data structure here
*
* @param maxNumbers - The maximum numbers that can be stored in the phone directory.
*/
public PhoneDirectory(int maxNumbers) {
set = new HashSet<Integer>();
for (int i = 0; i < maxNumbers; i++) {
queue.offer(i);
}
max = maxNumbers - 1;
}

/**
* Provide a number which is not assigned to anyone.
*
* @return - Return an available number. Return -1 if none is available.
*/
public int get() {
if (queue.isEmpty()) {
return -1;
}

int e = queue.poll();
return e;
}

/**
* Check if a number is available or not.
*/
public boolean check(int number) {
return !set.contains(number) && number <= max;
}

/**
* Recycle or release a number.
*/
public void release(int number) {
if (set.contains(number)) {
set.remove(number);
queue.offer(number);
}
}
}
}

//////

class PhoneDirectory {

private boolean[] provided;

/**
@param maxNumbers - The maximum numbers that can be stored in the phone directory.
*/
public PhoneDirectory(int maxNumbers) {
provided = new boolean[maxNumbers];
}

/**
Provide a number which is not assigned to anyone.
@return - Return an available number. Return -1 if none is available.
*/
public int get() {
for (int i = 0; i < provided.length; ++i) {
if (!provided[i]) {
provided[i] = true;
return i;
}
}
return -1;
}

/** Check if a number is available or not. */
public boolean check(int number) {
return !provided[number];
}

/** Recycle or release a number. */
public void release(int number) {
provided[number] = false;
}
}

/**
* Your PhoneDirectory object will be instantiated and called as such:
* PhoneDirectory obj = new PhoneDirectory(maxNumbers);
* int param_1 = obj.get();
* boolean param_2 = obj.check(number);
* obj.release(number);
*/

• // OJ: https://leetcode.com/problems/design-phone-directory/
// Time: O(1)
// Space: O(N)
class PhoneDirectory {
private:
unordered_set<int> pool;
public:
PhoneDirectory(int maxNumbers) {
while (maxNumbers--) pool.insert(maxNumbers);
}
int get() {
if (pool.empty()) return -1;
int ans = *pool.begin();
pool.erase(pool.begin());
return ans;
}
bool check(int number) {
return pool.find(number) != pool.end();
}
void release(int number) {
if (check(number)) return;
pool.insert(number);
}
};

• from collections import deque

class PhoneDirectory(object):

def __init__(self, maxNumbers):
"""
@param maxNumbers - The maximum numbers that can be stored in the phone directory.
:type maxNumbers: int
"""
self.available = [True] * maxNumbers
# use extra space deque, to get faster get() call
self.q = deque([i for i in range(0, maxNumbers)])

def get(self):
"""
Provide a number which is not assigned to anyone.
@return - Return an available number. Return -1 if none is available.
:rtype: int
"""
if self.q:
self.available[self.q[0]] = False
return self.q.popleft()
return -1

def check(self, number):
"""
Check if a number is available or not.
:type number: int
:rtype: bool
"""
return self.available[number]

def release(self, number):
"""
Recycle or release a number.
:type number: int
:rtype: void
"""
if not self.available[number]:
self.available[number] = True
self.q.append(number)

# Your PhoneDirectory object will be instantiated and called as such:
# obj = PhoneDirectory(maxNumbers)
# param_1 = obj.get()
# param_2 = obj.check(number)
# obj.release(number)