# k-th smallest element in sliding segment

Consider an array $$a[1\ldots n]$$ and another array $$l = a[0]$$ (initial value). At each turn we may add next element to array $$l$$, or remove first element from array $$l$$. F.e. after first iteration it could be empty or could become $$a[0, 1]$$. We want to find k-th smallest element at each iteration in array $$l$$.

First of all if size of $$l$$ is less than $$k$$ the answer is 'No'. Let's consider more interesting case.

I've decided to have two heaps (one min and one max heap).

Max heap contains all k-th smallest elements from $$a[l..r]$$ and min heap contains elements which are greater than the k-th smallest element. Then answer is head of max-heap (we can take it in O(1)).

But there is a small problem. What if need to consider $$a[l+1 .. r]$$ (so we need to push left bound). Now of course if $$r - l < k$$ the answer is 'No', but what should we do otherwise? I thought we should do following: if $$a[l] > maxheap[0]$$ then the answer doesn't change (because we will delete element greater than k-th smallest element), but what should we do with our heaps? Unfortunately I can't delete in heap by position (it takes a long time). The best we can do is delete root node in O(log n). How should I affect them?

Maintain an AVL tree $$B$$ that stores the elements in $$l$$. In addition, for each element $$a$$ in $$l$$, keep a pointer $$p_a$$ to the corresponding node in $$B$$.

• When an element $$x$$ is added to $$l$$, then simply insert a new node $$v$$ representing $$x$$ into $$B$$ and make $$p_x$$ point to $$v$$.

• When the first element $$y$$ of $$l$$ needs to be removed, delete (the node pointed by) $$p_y$$ from $$B$$.

• To report the $$k$$-minimum element in $$l$$, simply look for the minimum element in $$B$$ (i.e., the one stored in the leftmost node). This can be done in $$O(\log n)$$ time by just keeping, in each node $$v$$, the size of the subtree of $$B$$ rooted in $$v$$.

By combining the above operations, each turn of your problem will require $$O(\log(1 + |l|)) = O(\log n)$$ time.

• I don't need minimum. I need k-th minimum. Oct 21, 2020 at 11:59
• And BST would give me O(k log n) per each operation. It's too long. Even quick-select would give O(n) in worst case Oct 21, 2020 at 12:01
• @openspace As I said, if you choose to implement your BST using AVL trees then you get a time of $O(\log n)$ per operation. Oct 21, 2020 at 12:31
• @openspace, sorry about that. I fixed the answer. It doesn't really matter what element you're looking for. In an AVL tree of $n$ elements the element with a given rank can be found in $O(\log n)$ time. Oct 21, 2020 at 12:33
• how we determine the rank? K-th element could be in any place of tree. At least I'd need to make O(k log n) traverse operations. Oct 21, 2020 at 12:35