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)

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

1756 - Design Most Recently Used Queue

1756. Design Most Recently Used Queue

Level

Description

Solution

Follow up

All Problems

All Solutions

Welcome to Subscribe On Youtube

1756. Design Most Recently Used Queue

Level

Description

Solution

Follow up

All Problems

All Solutions