Domain 2MediumCORE

Design Phone Directory

We need to manage a pool of phone numbers from 0 to maxNumbers - 1. The system must support three operations: allocating an unused number (get), checking if a specific number is free (check), and freeing up a previously allocated number (release).

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Linked List#Design

379. Design Phone Directory

Model: qwen3.5:9b
Topics: Linked List,Design
FAANG asked: 1
Acceptance rate: 48.4%


Problem Breakdown

We need to manage a pool of phone numbers from 0 to maxNumbers - 1. The system must support three operations: allocating an unused number (get), checking if a specific number is free (check), and freeing up a previously allocated number (release).

Key constraints are the maximum capacity (N≤104N \le 10^4) and the total number of calls (up to 2⋅1042 \cdot 10^4). We need an efficient way to track availability. The tricky part is ensuring get returns any available slot quickly without scanning a large array every time, while maintaining fast lookups for check.

Intuition

A naive approach would be to use a boolean list where we scan from index 0 upwards until we find an empty slot (True) or reach the end.

  • Naive Time Complexity: O(N)O(N) per get call because of scanning. With many calls, this leads to O(K⋅N)O(K \cdot N) total time, which is too slow if KK (calls) and NN are large.
  • Optimization Insight: Since the order in which we return numbers doesn’t matter (“any available phone number”), we don’t need a specific queue structure like FIFO. We just need to know which slots exist as free resources. A Hash Set allows us to store all currently free numbers and perform O(1)O(1) lookups, insertions (release), and deletions (get).
  • Key Insight: Maintain the state of “available” vs “occupied”. If we track available numbers in a set:
    • check is simply checking membership.
    • release adds to the set.
    • get removes from the set (and returns value).

Approach

  1. Initialization: Create a Python set initialized with all integers from 00 to maxNumbers - 1. This represents our pool of free slots.
  2. Constructor (__init__): Populate the set and store it as an instance variable. Time complexity is linear relative to capacity, which happens once at startup.
  3. Method get():
    • Check if the set is empty. If so, return -1.
    • Otherwise, use .pop(). This removes and returns a random element from the set in O(1)O(1) amortized time. We don’t need to track which specific number was returned for future logic other than its absence.
  4. Method check(number):
    • Return whether number is present in our available slots set using in. This is O(1)O(1).
  5. Method release(number):
    • Add the number back to the set if it’s not already there (though logically, we assume valid inputs where only occupied numbers are released). Python sets handle duplicate additions gracefully by ignoring them, so a simple .add() works perfectly for both cases without explicit existence checks.

Complexity Analysis

  • Time Complexity:
    • Initialization: O(N)O(N) to build the initial set of available slots.
    • get, check, release: All are O(1)O(1) amortized operations on a hash set.
    • Total for KK calls after initialization is O(K)O(K). Given constraints, this fits well within time limits.
  • Space Complexity:
    • We store every available slot in the set: O(N)O(N). This is necessary to track state and cannot be avoided without scanning (which would increase space but hurt time).

Solution

class PhoneDirectory:
    def __init__(self, maxNumbers):
        # Initialize a set with all numbers from 0 to maxNumbers - 1.
        # This represents the pool of currently available phone slots.
        self.available = set(range(maxNumbers))

    def get(self) -> int:
        """Returns an empty slot or -1 if no number is available."""
        if not self.available:
            return -1
        
        # Pop removes and returns a random element from the set efficiently.
        return self.available.pop()

    def check(self, number: int) -> bool:
        """Checks if 'number' slot is currently empty (available)."""
        return number in self.available

    def release(self, number: int):
        """Recycles or releases a specific slot back to the pool."""
        # Adding an existing element does nothing harmful; it ensures 
        # availability status matches reality.
        self.available.add(number)

Edge Cases Handled

  • Empty Directory: If get is called when all slots are taken, self.available becomes empty. The check if not self.available correctly returns -1.
  • Full Capacity Initialization: Initializing with maxNumbersmaxNumbers ensures the range covers exactly [0, maxNumbers), matching constraints (number<maxNumbersnumber < maxNumbers).
  • Release on Already Free Slot: If a number is released that was never taken (or already free), set.add handles it idempotently without throwing errors or corrupting state. This makes the implementation robust against invalid release calls in some test environments, though valid inputs are expected per problem description.