Problem editorial

Design Phone Directory

MediumDesign PatternsArrayHash TableLinked List

Editorial

Core insight

Design Phone Directory · Design Patterns

Core Insight for Design Phone Directory

The key intuition for solving LeetCode 379 efficiently is recognizing that we have two distinct requirements that usually require different data structures:

Fast Allocation: We need to grab any available number quickly. A Queue (or Stack) is ideal for this because poll() or pop() is $O(1)$ .
Fast Lookup/Validation: We need to check if a specific number is available or if a number being released is already free (to avoid duplicates). A Boolean Array or HashSet is ideal for this because random access/lookup is $O(1)$ .

By maintaining both structures simultaneously, we can achieve $O(1)$ for all operations. The Queue acts as a reservoir of "ready-to-use" numbers, while the Boolean Array acts as the "source of truth" regarding the state of every number.

Visual Description: Imagine a boolean array of size maxNumbers initialized to true (all available). Alongside it, a Queue is filled with integers $0$ to maxNumbers - 1.

When get() is called, we remove the head of the Queue (say, value X) and set index X in the array to false.
When check(Y) is called, we simply read the value at index Y in the array.
When release(Z) is called, we check index Z. If it is false (assigned), we set it to true and push Z back into the Queue. If it is already true, we do nothing to prevent Z from appearing in the Queue twice.

Deep dive

Full breakdown

Full reasoning, pitfalls, and implementation flow

LeetCode 379: Design Phone Directory Solution & Explanation

Problem Overview

TL;DR: The optimal solution combines a Queue to store available numbers for $O(1)$ retrieval and a Boolean Array (or HashSet) to track the status of every number for $O(1)$ lookups and duplicate prevention.

The LeetCode 379 problem, "Design Phone Directory," asks us to implement a system that manages a pool of phone numbers within a range $[0, \text{maxNumbers} - 1]$ . The system must support three specific operations: assigning a number (get), checking if a number is free (check), and recycling a number (release). The primary challenge is to implement these operations efficiently, ideally in constant time, to handle up to $2 \times 10^4$ calls.

Brute Force Approach for Design Phone Directory

A naive approach might involve storing the state of the directory using a simple list or iterating through numbers on demand.

Storage: Keep a list of all currently assigned numbers.
get(): Iterate from $0$ to $\text{maxNumbers} - 1$ . For each number, scan the list of assigned numbers to see if it is taken. If not, add it to the list and return it.
check(number): Scan the list of assigned numbers to see if number exists.
release(number): Search for number in the assigned list and remove it.

python

1# Pseudo-code for Brute Force
2class PhoneDirectory:
3    def __init__(self, maxNumbers):
4        self.max = maxNumbers
5        self.assigned = [] # List of assigned numbers
6
7    def get(self):
8        # O(N^2) potentially if implemented poorly, or O(N) with optimal search
9        for i in range(self.max):
10            if i not in self.assigned: 
11                self.assigned.append(i)
12                return i
13        return -1
14
15    def check(self, number):
16        # O(N) scan
17        return number not in self.assigned
18
19    def release(self, number):
20        # O(N) to find and remove
21        if number in self.assigned:
22            self.assigned.remove(number)

Why this fails: The time complexity for get, check, and release becomes $O(N)$ (where $N$ is the number of currently assigned numbers) because searching or removing from an unsorted list requires linear time. With $2 \times 10^4$ operations, an $O(N)$ implementation results in an overall complexity of roughly $O(K \times N)$ (where $K$ is the number of operations). In the worst case, this approaches $4 \times 10^8$ operations, which is inefficient and risks a Time Limit Exceeded (TLE) or performs poorly in a system design context where latency is critical.

Algorithm Strategy: Design Patterns

We will implement the PhoneDirectory class using two primary data structures:

availableQueue: A Queue (or LinkedList) storing all numbers that are currently free and ready to be assigned.
isAvailable: A Boolean Array (or HashSet) of size maxNumbers. isAvailable[i] is true if number i is free, and false otherwise.

Initialization (PhoneDirectory):

Create the queue and fill it with numbers $0$ to $\text{maxNumbers} - 1$ .
Create the boolean array and set all entries to true.

Allocation (get):

Check if the availableQueue is empty. If so, return -1.
If not empty, remove the front element x from availableQueue.
Update isAvailable[x] to false.
Return x.

Status Check (check):

Return the value of isAvailable[number]. This provides an instant status report.

Deallocation (release):

Check isAvailable[number].
If it is already true, the number is already in the pool. Do nothing (this prevents duplicate entries in the queue).
If it is false, set isAvailable[number] to true and add number back to availableQueue.

Execution Flow

Let's trace the operations with maxNumbers = 3.

Initialization:
- availableQueue: [0, 1, 2]
- isAvailable: [true, true, true]
Call get():
- Queue is not empty. Poll 0.
- availableQueue: [1, 2]
- isAvailable: [false, true, true]
- Return 0.
Call get():
- Queue is not empty. Poll 1.
- availableQueue: [2]
- isAvailable: [false, false, true]
- Return 1.
Call check(1):
- Look up isAvailable[1]. It is false.
- Return false.
Call release(0):
- Look up isAvailable[0]. It is false (meaning it is currently assigned).
- Set isAvailable[0] to true.
- Add 0 to Queue.
- availableQueue: [2, 0]
- isAvailable: [true, false, true]
Call release(0) again (Redundant release):
- Look up isAvailable[0]. It is true.
- Do nothing. (Crucial step to maintain integrity).

Proof of Correctness

The correctness relies on the synchronization between the Queue and the Boolean Array.

Completeness: The Queue is initialized with all numbers, ensuring every number can be issued.
Uniqueness: The isAvailable check inside release() prevents a number from being added to the Queue more than once. This guarantees that get() never issues the same number to two different users simultaneously.
Validity: The isAvailable array is updated atomically with Queue operations. A number is only marked "assigned" (false) when it leaves the Queue, and only marked "available" (true) when it enters the Queue.

Pattern Reuse Notes

The Design (General/Specific) pattern used here—combining data structures to optimize specific operations—is fundamental for many system design-style algorithm problems.

LeetCode 146: LRU Cache: Combines a Hash Map (for $O(1)$ access) with a Doubly Linked List (for $O(1)$ ordering updates).
LeetCode 155: Min Stack: Combines two stacks (one for values, one for minimums) to achieve $O(1)$ minimum retrieval.
LeetCode 225: Implement Stack using Queues: Manipulates Queues to mimic LIFO behavior.
LeetCode 232: Implement Queue using Stacks: Manipulates Stacks to mimic FIFO behavior.

In all these cases, the core task is identifying the bottleneck of a single data structure and augmenting it with a second one to satisfy constraints.

Feynman coach · Before you peek at the code

Can you explain the core insight in your own words?

If you can explain it before reading code, you’re far more likely to recall it under interview pressure.

Loading your attempt…

Reference Implementation

C++ Solution for LeetCode 379

cpp

1#include <vector>
2#include <queue>
3
4class PhoneDirectory {
5private:
6    std::queue<int> availableQueue;
7    std::vector<bool> isAvailable;
8    int maxLimit;
9
10public:
11    /** Initialize your data structure here
12        @param maxNumbers - The maximum numbers that can be stored in the phone directory. */
13    PhoneDirectory(int maxNumbers) {
14        maxLimit = maxNumbers;
15        isAvailable.resize(maxNumbers, true);
16        for (int i = 0; i < maxNumbers; ++i) {
17            availableQueue.push(i);
18        }
19    }
20    
21    /** Provide a number which is not assigned to anyone.
22        @return - Return an available number. Return -1 if none is available. */
23    int get() {
24        if (availableQueue.empty()) {
25            return -1;
26        }
27        
28        int number = availableQueue.front();
29        availableQueue.pop();
30        
31        // Mark as assigned
32        isAvailable[number] = false;
33        
34        return number;
35    }
36    
37    /** Check if a number is available or not. */
38    bool check(int number) {
39        if (number < 0 || number >= maxLimit) return false;
40        return isAvailable[number];
41    }
42    
43    /** Recycle or release a number. */
44    void release(int number) {
45        if (number < 0 || number >= maxLimit) return;
46        
47        // Only release if it's currently assigned (false)
48        if (!isAvailable[number]) {
49            isAvailable[number] = true;
50            availableQueue.push(number);
51        }
52    }
53};

Java Solution for LeetCode 379

java

1import java.util.LinkedList;
2import java.util.Queue;
3
4class PhoneDirectory {
5    private Queue<Integer> availableQueue;
6    private boolean[] isAvailable;
7    private int maxLimit;
8
9    public PhoneDirectory(int maxNumbers) {
10        this.maxLimit = maxNumbers;
11        this.availableQueue = new LinkedList<>();
12        this.isAvailable = new boolean[maxNumbers];
13        
14        // Initialize all numbers as available
15        for (int i = 0; i < maxNumbers; i++) {
16            availableQueue.offer(i);
17            isAvailable[i] = true;
18        }
19    }
20    
21    public int get() {
22        if (availableQueue.isEmpty()) {
23            return -1;
24        }
25        
26        int number = availableQueue.poll();
27        isAvailable[number] = false; // Mark as assigned
28        return number;
29    }
30    
31    public boolean check(int number) {
32        if (number < 0 || number >= maxLimit) return false;
33        return isAvailable[number];
34    }
35    
36    public void release(int number) {
37        if (number < 0 || number >= maxLimit) return;
38        
39        // If the number is currently assigned (false), release it
40        if (!isAvailable[number]) {
41            isAvailable[number] = true;
42            availableQueue.offer(number);
43        }
44    }
45}

Python Solution for LeetCode 379

python

1from collections import deque
2
3class PhoneDirectory:
4
5    def __init__(self, maxNumbers: int):
6        self.max_limit = maxNumbers
7        # Queue stores available numbers for O(1) retrieval
8        self.available_queue = deque(range(maxNumbers))
9        # Boolean array stores status for O(1) lookup
10        self.is_available = [True] * maxNumbers
11
12    def get(self) -> int:
13        if not self.available_queue:
14            return -1
15        
16        number = self.available_queue.popleft()
17        self.is_available[number] = False
18        return number
19
20    def check(self, number: int) -> bool:
21        if number < 0 or number >= self.max_limit:
22            return False
23        return self.is_available[number]
24
25    def release(self, number: int) -> None:
26        if number < 0 or number >= self.max_limit:
27            return
28            
29        # Only add back if it is currently assigned (False)
30        if not self.is_available[number]:
31            self.is_available[number] = True
32            self.available_queue.append(number)

AI Coach Insight

For Design Phone Directory, focus on explaining why the structure works, not just naming Design Patterns.

Complexity Analysis

Time Complexity:
- Constructor: $O(N)$ where $N$ is maxNumbers, to fill the queue and array.
- get(): $O(1)$ . Polling from a queue and updating an array index are constant time operations.
- check(): $O(1)$ . Array access is constant time.
- release(): $O(1)$ . Array access and queue insertion are constant time.
Space Complexity: $O(N)$ . We store $N$ integers in the queue (initially) and $N$ booleans in the array. This is the minimum space required to track the state of $N$ items explicitly.

Related Patterns

Pattern: Design Patterns
Subpattern: Design (General/Specific)

This problem falls under the Design pattern because it requires combining standard data structures (Queues, Sets, Arrays) to satisfy specific time complexity constraints ( $O(1)$ ) for a set of defined interface methods.

Common Mistakes & FAQ

Why do I get duplicates in my get() calls?
- Mistake: Implementing release() without checking if the number is already available.
- Reasoning: If a user calls release(5) twice, a naive implementation might push 5 into the queue twice. Later, get() will return 5 two separate times, assigning the same number to two users.
- Consequence: Correctness failure. The isAvailable check prevents this.
Why does my solution get Time Limit Exceeded (TLE)?
- Mistake: Using a List/Array and searching linearly for available numbers in get() or using list.remove() in release().
- Reasoning: list.remove() is $O(N)$ . Searching an array for the first true value is $O(N)$ .
- Consequence: Efficiency failure. Operations must be $O(1)$ .
Why not just use a HashSet?
- Mistake: Relying solely on a HashSet of available numbers.
- Reasoning: While check and release are $O(1)$ on average, getting an arbitrary element from a HashSet (the get operation) usually requires an iterator, which isn't strictly $O(1)$ in all language implementations or might require converting to a list.
- Consequence: Potential inefficiency or messy code. The Queue + Set/Array combo is structurally cleaner for the "Producer-Consumer" nature of get.

Practise Design Phone Directory and the problems around it

Design Phone Directory is a Design Patterns problem, in the Design (General/Specific) subpattern. Once the approach above makes sense, write it yourself and then work through the neighbouring problems that reuse it.

Core insight

Design Phone Directory · Design Patterns

Core Insight for Design Phone Directory

The key intuition for solving LeetCode 379 efficiently is recognizing that we have two distinct requirements that usually require different data structures:

Fast Allocation: We need to grab any available number quickly. A Queue (or Stack) is ideal for this because poll() or pop() is $O(1)$ .
Fast Lookup/Validation: We need to check if a specific number is available or if a number being released is already free (to avoid duplicates). A Boolean Array or HashSet is ideal for this because random access/lookup is $O(1)$ .

Visual Description: Imagine a boolean array of size maxNumbers initialized to true (all available). Alongside it, a Queue is filled with integers $0$ to maxNumbers - 1.

When get() is called, we remove the head of the Queue (say, value X) and set index X in the array to false.
When check(Y) is called, we simply read the value at index Y in the array.
When release(Z) is called, we check index Z. If it is false (assigned), we set it to true and push Z back into the Queue. If it is already true, we do nothing to prevent Z from appearing in the Queue twice.

Deep dive

Full breakdown

Full reasoning, pitfalls, and implementation flow

LeetCode 379: Design Phone Directory Solution & Explanation

Problem Overview

Brute Force Approach for Design Phone Directory

A naive approach might involve storing the state of the directory using a simple list or iterating through numbers on demand.

Storage: Keep a list of all currently assigned numbers.
get(): Iterate from $0$ to $\text{maxNumbers} - 1$ . For each number, scan the list of assigned numbers to see if it is taken. If not, add it to the list and return it.
check(number): Scan the list of assigned numbers to see if number exists.
release(number): Search for number in the assigned list and remove it.

python

1# Pseudo-code for Brute Force
2class PhoneDirectory:
3    def __init__(self, maxNumbers):
4        self.max = maxNumbers
5        self.assigned = [] # List of assigned numbers
6
7    def get(self):
8        # O(N^2) potentially if implemented poorly, or O(N) with optimal search
9        for i in range(self.max):
10            if i not in self.assigned: 
11                self.assigned.append(i)
12                return i
13        return -1
14
15    def check(self, number):
16        # O(N) scan
17        return number not in self.assigned
18
19    def release(self, number):
20        # O(N) to find and remove
21        if number in self.assigned:
22            self.assigned.remove(number)

Algorithm Strategy: Design Patterns

We will implement the PhoneDirectory class using two primary data structures:

availableQueue: A Queue (or LinkedList) storing all numbers that are currently free and ready to be assigned.
isAvailable: A Boolean Array (or HashSet) of size maxNumbers. isAvailable[i] is true if number i is free, and false otherwise.

Initialization (PhoneDirectory):

Create the queue and fill it with numbers $0$ to $\text{maxNumbers} - 1$ .
Create the boolean array and set all entries to true.

Allocation (get):

Check if the availableQueue is empty. If so, return -1.
If not empty, remove the front element x from availableQueue.
Update isAvailable[x] to false.
Return x.

Status Check (check):

Return the value of isAvailable[number]. This provides an instant status report.

Deallocation (release):

Check isAvailable[number].
If it is already true, the number is already in the pool. Do nothing (this prevents duplicate entries in the queue).
If it is false, set isAvailable[number] to true and add number back to availableQueue.

Execution Flow

Let's trace the operations with maxNumbers = 3.

Initialization:
- availableQueue: [0, 1, 2]
- isAvailable: [true, true, true]
Call get():
- Queue is not empty. Poll 0.
- availableQueue: [1, 2]
- isAvailable: [false, true, true]
- Return 0.
Call get():
- Queue is not empty. Poll 1.
- availableQueue: [2]
- isAvailable: [false, false, true]
- Return 1.
Call check(1):
- Look up isAvailable[1]. It is false.
- Return false.
Call release(0):
- Look up isAvailable[0]. It is false (meaning it is currently assigned).
- Set isAvailable[0] to true.
- Add 0 to Queue.
- availableQueue: [2, 0]
- isAvailable: [true, false, true]
Call release(0) again (Redundant release):
- Look up isAvailable[0]. It is true.
- Do nothing. (Crucial step to maintain integrity).

Proof of Correctness

The correctness relies on the synchronization between the Queue and the Boolean Array.

Completeness: The Queue is initialized with all numbers, ensuring every number can be issued.
Uniqueness: The isAvailable check inside release() prevents a number from being added to the Queue more than once. This guarantees that get() never issues the same number to two different users simultaneously.
Validity: The isAvailable array is updated atomically with Queue operations. A number is only marked "assigned" (false) when it leaves the Queue, and only marked "available" (true) when it enters the Queue.

Pattern Reuse Notes

The Design (General/Specific) pattern used here—combining data structures to optimize specific operations—is fundamental for many system design-style algorithm problems.

LeetCode 146: LRU Cache: Combines a Hash Map (for $O(1)$ access) with a Doubly Linked List (for $O(1)$ ordering updates).
LeetCode 155: Min Stack: Combines two stacks (one for values, one for minimums) to achieve $O(1)$ minimum retrieval.
LeetCode 225: Implement Stack using Queues: Manipulates Queues to mimic LIFO behavior.
LeetCode 232: Implement Queue using Stacks: Manipulates Stacks to mimic FIFO behavior.

In all these cases, the core task is identifying the bottleneck of a single data structure and augmenting it with a second one to satisfy constraints.

Feynman coach · Before you peek at the code

Can you explain the core insight in your own words?

If you can explain it before reading code, you’re far more likely to recall it under interview pressure.

Loading your attempt…

Reference Implementation

C++ Solution for LeetCode 379

cpp

1#include <vector>
2#include <queue>
3
4class PhoneDirectory {
5private:
6    std::queue<int> availableQueue;
7    std::vector<bool> isAvailable;
8    int maxLimit;
9
10public:
11    /** Initialize your data structure here
12        @param maxNumbers - The maximum numbers that can be stored in the phone directory. */
13    PhoneDirectory(int maxNumbers) {
14        maxLimit = maxNumbers;
15        isAvailable.resize(maxNumbers, true);
16        for (int i = 0; i < maxNumbers; ++i) {
17            availableQueue.push(i);
18        }
19    }
20    
21    /** Provide a number which is not assigned to anyone.
22        @return - Return an available number. Return -1 if none is available. */
23    int get() {
24        if (availableQueue.empty()) {
25            return -1;
26        }
27        
28        int number = availableQueue.front();
29        availableQueue.pop();
30        
31        // Mark as assigned
32        isAvailable[number] = false;
33        
34        return number;
35    }
36    
37    /** Check if a number is available or not. */
38    bool check(int number) {
39        if (number < 0 || number >= maxLimit) return false;
40        return isAvailable[number];
41    }
42    
43    /** Recycle or release a number. */
44    void release(int number) {
45        if (number < 0 || number >= maxLimit) return;
46        
47        // Only release if it's currently assigned (false)
48        if (!isAvailable[number]) {
49            isAvailable[number] = true;
50            availableQueue.push(number);
51        }
52    }
53};

Java Solution for LeetCode 379

java

1import java.util.LinkedList;
2import java.util.Queue;
3
4class PhoneDirectory {
5    private Queue<Integer> availableQueue;
6    private boolean[] isAvailable;
7    private int maxLimit;
8
9    public PhoneDirectory(int maxNumbers) {
10        this.maxLimit = maxNumbers;
11        this.availableQueue = new LinkedList<>();
12        this.isAvailable = new boolean[maxNumbers];
13        
14        // Initialize all numbers as available
15        for (int i = 0; i < maxNumbers; i++) {
16            availableQueue.offer(i);
17            isAvailable[i] = true;
18        }
19    }
20    
21    public int get() {
22        if (availableQueue.isEmpty()) {
23            return -1;
24        }
25        
26        int number = availableQueue.poll();
27        isAvailable[number] = false; // Mark as assigned
28        return number;
29    }
30    
31    public boolean check(int number) {
32        if (number < 0 || number >= maxLimit) return false;
33        return isAvailable[number];
34    }
35    
36    public void release(int number) {
37        if (number < 0 || number >= maxLimit) return;
38        
39        // If the number is currently assigned (false), release it
40        if (!isAvailable[number]) {
41            isAvailable[number] = true;
42            availableQueue.offer(number);
43        }
44    }
45}

Python Solution for LeetCode 379

python

1from collections import deque
2
3class PhoneDirectory:
4
5    def __init__(self, maxNumbers: int):
6        self.max_limit = maxNumbers
7        # Queue stores available numbers for O(1) retrieval
8        self.available_queue = deque(range(maxNumbers))
9        # Boolean array stores status for O(1) lookup
10        self.is_available = [True] * maxNumbers
11
12    def get(self) -> int:
13        if not self.available_queue:
14            return -1
15        
16        number = self.available_queue.popleft()
17        self.is_available[number] = False
18        return number
19
20    def check(self, number: int) -> bool:
21        if number < 0 or number >= self.max_limit:
22            return False
23        return self.is_available[number]
24
25    def release(self, number: int) -> None:
26        if number < 0 or number >= self.max_limit:
27            return
28            
29        # Only add back if it is currently assigned (False)
30        if not self.is_available[number]:
31            self.is_available[number] = True
32            self.available_queue.append(number)

Design Phone Directory

Core insight

Core Insight for Design Phone Directory

Full breakdown

LeetCode 379: Design Phone Directory Solution & Explanation

Problem Overview

Brute Force Approach for Design Phone Directory

Algorithm Strategy: Design Patterns

Execution Flow

Proof of Correctness

Pattern Reuse Notes

Can you explain the core insight in your own words?

Reference Implementation

C++ Solution for LeetCode 379

Java Solution for LeetCode 379

Python Solution for LeetCode 379

Practise Design Phone Directory and the problems around it

Related problems

Design Phone Directory

Core insight

Core Insight for Design Phone Directory

Full breakdown

LeetCode 379: Design Phone Directory Solution & Explanation

Problem Overview

Brute Force Approach for Design Phone Directory

Algorithm Strategy: Design Patterns

Execution Flow

Proof of Correctness

Pattern Reuse Notes

Can you explain the core insight in your own words?

Reference Implementation

C++ Solution for LeetCode 379

Java Solution for LeetCode 379

Python Solution for LeetCode 379

Practise Design Phone Directory and the problems around it

Related problems