Leetcode #1756: Design Most Recently Used Queue
In this guide, we solve Leetcode #1756 Design Most Recently Used Queue in Python and focus on the core idea that makes the solution efficient.
You will see the intuition, the step-by-step method, and a clean Python implementation you can use in interviews.
Problem Statement
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].
Quick Facts
- Difficulty: Medium
- Premium: Yes
- Tags: Design, Array, Linked List, Divide and Conquer, Doubly-Linked List, Simulation
Intuition
Linked list problems often require pointer manipulation rather than extra memory.
Two-pointer techniques expose cycles, midpoints, or reordering patterns.
Approach
Traverse with fast/slow pointers or reverse sublists when needed.
Maintain invariants carefully to avoid losing nodes.
Steps:
- Traverse with pointers.
- Reverse or split if required.
- Reconnect nodes correctly.
Example
Input:
["MRUQueue", "fetch", "fetch", "fetch", "fetch"]
[[8], [3], [5], [2], [8]]
Output:
[null, 3, 6, 2, 2]
Explanation:
MRUQueue mRUQueue = new MRUQueue(8); // Initializes the queue to [1,2,3,4,5,6,7,8].
mRUQueue.fetch(3); // Moves the 3rd element (3) to the end of the queue to become [1,2,4,5,6,7,8,3] and returns it.
mRUQueue.fetch(5); // Moves the 5th element (6) to the end of the queue to become [1,2,4,5,7,8,3,6] and returns it.
mRUQueue.fetch(2); // Moves the 2nd element (2) to the end of the queue to become [1,4,5,7,8,3,6,2] and returns it.
mRUQueue.fetch(8); // The 8th element (2) is already at the end of the queue so just return it.
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
The time complexity is O(n). The space complexity is O(1).
Edge Cases and Pitfalls
Watch for boundary values, empty inputs, and duplicate values where applicable. If the problem involves ordering or constraints, confirm the invariant is preserved at every step.
Summary
This Python solution focuses on the essential structure of the problem and keeps the implementation interview-friendly while meeting the constraints.