Leetcode 379. Design Phone Directory
Problem Explanation
The problem requires us to design a phone directory to store and retrieve phone numbers. The phone directory must support the following operations:
-
get()
: This operation should provide an available phone number which is not assigned to anyone. It should return -1 if no phone numbers are available. -
check(int number)
: This operation should check if a phone number is available or not. It should return true if the number is available, otherwise false. -
release(int number)
: This operation should recycle or release a phone number, making it available again in the phone directory.
The directory will be initialized with a maximum number of phone numbers and each phone number will be a digit starting from 0 up to maxNumbers
.
Solution Approach
In our solution, we are maintaining an array called next
of size maxNumbers
which stores the next available number for the directory. Initially all numbers are available, hence for each index i
, next[i]
is i+1
. Once numbers start to be assigned and released, this array will dynamically update the next available numbers.
Our current available number is stored in the variable number
. Initially it is zero.
-
When
get()
is called, we check if our current number is available (next[number] != -1
), if not, we return -1 as no numbers are available. If it is available, we return the number, update our current number tonext[number]
and setnext[our returned number]
to -1, indicating it is not available anymore. -
For
check(int number)
, we simply returnnext[number] != -1
, i.e., whether the number is available or not. -
For
release(int number)
, we first check if the number is already available, then do nothing. If not, we make it available by settingnext[number]
to our current number and then update our current number tonumber
.
Python
1 2python 3class PhoneDirectory: 4 def __init__(self, maxNumbers): 5 self.next = [i + 1 for i in range(maxNumbers)] # initialize next array 6 self.next.append(-1) # append -1 at the end 7 self.number = 0 # current number 8 9 def get(self): 10 if self.next[self.number] == -1: 11 return -1 12 ret = self.number 13 self.number = self.next[self.number] 14 self.next[ret] = -1 15 return ret 16 17 def check(self, number): 18 return self.next[number] != -1 19 20 def release(self, number): 21 if self.next[number] != -1: 22 return 23 self.next[number] = self.number 24 self.number = number
Java
1
2java
3public class PhoneDirectory {
4 private int[] next;
5 private int number;
6
7 public PhoneDirectory(int maxNumbers) {
8 next = new int[maxNumbers];
9 for (int i = 0; i < maxNumbers; i++) {
10 next[i] = (i + 1) % maxNumbers;
11 }
12 number = 0;
13 }
14
15 public int get() {
16 if (next[number] == -1) return -1;
17 int ans = number;
18 number = next[number];
19 next[ans] = -1;
20 return ans;
21 }
22
23 public boolean check(int number) {
24 return next[number] != -1;
25 }
26
27 public void release(int number) {
28 if (next[number] != -1) return;
29 next[number] = this.number;
30 this.number = number;
31 }
32}
JavaScript
1
2javascript
3class PhoneDirectory {
4 constructor(maxNumbers) {
5 this.next = new Array(maxNumbers).fill().map((_, idx) => idx + 1);
6 this.next.push(-1);
7 this.number = 0;
8 }
9
10 get() {
11 if (this.next[this.number] === -1) return -1;
12 const ret = this.number;
13 this.number = this.next[this.number];
14 this.next[ret] = -1;
15 return ret;
16 }
17
18 check(number) {
19 return this.next[number] !== -1;
20 }
21
22 release(number) {
23 if (this.next[number] !== -1) return;
24 this.next[number] = this.number;
25 this.number = number;
26 }
27}
C++
1
2C++
3class PhoneDirectory {
4 vector<int> next;
5 int number;
6
7public:
8 PhoneDirectory(int maxNumbers) {
9 next = vector<int>(maxNumbers);
10 for (int i = 0; i < maxNumbers - 1; ++i)
11 next[i] = i + 1;
12 next.back() = 0;
13 number = 0;
14 }
15
16 int get() {
17 if (next[number] == -1)
18 return -1;
19 const int ans = number;
20 number = next[number];
21 next[ans] = -1; // Mark as used
22 return ans;
23 }
24
25 bool check(int number) {
26 return next[number] != -1;
27 }
28
29 void release(int number) {
30 if (next[number] != -1)
31 return;
32 next[number] = this->number;
33 this->number = number;
34 }
35};
C#
1 2csharp 3public class PhoneDirectory { 4 private int[] next; 5 private int number; 6 7 public PhoneDirectory(int maxNumbers) { 8 next = new int[maxNumbers]; 9 for (int i = 0; i < maxNumbers; i++) 10 next[i] = (i + 1) % maxNumbers; 11 number = 0; 12 } 13 14 public int Get() { 15 if (next[number] == -1) return -1; 16 int ans = number; 17 number = next[number]; 18 next[ans] = -1; 19 return ans; 20 } 21 22 public bool Check(int number) { 23 return next[number] != -1; 24 } 25 26 public void Release(int number) { 27 if (next[number] != -1) return; 28 next[number] = this.number; 29 this.number = number; 30 } 31}
These solutions have a constant time complexity due to a single array traversal. Hence they are efficient and optimal solutions for the problem.In summary, we have successfully tackled the problem using a straightforward but effective approach. The most complex part is managing the availability of numbers in the phone directory. We accomplished this by maintaining an array which keeps track of the next available number, and accordingly updating that array whenever a number is fetched or released. This approach ensures that we can operate in constant time, making it very efficient even for large inputs. We have provided the implementation details in multiple widely-used programming languages, demonstrating how the core idea can be applied irrespective of the specific language syntax.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.