Formatted question description: https://leetcode.ca/all/1756.html

1756. Design Most Recently Used Queue

Level

Medium

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,...,n].
• 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 <= n <= 2000
• 1 <= k <= 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?

Solution

Use an array to represent the queue.

In the constructor, initialize the array with length n and elements from 1 to n.

In method fetch, fetch the element at the given index, move the elements after the element to the previous indices, put the element at the last index, and return the element.

Follow up

• better than o(N) fetch, first thought is binary search.
• but worst case it could be still o(N), on average it will be better than flat o(N)

Java

class MRUQueue {
    int size;
    int[] queue;

    public MRUQueue(int n) {
        size = n;
        queue = new int[n];
        for (int i = 0; i < n; i++)
            queue[i] = i + 1;
    }
    
    public int fetch(int k) {
        int num = queue[k - 1];
        for (int i = k; i < size; i++)
            queue[i - 1] = queue[i];
        queue[size - 1] = num;
        return num;
    }
}

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

All Problems

All Solutions