Skip to content

379. Design Phone Directory 👎

  • Time: $O(1)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class PhoneDirectory {
 public:
  PhoneDirectory(int maxNumbers) : next(maxNumbers) {
    for (int i = 0; i < maxNumbers - 1; ++i)
      next[i] = i + 1;
    next.back() = 0;
  }

  int get() {
    if (next[number] == -1)
      return -1;
    const int ans = number;
    number = next[number];
    next[ans] = -1;  // Mark as used.
    return ans;
  }

  bool check(int number) {
    return next[number] != -1;
  }

  void release(int number) {
    if (next[number] != -1)
      return;
    next[number] = this->number;
    this->number = number;
  }

 private:
  int number = 0;    // the current possible available number
  vector<int> next;  // the next available numbers
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class PhoneDirectory {
  public PhoneDirectory(int maxNumbers) {
    next = new int[maxNumbers];
    for (int i = 0; i < maxNumbers - 1; ++i)
      next[i] = i + 1;
    next[maxNumbers - 1] = 0;
  }

  public int get() {
    if (next[number] == -1)
      return -1;
    final int availableNum = number;
    number = next[number];
    next[availableNum] = -1; // Mark as used.
    return ans;
  }

  public boolean check(int number) {
    return next[number] != -1;
  }

  public void release(int number) {
    if (next[number] != -1)
      return;

    next[number] = this.number;
    this.number = number;
  }

  private int number; // the current possible available number
  private int[] next; // the next available numbers
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class PhoneDirectory:
  def __init__(self, maxNumbers: int):
    # the next available numbers
    self.next = [i + 1 for i in range(maxNumbers - 1)] + [0]
    # the current possible available number
    self.number = 0

  def get(self) -> int:
    if self.next[self.number] == -1:
      return -1
    ans = self.number
    self.number = self.next[self.number]
    self.next[ans] = -1  # Mark as used.
    return ans

  def check(self, number: int) -> bool:
    return self.next[number] != -1

  def release(self, number: int) -> None:
    if self.next[number] != -1:
      return
    self.next[number] = self.number
    self.number = number