Minimum value for all continuous ranges of fixed size in linear complexity

Initial problem

Statement:

Let AA be an array A0,A1,…,An−1A0,A1,…,An−1 of the size nn. Find the maximum sum of continuous subarray(window) of the size kk with possibility to ignore one of the elements.

Naive O(n⋅k)O(n⋅k) solution:

Let's denote sums[i]=Ai−k+1+Ai−k+2+…+Aisums[i]=Ai−k+1+Ai−k+2+…+Ai

minimum[i]=min(Ai−k+1,Ai−k+2,…,Ai,0)minimum[i]=min(Ai−k+1,Ai−k+2,…,Ai,0) (if minimum is positive, we will use 0 instead)

For i<k−1,minimum[i]=sums[i]=0i<k−1,minimum[i]=sums[i]=0

Key idea: The answer is maximum of sums[i]−minimum[i]sums[i]−minimum[i], for every k−1≤i<Nk−1≤i<N

So, let's go straight forward, and for every ii, calculate sums[i]sums[i], find minimum[i]minimum[i], and then pick the maximum for sums[i]sums[i] — minimum[i]minimum[i].

There is a way to calculate sumssums in O(n)O(n) using formula: sums[i]=Ai+sums[i−1]−Ai−ksums[i]=Ai+sums[i−1]−Ai−k.

But there is no obvious algorithm to calculate minimum[i]minimum[i], so for every ii we will need to iterate every value in the k-window and pick the minimum.

Complexity: O(n⋅k)O(n⋅k)

Linearithmic solution:

Though, it's a not-straight forward strategy to find minimum in the range, there is well-known problem called RMQ, range minimum queries, especially static range minimum queries, which helps us find the solution in O(n⋅log(n))O(n⋅log(n)) (using sparse table to find minimum in needed range)

Sparse table is really fast, and with a good implementation it might succeed, when linear complexity is needed, though it's not what we are looking for.

CPalgorithms RMQ section

Top coder RMQ and LCA

Another O(n⋅log(n))O(n⋅log(n)) approach:

To find minimum in our k-window, we can use priority queues(pqpq) of minimum.

Let's build sumssums with technique we used in our O(n⋅k)O(n⋅k) solution, and instead of going through k-window to find minimum for every ii, we will start with i=0i=0 and iterate until the end.

For every ii we will add a pair (value=Ai,index=i)(value=Ai,index=i) And then we remove the top of priority queue, if second element is out of the k-window (pq.top().index≤i−k)(pq.top().index≤i−k), until we find the element that is inside. so for ii answer is sums[i]−pq.top().valuesums[i]−pq.top().value

Linear time? Not yet.

Let's take a look on even better (if k≪nif k≪n) linearithmic solution in O(n⋅log(k))O(n⋅log(k))

Instead of priority queue, we can use set(setset) (in our case multiset)! Although hidden constants of sets are way bigger than priority queue ( because of tree balancing ), set let you keep constant size of k, which let us insert, erase and get minimum if O(log(k))O(log(k))

To make this work we still using our sumssums technique, but now you can use the same idea to find minimum,

Insert A0,A1,…Ak−1A0,A1,…Ak−1 to the set.

To find minimum of the set in c++, use *s.begin()

For i=k−1i=k−1 answer is sums[k−1]−min(set)sums[k−1]−min(set)

Iterate through i≥ki≥k, and for every ii,

set.insert(A[i])

set.erase(A[i-k]) *

*to make sure you erase only one element use set.erase(set.find(A[i-k])) instead.

And the answer again will be sums[i]−min(set)sums[i]−min(set)

We are inserting and erasing from the set of constant size kk, nn times, so overall complexity: O(n⋅log(k))O(n⋅log(k))

This solution also might be generalized for qq elements to remove, just take qq smallest negative values int the set of every ii. For generalized problem overall complexity is: O(n⋅q⋅log(k))O(n⋅q⋅log(k)), but feel free to come up with better solutions for this problem in the comments.

Finally transition to O(n)O(n)

The key observation that you might already found, that for every ii, if there is exist jj such, Ai>AjAi>Aj and i<ji<j, then for every j≤w≤j+k−1j≤w≤j+k−1, minimum[w]≠Ajminimum[w]≠Aj

So now, when we have all the things we need, let's take a look on double-ended queue(deque). This data-structure allows to insert(push) and remove(pop) from 2 sides(back and front) in O(1)O(1) Although it doesn't keep the elements in order.

How can we help it? Let's use our observation!

Let's say we want to keep minimum for current window in front of the deque. As priority queue in third solution, we will keep in the queue pair of (value=Ai,index=i)(value=Ai,index=i)

We iterate through every ii from 0 to n-1,

Let's remove all elements from the front, that outside of current window.

while(deque.front().index≤i−kdeque.front().index≤i−k) — remove deque.front()deque.front()

And now to insert new AiAi, let's go to back of our deque.

We know that for every element in the deque, index<iindex<i, because we iterate on ii. Now because of the observation we made, we can remove all the elements from the back, that are bigger than AiAi

And what we'll get in the front is actual minimum for current window.

When i≥k−1i≥k−1 we can start to finding the maximum of sums[i]−deque.front().valuesums[i]−deque.front().value

Every element is once added (only when iterated through), and at most once removed. Because we used deque, we can't iterate trough an entire deque (only when removing), so overall complexity: O(n)O(n)

Conclusion:

By the end we found an algorithm that finds minimum for every k-size subarray in linear time, I don't know if it's actually useful in other problems, but I enjoyed writing this blog. Feel free to correct me if you found any mistakes or you have another ideas in the comments.

My c++ implementation on PasteBin.com