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

# 1756. Design Most Recently Used Queue

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"]
[, , , , ]
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.

• 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);
*/