1756. Design Most Recently Used Queue 🔒

MediumStackDesignBinary Indexed TreeArrayHash TableOrdered Set

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 parameter n, 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

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
Call fetch(2):
- The 2nd element is now 2
- Move 2 to the end: Queue becomes [1, 4, 5, 3, 2]
- Return 2

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

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

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 to n using list(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
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 to k (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 list
fetch: 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 Evaluator

Example 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 is 2
Step 2: Remove element 2 using slice self.q[1:2] = []
- Queue becomes: [1, 3, 4]
Step 3: Append 2 to the end
- Queue becomes: [1, 3, 4, 2]
Step 4: Return 2

Second fetch operation: fetch(3)

result = mru.fetch(3)

Step 1: Access element at index 3-1 = 2, which is 4
Step 2: Remove element 4 using slice self.q[2:3] = []
- Queue becomes: [1, 3, 2]
Step 3: Append 4 to the end
- Queue becomes: [1, 3, 2, 4]
Step 4: Return 4

Third fetch operation: fetch(1)

result = mru.fetch(1)

Step 1: Access element at index 1-1 = 0, which is 1
Step 2: Remove element 1 using slice self.q[0:1] = []
- Queue becomes: [3, 2, 4]
Step 3: Append 1 to the end
- Queue becomes: [3, 2, 4, 1]
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 operation self.q[k - 1 : k] = [] requires O(n-k) time in the worst case because Python needs to shift all elements after position k-1 to the left by one position. The append operation takes O(1) amortized time. Overall, the fetch operation is O(n).

Space Complexity:

O(n) - The class maintains a list self.q that stores n elements. No additional space that scales with input size is used during operations, so the overall space complexity is O(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

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

Linear Search

Binary Search

Quick Select

Hash Set

I don't know