Leetcode 1756. Design Most Recently Used Queue — Squarespace

Problem

Design a special queue data structure that maintains elements in order of their most recent access. The queue should support two primary operations:

enqueue(val): Add a new value to the end of the queue (most recent position)
fetch(k): Retrieve the element at position k (using 1-based indexing), then automatically move that element to the end of the queue (making it the most recently accessed)

The queue is initialized with a capacity parameter n, though the actual number of elements may vary based on operations performed.

The key challenge is implementing the fetch operation efficiently. When you fetch an element at position k, you must return its value and reposition it to the end of the queue, shifting other elements as needed.

Requirements

Implement a constructor MRUQueue(n) that initializes the queue with capacity n
Implement enqueue(val) to add a value to the end of the queue
Implement fetch(k) to return the element at position k (1-indexed) and move it to the end
After a fetch(k) operation, the fetched element should be at the most recent position (end)
Elements that were after position k should shift left by one position
Maintain correct ordering after multiple operations

Constraints

1 ≤ n ≤ 2000
1 ≤ val ≤ 10^6
1 ≤ k ≤ current queue size
At most 2000 calls will be made to enqueue and fetch combined
You may assume all fetch operations use valid indices

Examples

Example 1:

` Operations: MRUQueue mru = new MRUQueue(5) mru.enqueue(10) mru.enqueue(20) mru.enqueue(30) mru.fetch(2)

Output: 20 Explanation:

Initially queue is empty
After enqueue(10): [10]
After enqueue(20): [10, 20]
After enqueue(30): [10, 20, 30]
fetch(2) returns 20 (at position 2) and moves it to end: [10, 30, 20] `

Example 2:

` Operations: MRUQueue mru = new MRUQueue(3) mru.enqueue(5) mru.enqueue(10) mru.enqueue(15) mru.fetch(3) mru.fetch(2)

Output: fetch(3) returns 15, fetch(2) returns 10 Explanation:

After enqueues: [5, 10, 15]
fetch(3) returns 15, queue becomes: [5, 10, 15]
fetch(2) returns 10, queue becomes: [5, 15, 10] `

Example 3:

` Operations: MRUQueue mru = new MRUQueue(4) mru.enqueue(1) mru.enqueue(2) mru.enqueue(3) mru.fetch(1) mru.enqueue(4) mru.fetch(2)

Output: fetch(1) returns 1, fetch(2) returns 3 Explanation:

After first three enqueues: [1, 2, 3]
fetch(1) returns 1, queue becomes: [2, 3, 1]
enqueue(4): [2, 3, 1, 4]
fetch(2) returns 3, queue becomes: [2, 1, 4, 3] `

Hint 1: Data Structure Choice The simplest approach uses a list/array to store elements. While not optimal for very large inputs, it provides straightforward implementation and is acceptable given the constraint limits. The fetch operation requires removing an element from the middle and appending it to the end.

Hint 2: Array Implementation For the array approach, you can use pop(index) to remove the element at position k-1 (converting from 1-indexed to 0-indexed) and append() to add it to the end. This gives O(n) time for fetch operations but O(1) for enqueue, which is acceptable for the given constraints.

Hint 3: Optimization Consideration For a more optimized solution handling many fetch operations on large queues, consider using a data structure that supports efficient removal from arbitrary positions, such as a combination of a linked list for ordering and a hash map for quick access. However, for the given constraints (n ≤ 2000), a simple array is sufficient.

Full Solution ` class MRUQueue: def init(self, n: int): """ Initialize the queue with capacity n. We use a simple list to store elements. """ self.queue = []
def enqueue(self, val: int) -> None:
    """
    Add a value to the end of the queue.
    Time Complexity: O(1)
    """
    self.queue.append(val)

def fetch(self, k: int) -> int:
    """
    Retrieve the element at position k (1-indexed),
    then move it to the most recent position (end of queue).
    Time Complexity: O(n) due to list removal from middle
    """
    # Convert to 0-indexed
    index = k - 1
    
    # Get the value at position k
    val = self.queue[index]
    
    # Remove it from its current position
    self.queue.pop(index)
    
    # Add it to the end (most recent position)
    self.queue.append(val)
    
    return val
`

Approach Explanation:

The solution uses a straightforward list-based implementation:

Initialization: Store elements in a list that represents the queue in access order

Enqueue: Simply append to the end of the list - O(1) operation

Fetch:

Convert the 1-indexed position to 0-indexed

Retrieve the value at that position

Remove it from the current position using pop(index) - O(n) operation

Append it to the end to make it most recently accessed - O(1) operation

Return the value

Time Complexity:

enqueue: O(1) - appending to a list

fetch: O(n) - removing from middle of list requires shifting elements

Space Complexity: O(n) where n is the number of elements in the queue

Alternative Optimization:

For scenarios with many fetch operations, you could optimize using:

A doubly-linked list for O(1) removal and insertion

A hash map to store node references for O(1) lookup

This would make fetch O(1) but adds complexity

However, given the constraints (at most 2000 operations, n ≤ 2000), the simple array solution is both correct and efficient enough.