3
$\begingroup$

Given a zero-indexed, unsorted array, $a$ of integers (can be positive, negative, or zero) of size $n$. A window of size $k~(k < n)$ is defined as a subarray $a[i...i+k]$ for every $0 \leq i \leq n - k - 1$. The problem is to find the minimum difference between two elements present in the same window, for every window.

I was able to come up with the following algorithms:

  1. Maintain an array of size $k$ for every window (can be reused for every window). Sort each of these and find the minimum difference between consecutive elements. This will take $\mathcal{O}(k)$ space (not accounting the space required for the output) and $\mathcal{O}(n*k \log k)$ time.

  2. A slightly clever optimization is to add the incoming element into the already sorted window (alike insertion sort) and remove the leaving element. This reduces the time to $\mathcal{O}(n*k)$ while the space is same as above.

However, I am looking for an algorithm which runs in $\mathcal{O}(n*\log k)$ time and possibly $\mathcal{O}(k)$ space.

Note: This is not a homework question but was asked to me in a software engineering interview.

$\endgroup$
0
3
$\begingroup$

If you use a balanced binary search tree (instead of just a sorted list), you can remove and add new items in $O(\log(k))$.

In addition, you want to keep a min-heap of the differences of consecutive elements in the tree.

When adding a new item to the window, say it was $b$, and its value is between two elements $a$ and $c$ (i.e, $a<b<c$) - you will want to remove the difference $c-a$ from the heap, and add the two new differences $c-b$ and $b-a$.

When removing an item from the window, $b$, and its immediate neighbors in the tree are $a$ and $c$ (such that $a<b<c$), then you will want to do the opposite of the insersion: remove $c-b$ and $b-a$ from the heap, and add $c-a$ instead.

All of those insersion \ deletion operations work in $O(\log(k))$, and querying the minimal difference from the heap takes $O(1)$ time.

$\endgroup$
3
  • $\begingroup$ So, let's say we are at an intermediate window and have the current minimum with us. Now a new element enters, this insertion can be done in $\mathcal{O}(\log k)$ time. Then, we find the in-order successor and predecessor, which can also be done in $\mathcal{O}(\log k)$ time, right? So, we are good till now. But how to handle the deletion? As in, what if it was involved in the previous window's minimum? $\endgroup$
    – avocado
    Dec 5 '21 at 17:29
  • $\begingroup$ @avocado You are right. My bad. $\endgroup$
    – nir shahar
    Dec 5 '21 at 17:38
  • 1
    $\begingroup$ @avocado I fixed the answer to also handle the deletions as well. Notice that now also insertions have become a bit more complicated $\endgroup$
    – nir shahar
    Dec 5 '21 at 17:44

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.