Problem Description

The "Design Most Recently Used Queue" problem asks you to implement a special data structure called MRUQueue that behaves like a queue but with an extra operation. Given an initial queue containing the integers from 1 to n (in order), you must support two operations:

• MRUQueue(int n): Initializes the queue with the integers 1 to n in order (front to back).
• fetch(int k): Finds and removes the k-th element in the queue (1-based index), then appends it to the end of the queue, and returns its value.

Key constraints:

• Each fetch call always refers to a valid position in the queue.
• Elements are never duplicated or lost; they are only moved to the back.
• The queue always contains the same set of numbers, just in different orders.

Thought Process

At first glance, this problem seems similar to a standard queue, but the fetch operation is not typical: it requires us to access and move an arbitrary element efficiently. A brute-force approach would be to use a simple list or array and, for each fetch(k), remove the element at index k-1 and append it to the end. However, removing from the middle of a list is costly (O(n)), especially for large n and many operations.

Thus, we need a data structure that allows:

• Fast access by index (to find the k-th element)
• Efficient removal and insertion at arbitrary positions

For this problem, since constraints are moderate (n ≤ 2000 in Leetcode), a simple list/array is sufficient and acceptable. But we should be aware of more advanced techniques for larger constraints.

Solution Approach

Here’s how we can implement the MRUQueue:

1. Initialization:
   • Store the queue as a list/array, initialized with integers 1 to n.
2. fetch(k):
   • Access the k-1 index of the list (since Python, Java, C++ and JS use 0-based indexing).
   • Remove the element at that index (O(n) for array/list, but acceptable for small n).
   • Append it to the end of the list.
   • Return the value.

Why this works: The problem's constraints allow for this approach. For larger n, we’d consider a block-linked list or balanced BST with order-statistics for O(log n) access and movement.

Example Walkthrough

Suppose n = 5, so the initial queue is: [1, 2, 3, 4, 5].

1. fetch(3):
   • The 3rd element is 3. Remove it: [1, 2, 4, 5].
   • Append 3 to the end: [1, 2, 4, 5, 3].
   • Return 3.
2. fetch(5):
   • The 5th element is 3. Remove it: [1, 2, 4, 5].
   • Append 3 to the end: [1, 2, 4, 5, 3].
   • Return 3.
3. fetch(2):
   • The 2nd element is 2. Remove it: [1, 4, 5, 3].
   • Append 2 to the end: [1, 4, 5, 3, 2].
   • Return 2.

At each step, the queue is updated by moving the fetched element to the back, and the order is maintained.

Time and Space Complexity

Brute-force (list/array):

• Each fetch(k) is O(n) due to removal from the middle and append at the end.
• If there are m operations, total time is O(mn).
• Space is O(n) for the queue.

• Using a balanced BST or block-linked list, each operation can be O(log n).
• But for the given constraints, the brute-force is sufficient.

Summary

The Most Recently Used Queue problem requires efficiently moving arbitrary elements to the back of a queue. For small to moderate sizes, a simple list-based approach is effective and easy to implement. For larger data, more advanced data structures could be used to optimize access and movement. The key insight is recognizing the trade-off between simplicity and efficiency, and that for the given constraints, a straightforward solution is both correct and practical.

Code Implementation

class MRUQueue:

    def __init__(self, n: int):
        self.q = list(range(1, n + 1))

    def fetch(self, k: int) -> int:
        val = self.q.pop(k - 1)
        self.q.append(val)
        return val
      

class MRUQueue {
public:
    vector<int> q;
    MRUQueue(int n) {
        q.resize(n);
        for (int i = 0; i < n; ++i) q[i] = i + 1;
    }
    int fetch(int k) {
        int val = q[k - 1];
        q.erase(q.begin() + k - 1);
        q.push_back(val);
        return val;
    }
};
      

class MRUQueue {
    List<Integer> q;
    public MRUQueue(int n) {
        q = new ArrayList<>();
        for (int i = 1; i <= n; ++i) q.add(i);
    }
    public int fetch(int k) {
        int val = q.remove(k - 1);
        q.add(val);
        return val;
    }
}
      

var MRUQueue = function(n) {
    this.q = [];
    for (let i = 1; i <= n; ++i) this.q.push(i);
};

MRUQueue.prototype.fetch = function(k) {
    let val = this.q.splice(k - 1, 1)[0];
    this.q.push(val);
    return val;
};