MediumNo. 1756LeetCode Premium
Design Most Recently Used Queue — LeetCode 1756 Python Solution
- Pattern
- Linked List
- Topics
- Design, Array, Linked List, Divide and Conquer, Doubly-Linked List, Simulation
- Reading time
- 3 min
- Source
- leetcode.com
The problem
Design a queue-like data structure that moves the most recently used element to the end of the queue. Implement the MRUQueue class: MRUQueue(int n) constructs the MRUQueue with n elements: [1,2,3,...,n].
Example
- Input
- ["MRUQueue", "fetch", "fetch", "fetch", "fetch"]
- Output
- [null, 3, 6, 2, 2]
- Explanation
- MRUQueue mRUQueue = new MRUQueue(8); // Initializes the queue to [1,2,3,4,5,6,7,8].
Python solution
class MRUQueue:
def __init__(self, n: int):
self.q = list(range(1, n + 1))
def fetch(self, k: int) -> int:
ans = self.q[k - 1]
self.q[k - 1 : k] = []
self.q.append(ans)
return ans
# Your MRUQueue object will be instantiated and called as such:
# obj = MRUQueue(n)
# param_1 = obj.fetch(k)Complexity
- Time
- O(n)
- Space · auxiliary
- O(1)
Pattern: Linked List
Rewire pointers in place, with a dummy head and a saved next to keep it safe. LeetCode 1756. Design Most Recently Used Queue is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Linked List and Doubly-Linked List.
The linked list guide has the Python template for the pattern and the 75 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 2326 | Spiral Matrix IV | Medium |
| 0148 | Sort List | Medium |
| 0707 | Design Linked List | Medium |
| 1206 | Design Skiplist | Hard |
| 2181 | Merge Nodes in Between Zeros | Medium |
| 0019 | Remove Nth Node From End of List | Medium |
Frequently asked questions
- How hard is LeetCode 1756. Design Most Recently Used Queue?
LeetCode 1756. Design Most Recently Used Queue is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1756. Design Most Recently Used Queue?
The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 1756. Design Most Recently Used Queue?
The Python solution on this page uses O(1) auxiliary space.
- What topics does LeetCode 1756. Design Most Recently Used Queue cover?
LeetCode 1756. Design Most Recently Used Queue is tagged Design, Array, Linked List, Divide and Conquer, Doubly-Linked List and Simulation on LeetCode.
- Is LeetCode 1756. Design Most Recently Used Queue a premium problem?
Yes. LeetCode 1756. Design Most Recently Used Queue is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.