Problem Informations

• Problem Index: 1756
• Problem Link: Design Most Recently Used Queue
• Topics: Array, Hash Table, Stack, Design, Binary Indexed Tree, Ordered Set

Problem Description

Design a queue-like data structure that moves the most recently used element to the end of the queue.

Implement the MRUQueue class:

• MRUQueue(int n) constructs the MRUQueue with $n$ elements: $[1,2,3,\ldots,n]$.
• int fetch(int k) moves the $k$th element (1-indexed) to the end of the queue and returns it.

Example 1:

Input:

["MRUQueue", "fetch", "fetch", "fetch", "fetch"]
[[8], [3], [5], [2], [8]]

Output:

[null, 3, 6, 2, 2]

Explanation:

MRUQueue mRUQueue = new MRUQueue(8); // Initializes the queue to [1,2,3,4,5,6,7,8].
mRUQueue.fetch(3); // Moves the 3rd element (3) to the end of the queue to become [1,2,4,5,6,7,8,3] and returns it.
mRUQueue.fetch(5); // Moves the 5th element (6) to the end of the queue to become [1,2,4,5,7,8,3,6] and returns it.
mRUQueue.fetch(2); // Moves the 2nd element (2) to the end of the queue to become [1,4,5,7,8,3,6,2] and returns it.
mRUQueue.fetch(8); // The 8th element (2) is already at the end of the queue so just return it.

Constraints:

• $1 \leq n \leq 2000$
• $1 \leq k \leq n$
• At most 2000 calls will be made to fetch.

Follow up:

Finding an $O(n)$ algorithm per fetch is a bit easy. Can you find an algorithm with a better complexity for each fetch call?

Intuition

The problem requires designing a queue-like data structure that allows accessing and rearranging its elements based on their usage. The primary operation involves moving a specified element to the end of the queue, marking it as the most recently used. The structure is intuitive as it mimics a common real-world scenario where frequently accessed items are kept readily accessible.

Approach

The solution employs a simple yet effective data structure—a vector in C++—to implement the MRU (Most Recently Used) Queue. Here is the step-by-step approach:

1. Initialization:

   • The constructor initializes a vector to simulate the queue, populating it with integers from 1 to $n$. This represents the initial state of the MRUQueue, with all elements sequentially arranged.

2. Fetch Operation:

   • The fetch method is designed to manipulate the queue by accessing the $k$-th element, moving it to the end of the queue, and returning its value.
   • The algorithm works as follows:
     • The element at the $(k-1)$-th position (due to 0-based indexing in C++) is accessed and appended to the end of the vector. This marks the element as the most recently used.
     • The original $k$-th element is then removed from its position in the vector to maintain consistency and avoid duplicates in the data structure.
     • Finally, the method returns the value of the element that was moved to the end, which can be directly accessed using the back method of the vector.

By leveraging the vector’s dynamic array properties—efficient access and modification—the solution achieves the required operations. The complexity of the fetch operation is dominated by the need to shift elements when erasing, which makes it $O(n)$ in the worst case; however, this remains acceptable given the problem constraints.

Code

C++

class MRUQueue {
public:
    // Vector to store the elements of the MRUQueue
    vector<int> queue;

    // Constructor to initialize the queue with elements from 1 to n
    MRUQueue(int n) {
        for (int i = 1; i <= n; i++) {
            queue.emplace_back(i);
        }
    }

    // Fetch the k-th element (1-indexed), move it to the end, and return it
    int fetch(int k) {
        // Add the k-th element to the end of the queue
        queue.push_back(queue[k - 1]);
        // Remove the original k-th element from its position
        queue.erase(queue.begin() + k - 1);
        // Return the recently moved element
        return queue.back();
    }
};

/**
 * Your MRUQueue object will be instantiated and called as such:
 * MRUQueue* obj = new MRUQueue(n);
 * int param_1 = obj->fetch(k);
 */

Python

class MRUQueue:
    # List to store the elements of the MRUQueue
    queue = []

    # Constructor to initialize the queue with elements from 1 to n
    def __init__(self, n):
        for i in range(1, n + 1):
            self.queue.append(i)

    # Fetch the k-th element (1-indexed), move it to the end, and return it
    def fetch(self, k):
        # Add the k-th element to the end of the queue
        self.queue.append(self.queue[k - 1])
        # Remove the original k-th element from its position
        self.queue.pop(k - 1)
        # Return the recently moved element
        return self.queue[-1]

# Your MRUQueue object will be instantiated and called as such:
# obj = MRUQueue(n)
# param_1 = obj.fetch(k)

Complexity

• Time complexity: The time complexity for the fetch operation is $O(n)$. This is because the fetch function involves both inserting an element at the end of the vector and removing an element from the middle. Removing an element from the beginning or middle of a vector requires shifting subsequent elements, which takes $O(n)$ time in the worst case where $n$ is the current number of elements in the vector.
• Space complexity: The space complexity is $O(n)$. The space used by the MRUQueue is proportional to the number of elements in the queue, which is initialized with $n$ elements, where $n$ is the maximum size allowed (up to 2000 as given in the constraints).