1756. Design Most Recently Used Queue 🔒
Problem Description
This problem asks you to implement a Most Recently Used (MRU) Queue data structure with specific behavior for accessing elements.
The MRU Queue works as follows:
-
Initialization: When you create an
MRUQueue
with parametern
, it automatically populates itself with elements[1, 2, 3, ..., n]
in order. -
Fetch Operation: The
fetch(k)
method performs two actions:- It retrieves the element at position
k
(using 1-based indexing, where the first element is at position 1) - It moves that element to the end of the queue
- It returns the value of that element
- It retrieves the element at position
Example walkthrough:
- Start with
MRUQueue(5)
: Queue contains[1, 2, 3, 4, 5]
- Call
fetch(3)
:- The 3rd element is
3
- Move
3
to the end: Queue becomes[1, 2, 4, 5, 3]
- Return
3
- The 3rd element is
- Call
fetch(2)
:- The 2nd element is now
2
- Move
2
to the end: Queue becomes[1, 4, 5, 3, 2]
- Return
2
- The 2nd element is now
The solution uses a simple list to represent the queue. For the fetch
operation, it:
- Retrieves the element at index
k-1
(converting from 1-indexed to 0-indexed) - Removes that element from its current position using slice deletion
self.q[k-1:k] = []
- Appends the element to the end of the queue
- Returns the fetched element value
Intuition
The key insight for this problem is recognizing that we need a data structure that maintains order while allowing us to efficiently remove an element from any position and add it to the end.
Since we need to access elements by their position (the k
-th element), an array-like structure is a natural choice. A simple Python list gives us:
- Direct access to any element by index in
O(1)
time - The ability to append to the end efficiently
- Built-in operations for removing elements
The challenge is moving an element from position k
to the end. We can break this down into two steps:
- Remove the element at position
k
- Add that element to the end
For removal, Python's slice assignment self.q[k-1:k] = []
is an elegant way to delete exactly one element at index k-1
. This is equivalent to del self.q[k-1]
or self.q.pop(k-1)
, but using slice notation makes it clear we're removing a single-element slice.
The straightforward approach works well here because:
- We don't need to optimize for extremely large queues or frequent operations (based on typical constraints)
- The simplicity of the list-based solution makes it easy to understand and implement correctly
- Python's list operations handle the shifting of elements automatically when we remove from the middle
While this solution has O(n)
time complexity for the fetch
operation (due to shifting elements after removal), it's acceptable for moderate-sized queues and provides clean, readable code that directly maps to the problem's requirements.
Learn more about Stack patterns.
Solution Approach
The implementation uses a simple list-based approach to maintain the MRU Queue.
Data Structure:
- We use a Python list
self.q
to store the queue elements - The list is initialized with values from
1
ton
usinglist(range(1, n + 1))
Implementation Details:
-
Constructor
__init__(self, n)
:self.q = list(range(1, n + 1))
- Creates a list containing elements
[1, 2, 3, ..., n]
range(1, n + 1)
generates numbers from 1 to n (inclusive)- Converting to a list allows us to modify it later
- Creates a list containing elements
-
Method
fetch(self, k)
:ans = self.q[k - 1] self.q[k - 1 : k] = [] self.q.append(ans) return ans
The fetch operation performs four steps:
-
Step 1:
ans = self.q[k - 1]
- Store the k-th element (converting from 1-indexed to 0-indexed) -
Step 2:
self.q[k - 1 : k] = []
- Remove the element at position k-1- This slice assignment removes exactly one element
- It's equivalent to deleting the slice from index
k-1
tok
(exclusive) - Elements after position k automatically shift left to fill the gap
-
Step 3:
self.q.append(ans)
- Add the removed element to the end of the queue -
Step 4:
return ans
- Return the value of the fetched element
-
Time Complexity:
__init__
: O(n) to create the initial listfetch
: O(n) due to the element removal requiring shifts of subsequent elements
Space Complexity:
- O(n) to store the queue elements
The solution elegantly handles the MRU behavior by combining Python's list slicing for removal with the append operation for adding to the end, making the code concise and readable.
Ready to land your dream job?
Unlock your dream job with a 5-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's trace through a concrete example with n = 4
to understand how the MRU Queue operates:
Initial Setup:
mru = MRUQueue(4) # Queue state: [1, 2, 3, 4]
First fetch operation: fetch(2)
result = mru.fetch(2)
- Step 1: Access element at index
2-1 = 1
, which is2
- Step 2: Remove element
2
using sliceself.q[1:2] = []
- Queue becomes:
[1, 3, 4]
- Queue becomes:
- Step 3: Append
2
to the end- Queue becomes:
[1, 3, 4, 2]
- Queue becomes:
- Step 4: Return
2
Second fetch operation: fetch(3)
result = mru.fetch(3)
- Step 1: Access element at index
3-1 = 2
, which is4
- Step 2: Remove element
4
using sliceself.q[2:3] = []
- Queue becomes:
[1, 3, 2]
- Queue becomes:
- Step 3: Append
4
to the end- Queue becomes:
[1, 3, 2, 4]
- Queue becomes:
- Step 4: Return
4
Third fetch operation: fetch(1)
result = mru.fetch(1)
- Step 1: Access element at index
1-1 = 0
, which is1
- Step 2: Remove element
1
using sliceself.q[0:1] = []
- Queue becomes:
[3, 2, 4]
- Queue becomes:
- Step 3: Append
1
to the end- Queue becomes:
[3, 2, 4, 1]
- Queue becomes:
- Step 4: Return
1
Final queue state: [3, 2, 4, 1]
Notice how each fetched element moves to the end, maintaining the "most recently used" property where recently accessed elements migrate toward the back of the queue.
Solution Implementation
1class MRUQueue:
2 def __init__(self, n: int):
3 """
4 Initialize the MRU (Most Recently Used) Queue with n sequential elements.
5
6 Args:
7 n: The number of elements to initialize the queue with (1 to n).
8 """
9 # Create a list containing elements from 1 to n
10 self.queue = list(range(1, n + 1))
11
12 def fetch(self, k: int) -> int:
13 """
14 Fetch the k-th element from the queue and move it to the end (mark as most recently used).
15
16 Args:
17 k: The 1-indexed position of the element to fetch.
18
19 Returns:
20 The value of the k-th element.
21 """
22 # Get the element at position k (converting to 0-indexed)
23 element = self.queue[k - 1]
24
25 # Remove the element from its current position
26 del self.queue[k - 1]
27
28 # Append the element to the end of the queue (marking it as most recently used)
29 self.queue.append(element)
30
31 return element
32
33
34# Your MRUQueue object will be instantiated and called as such:
35# obj = MRUQueue(n)
36# param_1 = obj.fetch(k)
37
1/**
2 * Binary Indexed Tree (Fenwick Tree) for efficient range sum queries and updates
3 */
4class BinaryIndexedTree {
5 private int size;
6 private int[] tree;
7
8 /**
9 * Initialize Binary Indexed Tree with given size
10 * @param n the size of the tree
11 */
12 public BinaryIndexedTree(int n) {
13 this.size = n;
14 this.tree = new int[n + 1]; // 1-indexed array for BIT
15 }
16
17 /**
18 * Update the value at position x by adding delta
19 * @param x the position to update (1-indexed)
20 * @param delta the value to add
21 */
22 public void update(int x, int delta) {
23 while (x <= size) {
24 tree[x] += delta;
25 x += x & -x; // Move to next position using lowbit operation
26 }
27 }
28
29 /**
30 * Query the prefix sum from 1 to x
31 * @param x the end position (1-indexed)
32 * @return the sum of elements from 1 to x
33 */
34 public int query(int x) {
35 int sum = 0;
36 while (x > 0) {
37 sum += tree[x];
38 x -= x & -x; // Move to parent position using lowbit operation
39 }
40 return sum;
41 }
42}
43
44/**
45 * MRU Queue implementation that supports fetching the k-th element
46 * and moving it to the end (most recently used position)
47 */
48class MRUQueue {
49 private int currentSize;
50 private int[] queue;
51 private BinaryIndexedTree fenwickTree;
52
53 /**
54 * Initialize MRU Queue with elements from 1 to n
55 * @param n the initial number of elements
56 */
57 public MRUQueue(int n) {
58 this.currentSize = n;
59 // Allocate extra space (2010) for future additions when elements are moved to end
60 queue = new int[n + 2010];
61
62 // Initialize queue with values 1 to n
63 for (int i = 1; i <= n; ++i) {
64 queue[i] = i;
65 }
66
67 // Initialize Fenwick Tree to track deleted positions
68 fenwickTree = new BinaryIndexedTree(n + 2010);
69 }
70
71 /**
72 * Fetch the k-th element from the queue and move it to the end
73 * @param k the position of element to fetch (1-indexed)
74 * @return the value of the k-th element
75 */
76 public int fetch(int k) {
77 // Binary search to find the actual position of k-th element
78 // accounting for deleted positions
79 int left = 1, right = currentSize;
80
81 while (left < right) {
82 int mid = (left + right) >> 1;
83 // mid - query(mid) gives the number of active elements up to position mid
84 // (subtracting deleted positions)
85 if (mid - fenwickTree.query(mid) >= k) {
86 right = mid;
87 } else {
88 left = mid + 1;
89 }
90 }
91
92 // Get the element value at the found position
93 int elementValue = queue[left];
94
95 // Move the element to the end of the queue
96 queue[++currentSize] = elementValue;
97
98 // Mark the original position as deleted by updating the Fenwick Tree
99 fenwickTree.update(left, 1);
100
101 return elementValue;
102 }
103}
104
105/**
106 * Your MRUQueue object will be instantiated and called as such:
107 * MRUQueue obj = new MRUQueue(n);
108 * int param_1 = obj.fetch(k);
109 */
110
1class BinaryIndexedTree {
2public:
3 /**
4 * Constructor: Initialize a Binary Indexed Tree (Fenwick Tree) with size n
5 * @param n: The size of the tree
6 */
7 BinaryIndexedTree(int n) : size(n), tree(n + 1, 0) {}
8
9 /**
10 * Update the tree by adding delta to position index
11 * @param index: The 1-indexed position to update
12 * @param delta: The value to add at the position
13 */
14 void update(int index, int delta) {
15 while (index <= size) {
16 tree[index] += delta;
17 index += index & (-index); // Move to next node affected by this update
18 }
19 }
20
21 /**
22 * Query the prefix sum from position 1 to index
23 * @param index: The 1-indexed position to query up to
24 * @return: The sum of elements from 1 to index
25 */
26 int query(int index) {
27 int sum = 0;
28 while (index > 0) {
29 sum += tree[index];
30 index -= index & (-index); // Move to parent node
31 }
32 return sum;
33 }
34
35private:
36 int size; // Size of the tree
37 vector<int> tree; // The tree array storing partial sums
38};
39
40class MRUQueue {
41public:
42 /**
43 * Constructor: Initialize MRU Queue with n elements from 1 to n
44 * @param n: Number of initial elements in the queue
45 */
46 MRUQueue(int n) {
47 // Initialize queue with dummy element at index 0 and values 1 to n
48 queue.resize(n + 1);
49 iota(queue.begin() + 1, queue.end(), 1);
50
51 // Create BIT with extra capacity for future insertions (2010 operations)
52 fenwickTree = new BinaryIndexedTree(n + 2010);
53 }
54
55 /**
56 * Fetch the k-th element and move it to the end of the queue
57 * @param k: The 1-indexed position of the element to fetch
58 * @return: The value of the k-th element
59 */
60 int fetch(int k) {
61 // Binary search to find the actual position considering removed elements
62 int left = 1, right = queue.size();
63
64 while (left < right) {
65 int mid = (left + right) >> 1;
66 // Calculate effective position: actual position - number of removed elements before it
67 int effectivePosition = mid - fenwickTree->query(mid);
68
69 if (effectivePosition >= k) {
70 right = mid;
71 } else {
72 left = mid + 1;
73 }
74 }
75
76 // Get the element at the found position
77 int element = queue[left];
78
79 // Move element to the end by appending it
80 queue.push_back(element);
81
82 // Mark the original position as removed in the BIT
83 fenwickTree->update(left, 1);
84
85 return element;
86 }
87
88private:
89 vector<int> queue; // The queue storing elements
90 BinaryIndexedTree* fenwickTree; // BIT to track removed positions
91};
92
93/**
94 * Your MRUQueue object will be instantiated and called as such:
95 * MRUQueue* obj = new MRUQueue(n);
96 * int param_1 = obj->fetch(k);
97 */
98
1// Binary Indexed Tree (Fenwick Tree) for efficient range sum queries and updates
2let treeSize: number;
3let treeArray: number[];
4
5// Initialize the Binary Indexed Tree with given size
6function initializeBIT(n: number): void {
7 treeSize = n;
8 treeArray = new Array(n + 1).fill(0);
9}
10
11// Update the tree by adding value v at position x
12// Uses the BIT update pattern: move to next index by adding lowbit
13function updateBIT(x: number, v: number): void {
14 while (x <= treeSize) {
15 treeArray[x] += v;
16 x += x & -x; // Add lowbit to move to next responsible node
17 }
18}
19
20// Query the prefix sum from index 1 to x
21// Uses the BIT query pattern: move to parent by removing lowbit
22function queryBIT(x: number): number {
23 let sum = 0;
24 while (x > 0) {
25 sum += treeArray[x];
26 x -= x & -x; // Remove lowbit to move to parent node
27 }
28 return sum;
29}
30
31// MRU Queue implementation using Binary Indexed Tree
32let queue: number[];
33let queueBIT: { treeSize: number; treeArray: number[] };
34
35// Constructor for MRUQueue - initializes queue with elements 1 to n
36function MRUQueue(n: number): void {
37 // Initialize queue with values from 1 to n
38 queue = new Array(n + 1);
39 for (let i = 1; i <= n; i++) {
40 queue[i] = i;
41 }
42
43 // Initialize BIT with extra space (2010) for future insertions
44 const bitSize = n + 2010;
45 queueBIT = {
46 treeSize: bitSize,
47 treeArray: new Array(bitSize + 1).fill(0)
48 };
49}
50
51// Fetch the k-th element and move it to the end (Most Recently Used)
52function fetch(k: number): number {
53 // Binary search to find the actual position of k-th element
54 // accounting for elements that have been moved (marked in BIT)
55 let left = 1;
56 let right = queue.length;
57
58 while (left < right) {
59 const mid = (left + right) >> 1; // Equivalent to Math.floor((left + right) / 2)
60
61 // Calculate actual position: original position - number of moved elements before it
62 const actualPosition = mid - queryBITForMRU(mid);
63
64 if (actualPosition >= k) {
65 right = mid;
66 } else {
67 left = mid + 1;
68 }
69 }
70
71 // Get the element at the found position
72 const element = queue[left];
73
74 // Move element to the end of the queue
75 queue.push(element);
76
77 // Mark this position as moved in the BIT
78 updateBITForMRU(left, 1);
79
80 return element;
81}
82
83// Helper function to query BIT for MRUQueue
84function queryBITForMRU(x: number): number {
85 let sum = 0;
86 let index = x;
87 while (index > 0) {
88 sum += queueBIT.treeArray[index];
89 index -= index & -index;
90 }
91 return sum;
92}
93
94// Helper function to update BIT for MRUQueue
95function updateBITForMRU(x: number, v: number): void {
96 let index = x;
97 while (index <= queueBIT.treeSize) {
98 queueBIT.treeArray[index] += v;
99 index += index & -index;
100 }
101}
102
Time and Space Complexity
Time Complexity:
__init__(n)
:O(n)
- Creating a list of n elements from 1 to n+1 requires linear time.fetch(k)
:O(n)
- The slice deletion operationself.q[k - 1 : k] = []
requiresO(n-k)
time in the worst case because Python needs to shift all elements after position k-1 to the left by one position. Theappend
operation takesO(1)
amortized time. Overall, the fetch operation isO(n)
.
Space Complexity:
O(n)
- The class maintains a listself.q
that stores n elements. No additional space that scales with input size is used during operations, so the overall space complexity isO(n)
.
Learn more about how to find time and space complexity quickly.
Common Pitfalls
1. Index Confusion: 1-indexed vs 0-indexed
The most common mistake is forgetting that the problem uses 1-based indexing while Python lists use 0-based indexing.
Incorrect Implementation:
def fetch(self, k: int) -> int:
element = self.queue[k] # Wrong! This accesses the (k+1)th element
del self.queue[k]
self.queue.append(element)
return element
Why it fails: When fetch(1)
is called to get the first element, self.queue[1]
actually accesses the second element.
Correct Solution:
def fetch(self, k: int) -> int:
element = self.queue[k - 1] # Correct: Convert to 0-indexed
del self.queue[k - 1]
self.queue.append(element)
return element
2. Modifying List While Accessing It
Some developers try to remove and access in a single operation without storing the value first.
Incorrect Implementation:
def fetch(self, k: int) -> int:
self.queue.append(self.queue.pop(k - 1))
return self.queue[-1] # Wrong! Returns the moved element, but risky
Why it's problematic: While this might work, it's less clear and could lead to bugs if the logic needs to be extended. Additionally, if an exception occurs during pop
, you lose the element.
Better Solution:
def fetch(self, k: int) -> int:
element = self.queue[k - 1] # Store first
del self.queue[k - 1] # Then remove
self.queue.append(element) # Then append
return element # Finally return
3. Inefficient Element Removal
Using inefficient methods to remove elements from the middle of the list.
Inefficient Implementation:
def fetch(self, k: int) -> int:
element = self.queue[k - 1]
new_queue = []
for i, val in enumerate(self.queue):
if i != k - 1:
new_queue.append(val)
new_queue.append(element)
self.queue = new_queue
return element
Why it's inefficient: This creates an entirely new list and iterates through all elements, using O(n) extra space unnecessarily.
Optimal Solution:
def fetch(self, k: int) -> int:
element = self.queue[k - 1]
del self.queue[k - 1] # or self.queue.pop(k - 1)
self.queue.append(element)
return element
4. Not Handling Edge Cases
Failing to consider boundary conditions like fetching the last element.
Potential Issue:
When k
equals the length of the queue (fetching the last element), the element is already at the end. While the current implementation handles this correctly (remove and re-append), developers might try to "optimize" this case incorrectly:
def fetch(self, k: int) -> int:
if k == len(self.queue): # "Optimization" attempt
return self.queue[-1] # Wrong! Doesn't move the element
element = self.queue[k - 1]
del self.queue[k - 1]
self.queue.append(element)
return element
Why it fails: Even when fetching the last element, the operation should be consistent - the element should be removed and re-appended to maintain the MRU semantics properly.
Correct Approach: Treat all positions uniformly without special cases:
def fetch(self, k: int) -> int:
element = self.queue[k - 1]
del self.queue[k - 1]
self.queue.append(element)
return element
Which data structure is used to implement priority queue?
Recommended Readings
Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you
Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask
Want a Structured Path to Master System Design Too? Don’t Miss This!