##### Welcome to Subscribe On Youtube

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

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

############

class BinaryIndexedTree {
private int n;
private int[] c;

public BinaryIndexedTree(int n) {
this.n = n;
c = new int[n + 1];
}

public void update(int x, int delta) {
while (x <= n) {
c[x] += delta;
x += lowbit(x);
}
}

public int query(int x) {
int s = 0;
while (x > 0) {
s += c[x];
x -= lowbit(x);
}
return s;
}

public static int lowbit(int x) {
return x & -x;
}
}

class MRUQueue {
private int n;
private int[] data;
private BinaryIndexedTree tree;

public MRUQueue(int n) {
this.n = n;
data = new int[n + 2010];
for (int i = 1; i <= n; ++i) {
data[i] = i;
}
tree = new BinaryIndexedTree(n + 2010);
}

public int fetch(int k) {
int left = 1;
int right = n++;
while (left < right) {
int mid = (left + right) >> 1;
if (mid - tree.query(mid) >= k) {
right = mid;
} else {
left = mid + 1;
}
}
data[n] = data[left];
tree.update(left, 1);
return data[left];
}
}

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

• class BinaryIndexedTree:
def __init__(self, n):
self.n = n
self.c = [0] * (n + 1)

@staticmethod
def lowbit(x):
return x & -x

def update(self, x, delta):
while x <= self.n:
self.c[x] += delta
x += BinaryIndexedTree.lowbit(x)

def query(self, x):
s = 0
while x > 0:
s += self.c[x]
x -= BinaryIndexedTree.lowbit(x)
return s

class MRUQueue:
def __init__(self, n: int):
self.data = list(range(n + 1))
self.tree = BinaryIndexedTree(n + 2010)

def fetch(self, k: int) -> int:
left, right = 1, len(self.data)
while left < right:
mid = (left + right) >> 1
if mid - self.tree.query(mid) >= k:
right = mid
else:
left = mid + 1
self.data.append(self.data[left])
self.tree.update(left, 1)
return self.data[left]

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


• class BinaryIndexedTree {
public:
int n;
vector<int> c;

BinaryIndexedTree(int _n)
: n(_n)
, c(_n + 1) {}

void update(int x, int delta) {
while (x <= n) {
c[x] += delta;
x += lowbit(x);
}
}

int query(int x) {
int s = 0;
while (x > 0) {
s += c[x];
x -= lowbit(x);
}
return s;
}

int lowbit(int x) {
return x & -x;
}
};

class MRUQueue {
public:
int n;
vector<int> data;
BinaryIndexedTree* tree;

MRUQueue(int n) {
this->n = n;
data.resize(n + 1);
for (int i = 1; i <= n; ++i) data[i] = i;
tree = new BinaryIndexedTree(n + 2010);
}

int fetch(int k) {
int left = 1, right = data.size();
while (left < right) {
int mid = (left + right) >> 1;
if (mid - tree->query(mid) >= k)
right = mid;
else
left = mid + 1;
}
data.push_back(data[left]);
tree->update(left, 1);
return data[left];
}
};

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

• type BinaryIndexedTree struct {
n int
c []int
}

func newBinaryIndexedTree(n int) *BinaryIndexedTree {
c := make([]int, n+1)
return &BinaryIndexedTree{n, c}
}

func (this *BinaryIndexedTree) lowbit(x int) int {
return x & -x
}

func (this *BinaryIndexedTree) update(x, delta int) {
for x <= this.n {
this.c[x] += delta
x += this.lowbit(x)
}
}

func (this *BinaryIndexedTree) query(x int) int {
s := 0
for x > 0 {
s += this.c[x]
x -= this.lowbit(x)
}
return s
}

type MRUQueue struct {
data []int
tree *BinaryIndexedTree
}

func Constructor(n int) MRUQueue {
data := make([]int, n+1)
for i := range data {
data[i] = i
}
return MRUQueue{data, newBinaryIndexedTree(n + 2010)}
}

func (this *MRUQueue) Fetch(k int) int {
left, right := 1, len(this.data)
for left < right {
mid := (left + right) >> 1
if mid-this.tree.query(mid) >= k {
right = mid
} else {
left = mid + 1
}
}
this.data = append(this.data, this.data[left])
this.tree.update(left, 1)
return this.data[left]
}

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

• class BinaryIndexedTree {
private n: number;
private c: number[];

constructor(n: number) {
this.n = n;
this.c = new Array(n + 1).fill(0);
}

public update(x: number, v: number): void {
while (x <= this.n) {
this.c[x] += v;
x += x & -x;
}
}

public query(x: number): number {
let s = 0;
while (x > 0) {
s += this.c[x];
x -= x & -x;
}
return s;
}
}

class MRUQueue {
private q: number[];
private tree: BinaryIndexedTree;

constructor(n: number) {
this.q = new Array(n + 1);
for (let i = 1; i <= n; ++i) {
this.q[i] = i;
}
this.tree = new BinaryIndexedTree(n + 2010);
}

fetch(k: number): number {
let l = 1;
let r = this.q.length;
while (l < r) {
const mid = (l + r) >> 1;
if (mid - this.tree.query(mid) >= k) {
r = mid;
} else {
l = mid + 1;
}
}
const x = this.q[l];
this.q.push(x);
this.tree.update(l, 1);
return x;
}
}

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