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:
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.
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.