Algorithmic problem on sliding windows

Question

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.

Answer 1

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.

• avocado: 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?
• nir shahar: @avocado You are right. My bad.
• nir shahar: @avocado I fixed the answer to also handle the deletions as well. Notice that now also insertions have become a bit more complicated