patternMinor
Algorithmic problem on sliding windows
Viewed 0 times
algorithmicslidingproblemwindows
Problem
Given a zero-indexed, unsorted array, $a$ of integers (can be positive, negative, or zero) of size $n$. A window of size $k~(k
-
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.
-
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#146415, answer score: 3
Revisions (0)
No revisions yet.