1
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
11
  • $\begingroup$ I don't need minimum. I need k-th minimum. $\endgroup$
    – openspace
    Oct 21, 2020 at 11:59
  • $\begingroup$ 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 $\endgroup$
    – openspace
    Oct 21, 2020 at 12:01
  • $\begingroup$ @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. $\endgroup$
    – Steven
    Oct 21, 2020 at 12:31
  • $\begingroup$ @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. $\endgroup$
    – Steven
    Oct 21, 2020 at 12:33
  • $\begingroup$ 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. $\endgroup$
    – openspace
    Oct 21, 2020 at 12:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.