Skip to content

1756. Design Most Recently Used Queue 👍

  • Time: Constructor: $O(n\log n)$, fetch(k: int): $O(\log n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
from sortedcontainers import SortedList


class MRUQueue:
  def __init__(self, n: int):
    # [(priority value, actual value)]
    self.q = SortedList((i, i) for i in range(1, n + 1))

  def fetch(self, k: int) -> int:
    _, num = self.q.pop(k - 1)
    if self.q:
      maxPriority = self.q[-1][0]
      self.q.add((maxPriority + 1, num))
    else:
      self.q.add((0, num))
    return num