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].int fetch(int k) moves the kth element (1-indexed) to the end of the queue and returns it.
Example 1:
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.
Constraints:
1 <= n <= 20001 <= k <= n2000 calls will be made to fetch.Follow up: Finding an
O(n) algorithm per fetch is a bit easy. Can you find an algorithm with a better complexity for each fetch call?Problem Overview: Design a queue initialized with values 1..n. Each fetch(k) operation removes the k-th element in the current queue, returns it, and appends it to the end. The challenge is maintaining fast k-th element lookup while the structure keeps changing.
Approach 1: Array / List Simulation (O(n) per fetch, O(n) space)
The most direct solution uses a dynamic array or list. Initialize the array with values 1..n. For each fetch(k), access the element at index k-1, remove it using a shift operation, then append it to the end of the array. This works because arrays support direct indexing.
The drawback is the removal step. Deleting the k-th element requires shifting up to n elements, making each operation O(n). With up to thousands of operations, the total runtime can grow to O(n * q). This approach is acceptable for small constraints and is easy to implement, but it does not scale well when the queue grows large.
This simulation mainly relies on a basic array structure and straightforward index manipulation.
Approach 2: Binary Indexed Tree + Binary Search (O(log n) per fetch, O(n) space)
A more scalable solution treats the queue positions as indices and tracks which indices currently hold active elements. Store elements in a large array and use a Binary Indexed Tree (Fenwick Tree) to maintain how many active elements exist up to each index.
The Fenwick Tree allows prefix sum queries in O(log n). To locate the k-th element, perform a binary search over the tree to find the smallest index whose prefix sum equals k. That index corresponds to the k-th element in the current queue. After retrieving it, mark that position as removed in the tree and append the element to a new position at the end while updating the tree.
This structure efficiently supports dynamic ordering without physically shifting elements. Each fetch performs a logarithmic prefix query, binary search, and update, giving O(log n) time per operation and O(n) space overall. Conceptually, this behaves like an ordered set where you can query the k-th active element.
Recommended for interviews: Start with the array simulation to show you understand the queue behavior and how the k-th element moves to the end. Then optimize using a Fenwick Tree or ordered-set style structure to support fast k-th queries. Interviewers typically expect the O(log n) approach because it demonstrates knowledge of indexed data structures and dynamic order statistics.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Array / List Simulation | O(n) per fetch | O(n) | Simple implementation when constraints are small or for quickly explaining the behavior |
| Binary Indexed Tree (Fenwick Tree) | O(log n) per fetch | O(n) | Best choice for large inputs where frequent k-th element queries and updates are required |
| Ordered Set / Order Statistics Structure | O(log n) | O(n) | Languages with built-in ordered sets or trees that support k-th element queries |
Leetcode 1756 Design Most Recently Used Queue Explanation & Code Square Root Decomposition Technique • Brittany • 858 views views
Watch 6 more video solutions →Practice Design Most Recently Used Queue with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor