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