LeetCode 379 - Design Phone Directory

The problem asks us to design a data structure that manages a fixed pool of phone numbers. Initially, every number from 0 to maxNumbers - 1 is available. The directory must support three operations efficiently. The get() operation should assign and return an available number.

leetcodemediumarrayhash-tablelinked-listdesignqueue

LeetCode Problem 379

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Linked List, Design, Queue

Solution

Problem Understanding

The problem asks us to design a data structure that manages a fixed pool of phone numbers. Initially, every number from 0 to maxNumbers - 1 is available. The directory must support three operations efficiently.

The get() operation should assign and return an available number. If no numbers remain, it should return -1.

The check(number) operation should tell us whether a specific number is currently available.

The release(number) operation should return a previously assigned number back into the pool so it can be reused later.

The important detail is that numbers can move back and forth between two states:

  • Available
  • Assigned

The system must continuously track those states while supporting many operations efficiently.

The constraints are relatively small, with at most 10^4 phone numbers and 2 * 10^4 operations. Even though the limits are not massive, the problem is fundamentally about designing an efficient reusable resource allocator. A naive implementation may still pass in practice, but the intended solution should provide near constant-time operations.

Several edge cases matter immediately.

If all numbers are assigned, get() must return -1. A careless implementation might attempt to pop from an empty structure or return an invalid number.

If release(number) is called on a number that is already available, we must avoid inserting duplicates into the available pool. Otherwise, the same number could be assigned multiple times simultaneously.

Another important case is checking numbers after repeated release and reassignment cycles. The structure must always reflect the current availability state accurately.

The problem guarantees that number passed into check() and release() will always be within bounds, specifically 0 <= number < maxNumbers. This simplifies implementation because we do not need additional range validation.

Approaches

Brute Force Approach

The most straightforward solution is to maintain an array indicating whether each number is available.

For example:

  • True means the number is free
  • False means the number is assigned

For get(), we scan the entire array from left to right until we find an available number. We then mark it as assigned and return it.

For check(number), we simply return the boolean value at that index.

For release(number), we mark the number as available again.

This solution is correct because the availability array always reflects the true state of every phone number. However, the problem is the get() operation. In the worst case, we may need to scan all maxNumbers entries before finding a free number or determining none exist.

That makes get() take O(n) time.

Since there may be many operations, repeatedly scanning the array becomes inefficient.

Optimal Approach

The key insight is that we do not actually need to scan all numbers to find an available one. Instead, we can explicitly store all currently available numbers in a queue or stack.

At initialization:

  • Every number is available
  • We place all numbers into a queue

When get() is called:

  • Remove one number from the queue
  • Mark it as assigned
  • Return it

When release(number) is called:

  • If the number is currently assigned, add it back into the queue

To support fast check(number) operations, we also maintain a hash set containing all currently available numbers.

This gives us constant-time operations because:

  • Queue removal is O(1)
  • Hash set lookup is O(1)
  • Hash set insertion/removal is O(1)

The queue manages allocation order, while the hash set provides fast membership testing.

Approach Time Complexity Space Complexity Notes
Brute Force get(): O(n), others O(1) O(n) Scans the entire array to find a free number
Optimal O(1) average for all operations O(n) Uses queue plus hash set for constant-time operations

Algorithm Walkthrough

  1. Initialize a queue containing all phone numbers from 0 to maxNumbers - 1.

Every number starts as available, so the queue represents the pool of free numbers. 2. Initialize a hash set containing the same numbers.

The set allows fast lookup when checking whether a number is available. 3. For get():

  • If the queue is empty, return -1
  • Otherwise, remove a number from the front of the queue
  • Remove that same number from the availability set
  • Return the number

Removing the number from the set marks it as assigned. 4. For check(number):

  • Return whether the number exists in the availability set

Since sets support constant-time lookup, this operation is efficient. 5. For release(number):

  • First check whether the number is already available

  • If it is already in the availability set, do nothing

  • Otherwise:

  • Add the number back into the queue

  • Add it back into the availability set

This prevents duplicate entries in the queue.

Why it works

The core invariant is that the queue and the availability set always contain exactly the same available numbers.

Whenever a number is assigned through get(), it is removed from both structures.

Whenever a number is released, it is added back to both structures.

Because of this invariant:

  • check(number) is always accurate
  • get() always returns an unused number
  • No number can be assigned twice simultaneously

Python Solution

from collections import deque

class PhoneDirectory:

    def __init__(self, maxNumbers: int):
        self.available_queue = deque(range(maxNumbers))
        self.available_set = set(range(maxNumbers))

    def get(self) -> int:
        if not self.available_queue:
            return -1

        number = self.available_queue.popleft()
        self.available_set.remove(number)

        return number

    def check(self, number: int) -> bool:
        return number in self.available_set

    def release(self, number: int) -> None:
        if number in self.available_set:
            return

        self.available_queue.append(number)
        self.available_set.add(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)

The implementation uses two data structures.

The deque stores all currently available numbers in allocation order. We use popleft() because it runs in constant time.

The available_set tracks availability status. This makes check(number) extremely efficient because hash set membership testing is O(1) on average.

Inside get(), we first verify that at least one number remains available. If the queue is empty, we return -1.

Otherwise, we remove the front number from the queue and also remove it from the set. That transition marks the number as assigned.

The release() method carefully avoids duplicates. If the number is already available, we do nothing. Otherwise, we append it back into the queue and add it back into the set.

This ensures the queue and set remain synchronized throughout all operations.

Go Solution

type PhoneDirectory struct {
	availableQueue []int
	availableSet   map[int]bool
	head           int
}

func Constructor(maxNumbers int) PhoneDirectory {
	queue := make([]int, maxNumbers)
	available := make(map[int]bool)

	for i := 0; i < maxNumbers; i++ {
		queue[i] = i
		available[i] = true
	}

	return PhoneDirectory{
		availableQueue: queue,
		availableSet:   available,
		head:           0,
	}
}

func (this *PhoneDirectory) Get() int {
	if this.head >= len(this.availableQueue) {
		return -1
	}

	number := this.availableQueue[this.head]
	this.head++

	delete(this.availableSet, number)

	return number
}

func (this *PhoneDirectory) Check(number int) bool {
	return this.availableSet[number]
}

func (this *PhoneDirectory) Release(number int) {
	if this.availableSet[number] {
		return
	}

	this.availableQueue = append(this.availableQueue, number)
	this.availableSet[number] = true
}

/**
 * Your PhoneDirectory object will be instantiated and called as such:
 * obj := Constructor(maxNumbers);
 * param_1 := obj.Get();
 * param_2 := obj.Check(number);
 * obj.Release(number);
 */

The Go version uses a slice to simulate a queue. Instead of repeatedly removing elements from the front, which would be inefficient, we maintain a head pointer that tracks the current front position.

The availableSet is implemented using map[int]bool.

One implementation detail worth noting is that Go maps return the zero value for missing keys. Since the zero value for bool is false, this.availableSet[number] naturally works as a membership check.

Unlike Python's deque, Go slices do not provide efficient front removal, so using a head index is the preferred approach.

Worked Examples

Example 1

Input:

["PhoneDirectory", "get", "get", "check", "get", "check", "release", "check"]
[[3], [], [], [2], [], [2], [2], [2]]

Initial state:

Operation Queue Available Set Returned
Initialize [0, 1, 2] {0, 1, 2} null

Step 1: get()

Remove 0 from the queue.

Operation Queue Available Set Returned
get() [1, 2] {1, 2} 0

Step 2: get()

Remove 1 from the queue.

Operation Queue Available Set Returned
get() [2] {2} 1

Step 3: check(2)

Check whether 2 exists in the set.

Operation Queue Available Set Returned
check(2) [2] {2} true

Step 4: get()

Remove 2 from the queue.

Operation Queue Available Set Returned
get() [] {} 2

Step 5: check(2)

2 is no longer available.

Operation Queue Available Set Returned
check(2) [] {} false

Step 6: release(2)

Add 2 back into both structures.

Operation Queue Available Set Returned
release(2) [2] {2} null

Step 7: check(2)

2 is available again.

Operation Queue Available Set Returned
check(2) [2] {2} true

Complexity Analysis

Measure Complexity Explanation
Time O(1) average per operation Queue operations and hash set operations are constant time
Space O(n) We store all phone numbers in the queue and set

The solution maintains two data structures that together contain all available numbers. Since at most maxNumbers values exist, the total memory usage is linear.

Each operation performs only a constant number of queue or hash set operations, giving average O(1) runtime.

Test Cases

# Example from the problem statement
pd = PhoneDirectory(3)

assert pd.get() == 0          # first available number
assert pd.get() == 1          # second available number
assert pd.check(2) is True    # 2 is still available
assert pd.get() == 2          # last available number
assert pd.check(2) is False   # 2 is now assigned

pd.release(2)
assert pd.check(2) is True    # released number becomes available again

# Single number directory
pd = PhoneDirectory(1)

assert pd.get() == 0          # only number assigned
assert pd.get() == -1         # no numbers left
assert pd.check(0) is False   # assigned number unavailable

pd.release(0)
assert pd.check(0) is True    # released successfully
assert pd.get() == 0          # reusable after release

# Releasing already available number
pd = PhoneDirectory(2)

pd.release(1)                 # should do nothing
assert pd.get() == 0          # normal allocation
assert pd.get() == 1          # no duplicate insertion
assert pd.get() == -1         # all numbers exhausted

# Multiple release and reuse cycles
pd = PhoneDirectory(2)

a = pd.get()
b = pd.get()

assert {a, b} == {0, 1}       # both numbers assigned
assert pd.get() == -1         # no numbers available

pd.release(a)
assert pd.check(a) is True    # released correctly
assert pd.get() == a          # same number reused

pd.release(b)
assert pd.check(b) is True    # second number reusable

# Stress repeated operations
pd = PhoneDirectory(5)

nums = [pd.get() for _ in range(5)]
assert set(nums) == {0, 1, 2, 3, 4}  # all unique
assert pd.get() == -1                # exhausted

for num in nums:
    pd.release(num)

for num in nums:
    assert pd.check(num) is True     # all restored
Test Why
Problem example Validates standard allocation and release behavior
Single number directory Tests smallest possible input
Releasing already available number Ensures duplicate entries are not created
Multiple release cycles Verifies numbers can be reused repeatedly
Stress repeated operations Confirms correctness under many transitions

Edge Cases

One important edge case occurs when all numbers have already been assigned. In this situation, the queue of available numbers becomes empty. A buggy implementation might attempt to remove an element anyway, causing an exception or invalid behavior. The solution handles this safely by explicitly checking whether the queue is empty before removing a number. If no numbers remain, it returns -1.

Another subtle edge case is releasing a number that is already available. Without protection against duplicates, the same number could appear multiple times in the queue. That would eventually allow the same phone number to be assigned to multiple users simultaneously. The implementation prevents this by first checking whether the number already exists in the availability set before reinserting it.

A third important case involves repeated release and reassignment cycles. A number may be assigned, released, reassigned, and released again many times. The implementation maintains synchronization between the queue and the set throughout every operation, ensuring the availability state always remains correct regardless of how many times a number changes state.