Design Most Recently Used Queue

LeetCode 1756: Design Most Recently Used Queue Solution & Explanation

Problem Overview

TL;DR: The optimal solution for the given constraints uses a dynamic array (vector/list) to directly access the $k$-th element, remove it, and append it to the end of the list in $O(n)$ time.

The "Design Most Recently Used Queue" problem asks us to implement a specialized queue data structure initialized with integers from 1 to n. The key requirement is the fetch(k) operation, which retrieves the k-th element (1-indexed) from the current sequence, removes it from its current position, and moves it to the very end of the queue. We must return the value of the fetched element.

This is a LeetCode 1756 Solution that focuses on clean class design and efficient simulation of the required behavior.

Brute Force Approach for Design Most Recently Used Queue

A brute force approach often attempts to strictly adhere to the definition of a "Queue" (FIFO) without leveraging random access.

1. Storage: Use a standard Queue data structure (e.g., std::queue or LinkedList).
2. Fetch(k):
   • Dequeue the first k-1 elements and store them in a temporary buffer (or rotate them to the back).
   • Dequeue the k-th element (the target).
   • Restore the order of the k-1 elements at the front (if using a buffer) or accept the rotation.
   • Enqueue the target element at the very end.

Pseudo-code:

function fetch(k):
    temp_list = []
    for i from 1 to k-1:
        temp_list.add(queue.dequeue())
    
    target = queue.dequeue()
    
    // Restore elements to front (difficult with standard Queue)
    // Or reconstruct entire queue
    new_queue = new Queue()
    for item in temp_list: new_queue.enqueue(item)
    while queue is not empty: new_queue.enqueue(queue.dequeue())
    new_queue.enqueue(target)
    queue = new_queue
    return target

Complexity Analysis:

• Time: $O(n)$ per fetch operation, as we may need to traverse or reconstruct the entire queue.
• Space: $O(n)$ for the temporary buffer.

Why it is suboptimal: While technically $O(n)$, the constant factors are high due to repeated memory allocation and object movement. Furthermore, using a pure Queue abstraction makes accessing the $k$-th element cumbersome compared to random-access data structures. This approach struggles with code complexity and efficiency compared to using a dynamic array.

Algorithm Strategy: Design Patterns

We apply the Design pattern by encapsulating a dynamic array within our class. We maintain the invariant that the array always contains the current state of the queue in the correct order.

1. Initialization:

   • Create a dynamic array.
   • Populate it with integers $1$ through $n$ sequentially.

2. Fetch Operation:

   • Validate/Map Index: Convert the 1-based input k to a 0-based index (k-1).
   • Retrieve: Read the value at this index.
   • Remove: Delete the element at this index. The underlying container handles the shifting of subsequent elements.
   • Append: Add the retrieved value to the end of the array.
   • Return: Output the value.

This strategy leverages the standard library's optimized implementations of array manipulation, ensuring code correctness and readability, which is paramount in Design interviews.

Execution Flow

Let's trace n = 4 (Queue: [1, 2, 3, 4]) and fetch(3).

1. Initial State: Internal list is [1, 2, 3, 4].
2. Call fetch(3):
   • Target index is 3 - 1 = 2.
   • Element at index 2 is 3.
   • Remove: We remove 3. The list shifts: [1, 2, 4].
   • Append: We add 3 to the end. The list becomes: [1, 2, 4, 3].
   • Return: Return 3.
3. Next Call fetch(2):
   • Current list: [1, 2, 4, 3].
   • Target index is 2 - 1 = 1.
   • Element at index 1 is 2.
   • Remove: Remove 2. List shifts: [1, 4, 3].
   • Append: Add 2 to end. List becomes: [1, 4, 3, 2].
   • Return: Return 2.

Proof of Correctness

The algorithm is correct by simulation.

1. Initialization: The array explicitly starts with [1, ..., n], satisfying the initial condition.
2. Indexing: By mapping input k to k-1, we correctly access the $k$-th element in a 0-indexed array.
3. Order Maintenance: The remove operation in dynamic arrays preserves the relative order of all remaining elements. The append operation places the element at the logical end. This strictly follows the problem's definition of the MRU move.
4. Termination: Each operation performs a finite number of steps (removal and addition), guaranteeing termination.

Pattern Reuse Notes

The Design pattern and the concept of moving elements based on access frequency appear in several other popular interview questions:

• LeetCode 146: LRU Cache - Requires moving accessed elements to the "most recently used" position (usually head or tail), typically implemented with a Doubly Linked List and Hash Map for $O(1)$ access.
• LeetCode 155: Min Stack - Focuses on designing a class that maintains auxiliary state (minimum value) alongside standard stack operations.
• LeetCode 225: Implement Stack using Queues - Manipulating data order to simulate a different data structure's behavior.
• LeetCode 232: Implement Queue using Stacks - Similar to above, emphasizing the importance of internal state management.

Reference Implementation

C++ Solution for LeetCode 1756

1#include <vector>
2#include <numeric>
3
4class MRUQueue {
5private:
6    std::vector<int> queue;
7
8public:
9    MRUQueue(int n) {
10        // Reserve memory to avoid reallocations
11        queue.reserve(n);
12        for (int i = 1; i <= n; ++i) {
13            queue.push_back(i);
14        }
15    }
16    
17    int fetch(int k) {
18        // Convert 1-based index to 0-based
19        int index = k - 1;
20        
21        // Retrieve the element
22        int val = queue[index];
23        
24        // Remove the element at the specific index
25        // erase shifts elements after 'index' to the left -> O(N)
26        queue.erase(queue.begin() + index);
27        
28        // Add the element to the end -> O(1)
29        queue.push_back(val);
30        
31        return val;
32    }
33};

Java Solution for LeetCode 1756

1import java.util.ArrayList;
2import java.util.List;
3
4class MRUQueue {
5    private List<Integer> queue;
6
7    public MRUQueue(int n) {
8        queue = new ArrayList<>(n);
9        for (int i = 1; i <= n; i++) {
10            queue.add(i);
11        }
12    }
13    
14    public int fetch(int k) {
15        // ArrayList.remove(int index) removes the element and returns it.
16        // It also shifts subsequent elements to the left.
17        // k is 1-based, so we access k-1.
18        int val = queue.remove(k - 1);
19        
20        // Add the element to the end of the list
21        queue.add(val);
22        
23        return val;
24    }
25}

Python Solution for LeetCode 1756

1class MRUQueue:
2
3    def __init__(self, n: int):
4        # Initialize list with 1 to n
5        self.queue = list(range(1, n + 1))
6
7    def fetch(self, k: int) -> int:
8        # pop(index) removes the element at the index and returns it.
9        # Elements shift automatically. k is 1-based, so use k-1.
10        val = self.queue.pop(k - 1)
11        
12        # Append the value to the end of the list
13        self.queue.append(val)
14        
15        return val