# Algorithmic problem on sliding windows

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.

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) - 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), 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.

• 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? Dec 5 '21 at 17:29
• @avocado You are right. My bad. Dec 5 '21 at 17:38
• @avocado I fixed the answer to also handle the deletions as well. Notice that now also insertions have become a bit more complicated Dec 5 '21 at 17:44