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:

text
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.

Core Insight for Design Most Recently Used Queue

The core insight for LeetCode 1756 lies in analyzing the constraints and the nature of the operations.

1. Constraints: $n \le 2000$ and total operations $\le 2000$. This is a relatively small input size.
2. Operations: We need to access an element by its current index (1-based) and move it to the end.
3. Data Structure Choice: A Dynamic Array (like std::vector in C++, ArrayList in Java, or list in Python) supports:
   • Random Access: Accessing the element at index i is $O(1)$.
   • Append: Adding to the end is amortized $O(1)$.
   • Removal: Removing at index i is $O(n)$ because subsequent elements must shift left.

Given the constraints, an $O(n)$ operation per fetch results in a total complexity of roughly $2000 \times 2000 = 4 \times 10^6$ operations, which is well within the typical execution time limit (usually allowing $\sim 10^8$ operations per second). Therefore, the most pragmatic design is a direct simulation using a dynamic array.

Visual Description: Imagine the queue as a contiguous block of memory. When fetch(k) is called, we locate the slot at index $k-1$. We extract the value, causing a "gap." The block of memory to the right of the gap shifts left to fill it. Finally, the extracted value is placed in the newly available slot at the far right end of the block.

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.

Reference Implementation

C++ Solution for LeetCode 1756

cpp
#include <vector>
#include <numeric>

class MRUQueue {
private:
    std::vector<int> queue;

public:
    MRUQueue(int n) {
        // Reserve memory to avoid reallocations
        queue.reserve(n);
        for (int i = 1; i <= n; ++i) {
            queue.push_back(i);
        }
    }
    
    int fetch(int k) {
        // Convert 1-based index to 0-based
        int index = k - 1;
        
        // Retrieve the element
        int val = queue[index];
        
        // Remove the element at the specific index
        // erase shifts elements after 'index' to the left -> O(N)
        queue.erase(queue.begin() + index);
        
        // Add the element to the end -> O(1)
        queue.push_back(val);
        
        return val;
    }
};

Java Solution for LeetCode 1756

java
import java.util.ArrayList;
import java.util.List;

class MRUQueue {
    private List<Integer> queue;

    public MRUQueue(int n) {
        queue = new ArrayList<>(n);
        for (int i = 1; i <= n; i++) {
            queue.add(i);
        }
    }
    
    public int fetch(int k) {
        // ArrayList.remove(int index) removes the element and returns it.
        // It also shifts subsequent elements to the left.
        // k is 1-based, so we access k-1.
        int val = queue.remove(k - 1);
        
        // Add the element to the end of the list
        queue.add(val);
        
        return val;
    }
}

Python Solution for LeetCode 1756

python
class MRUQueue:

    def __init__(self, n: int):
        # Initialize list with 1 to n
        self.queue = list(range(1, n + 1))

    def fetch(self, k: int) -> int:
        # pop(index) removes the element at the index and returns it.
        # Elements shift automatically. k is 1-based, so use k-1.
        val = self.queue.pop(k - 1)
        
        # Append the value to the end of the list
        self.queue.append(val)
        
        return val