LeetCode 379: Design Phone Directory Solution in Python – A Step-by-Step Guide

What Is LeetCode 379: Design Phone Directory?

LeetCode 379: Design Phone Directory asks you to implement a PhoneDirectory class that manages a pool of phone numbers from 0 to maxNumbers-1. You need to support three operations: get a number, check if a number is available, and release a number back to the pool. It’s a design problem that tests your ability to handle allocation efficiently!

Problem Statement

• Class: PhoneDirectory
• Methods:
• __init__(maxNumbers): Initialize with maxNumbers available (0 to maxNumbers-1).
• get(): Return an available number (-1 if none).
• check(number): Return True if number is available, False otherwise.
• release(number): Recycle a number back to the pool.
• Rules:
• Numbers range from 0 to maxNumbers-1.
• Each number can be assigned at most once until released.

Constraints

• 1 <= maxNumbers <= 10⁴
• 0 <= number < maxNumbers
• At most 2 * 10⁴ calls to get, check, and release.

Examples

• Input: ["PhoneDirectory","get","get","check","get","check","release","check"], [[3],[],[],[1],[],[1],[1],[1]]
• Output: [null,0,1,true,2,false,null,true]
• Init(3): Pool = {0,1,2}.
• get(): 0, Pool = {1,2}.
• get(): 1, Pool = {2}.
• check(1): False (assigned).
• get(): 2, Pool = {}.
• check(1): False (still assigned).
• release(1): Pool = {1}.
• check(1): True (released).
• Input: ["PhoneDirectory","get","check","release","check"], [[2],[],[0],[0],[0]]
• Output: [null,0,true,null,true]
• Init(2): Pool = {0,1}.
• get(): 0, Pool = {1}.
• check(0): False.
• release(0): Pool = {1,0}.
• check(0): True.

These show the directory management—let’s solve it!

Understanding the Problem: Managing Phone Numbers

To tackle LeetCode 379 in Python, we need a class that: 1. Initializes with maxNumbers available numbers. 2. Assigns numbers (get), checks availability (check), and recycles numbers (release). 3. Operates efficiently for up to 2 * 10⁴ calls.

A naive approach might scan a list each time, but that’s slow. Instead, we’ll use:

• Best Solution: Set and queue—O(1) time per operation, O(n) space—fast and robust.
• Alternative Solution: List with swapping—O(1) time, O(n) space—simple but less flexible.

Let’s manage with the best solution!

Best Solution: Set and Queue

Why This Is the Best Solution

The set and queue approach offers O(1) average-case time for all operations by using a queue to store available numbers and a set to track assigned ones. It’s the most efficient and versatile—handling dynamic allocation and deallocation seamlessly with minimal overhead!

How It Works

Think of it like a phone number dispenser:

• Queue: Holds available numbers in order (FIFO).
• Set: Tracks assigned numbers for quick lookup.
• Init: Fill queue with 0 to maxNumbers-1, set is empty.
• Get: Pop from queue, add to set, return number (-1 if empty).
• Check: Check if number is not in set.
• Release: If not in set, add to queue and remove from set.

It’s like a ticket system—grab, check, return!

Step-by-Step Example

For maxNumbers = 3:

• Init: Queue = [0, 1, 2], Set = {}.
• get(): Pop 0, Set = {0}, return 0, Queue = [1, 2].
• get(): Pop 1, Set = {0, 1}, return 1, Queue = [2].
• check(1): 1 in Set, return False.
• get(): Pop 2, Set = {0, 1, 2}, return 2, Queue = [].
• check(1): 1 in Set, return False.
• release(1): 1 in Set, remove from Set, add to Queue, Set = {0, 2}, Queue = [1].
• check(1): 1 not in Set, return True.

For maxNumbers = 1:

• Init: Queue = [0], Set = {}.
• get(): Pop 0, Set = {0}, return 0, Queue = [].
• check(0): False.

Code with Explanation

Here’s the Python code using a set and queue:

Copy codefrom collections import deque

class PhoneDirectory:
    def __init__(self, maxNumbers: int):
        # Queue for available numbers, set for assigned
        self.available = deque(range(maxNumbers))
        self.assigned = set()

    def get(self) -> int:
        # Get an available number
        if not self.available:
            return -1
        num = self.available.popleft()
        self.assigned.add(num)
        return num

    def check(self, number: int) -> bool:
        # Check if number is available
        return number not in self.assigned

    def release(self, number: int) -> None:
        # Release a number if assigned
        if number in self.assigned:
            self.assigned.remove(number)
            self.available.append(number)

Explanation

• Lines 4-7: __init__:
• available: Queue with numbers 0 to maxNumbers-1.
• assigned: Empty set for tracking.
• Lines 9-14: get:
• If queue empty, return -1.
• Pop number, add to assigned, return it—O(1).
• Lines 16-18: check:
• Return True if number not in assigned—O(1) average.
• Lines 20-23: release:
• If number in assigned, remove it, add to queue—O(1).
• Time: O(1) average per operation.
• Space: O(n)—queue and set store up to n numbers.

This is like a phone number manager—quick and reliable!

Alternative Solution: List with Swapping

Why an Alternative Approach?

The list with swapping solution also runs in O(1) time per operation by using a list and an index to track available numbers, swapping released numbers to the end. It’s simpler in structure—great for understanding a different allocation strategy, though less flexible for dynamic releases!

How It Works

• List: Store numbers 0 to maxNumbers-1.
• Index: next_idx tracks first available number.
• Get: Return number at next_idx, increment index.
• Check: Check if number < next_idx (assigned).
• Release: Swap with last available, adjust index.

Step-by-Step Example

For maxNumbers = 3:

• Init: nums = [0, 1, 2], next_idx = 0.
• get(): Return 0, next_idx = 1, nums = [0, 1, 2].
• get(): Return 1, next_idx = 2, nums = [0, 1, 2].
• check(1): 1 < 2, return False.
• get(): Return 2, next_idx = 3, nums = [0, 1, 2].
• check(1): 1 < 3, return False.
• release(1): Swap 1 with 2 (last available), next_idx = 2, nums = [0, 2, 1].
• check(1): 1 < 2, return False (1 still assigned until next_idx moves back).

Code with Explanation

Copy codeclass Solution:
    def __init__(self, maxNumbers: int):
        # List of numbers, index of next available
        self.nums = list(range(maxNumbers))
        self.next_idx = 0
        self.max = maxNumbers

    def get(self) -> int:
        # Get next available number
        if self.next_idx >= self.max:
            return -1
        num = self.nums[self.next_idx]
        self.next_idx += 1
        return num

    def check(self, number: int) -> bool:
        # Check if number is available
        return number >= self.next_idx or number not in self.nums[:self.next_idx]

    def release(self, number: int) -> None:
        # Release by swapping with last assigned
        if number < self.next_idx and number in self.nums[:self.next_idx]:
            self.next_idx -= 1
            self.nums[self.next_idx], self.nums[number] = self.nums[number], self.nums[self.next_idx]

Explanation

• Lines 4-6: __init__:
• nums: List of 0 to maxNumbers-1.
• next_idx: Start at 0.
• Lines 8-13: get:
• If next_idx ≥ max, return -1.
• Return nums[next_idx], increment—O(1).
• Lines 15-17: check:
• True if number ≥ next_idx or not in assigned—O(1) average with check.
• Lines 19-22: release:
• If number assigned, swap with last, decrement next_idx—O(1).
• Time: O(1) per operation.
• Space: O(n)—list.

It’s like a number swapper—simple but less dynamic!

Comparing the Two Solutions

• Set and Queue (Best):
• Time: O(1) average—queue and set ops.
• Space: O(n)—queue and set.
• Pros: Fast, flexible releases.
• Cons: Slightly more memory.
• List with Swapping (Alternative):
• Time: O(1)—swaps and checks.
• Space: O(n)—list.
• Pros: Simple, O(1) space overhead.
• Cons: Less intuitive releases.

Set and queue win for flexibility and clarity!

Additional Examples and Edge Cases

• maxNumbers=1: Both handle single number.
• Full assignment: Both return -1 when empty.
• Repeated releases: Set handles duplicates better.

Both work, set is more robust.

Complexity Breakdown

• Set and Queue:
• Time: O(1) average.
• Space: O(n).
• List with Swapping:
• Time: O(1).
• Space: O(n).

Both are fast, set offers better release handling.

Key Takeaways

• Set and Queue: Manage dynamically—fast and robust!
• List Swapping: Swap simply—lean but rigid!
• Design: Efficiency meets flexibility.
• Python Tip: Collections rock—see [Python Basics](/python/basics).

Final Thoughts: Manage That Directory

LeetCode 379: Design Phone Directory in Python is a design challenge. Set and queue is the versatility champ, while list with swapping offers simplicity. Want more? Try LeetCode 146: LRU Cache or LeetCode 355: Design Twitter. Ready to dial? Visit Solve LeetCode 379 on LeetCode (premium) and assign those numbers today!