Skip to main content
Talentd

Design Most Recently Used Queue - Solution & Explanation

MediumPremiumFree on FleetCodeArrayHash TableStackDesign6 min readAsked at: Verizon, Google
Practice this problem

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].
  • 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 <= 2000
  • 1 <= k <= n
  • At most 2000 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?

Approach Overview

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.

Solution

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Array / List SimulationO(n) per fetchO(n)Simple implementation when constraints are small or for quickly explaining the behavior
Binary Indexed Tree (Fenwick Tree)O(log n) per fetchO(n)Best choice for large inputs where frequent k-th element queries and updates are required
Ordered Set / Order Statistics StructureO(log n)O(n)Languages with built-in ordered sets or trees that support k-th element queries

Video Solution

Leetcode 1756 Design Most Recently Used Queue Explanation & Code Square Root Decomposition Technique • Brittany • 883 views views

Watch 5 more video solutions →

Frequently Asked Questions

Is Design Most Recently Used Queue easy or hard?
The problem is rated Medium on LeetCode. A basic array simulation is straightforward, but the optimized solution requires understanding Fenwick Trees or ordered sets to efficiently support k-th element queries.
Design Most Recently Used Queue Python/Java solution
Most implementations maintain an array for element storage and a Fenwick Tree for index tracking. Python, Java, and C++ versions follow the same pattern: binary search on the tree to find the k-th active index, remove it, then append the element to the end while updating the tree.
How to solve Design Most Recently Used Queue in O(log n)?
Store elements in indexed positions and maintain a Fenwick Tree tracking which indices are active. Use prefix sums and binary search to locate the k-th active index in O(log n). After retrieving the value, mark the position inactive and append the element at the end with another update.
What is the best approach for Design Most Recently Used Queue?
The most efficient approach uses a Binary Indexed Tree (Fenwick Tree) combined with binary search to locate the k-th active element. Each fetch operation becomes O(log n) for both querying and updating the structure. This avoids the costly shifting required in a simple array implementation.
Is Design Most Recently Used Queue asked at Google/Amazon/Meta?
Problems involving queue design, order statistics, and Fenwick Trees appear frequently in interviews at companies like Google, Amazon, and Meta. Variants that require finding the k-th element in a dynamic structure are especially common in system design and data structure rounds.
What data structure is used in Design Most Recently Used Queue?
The optimal implementation uses a Binary Indexed Tree (Fenwick Tree) to track active indices and support prefix sum queries. Some solutions also model the structure as an ordered set that supports k-th element lookup and dynamic updates.
What is the time complexity of Design Most Recently Used Queue?
The optimal solution runs in O(log n) time per fetch operation using a Fenwick Tree or order statistics structure. A naive array-based implementation requires O(n) time because removing the k-th element shifts remaining elements.

Ready to solve this problem?

Practice Design Most Recently Used Queue with our built-in code editor and test cases.

Practice on FleetCode
Previous

LRU Cache