Watch 7 video solutions for Design Most Recently Used Queue, a medium level problem involving Array, Hash Table, Stack. This walkthrough by Brittany has 858 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |