How to find maximum of each subarray of some fixed given length in a given array

Question

We are given an array of n elements and an integer k. Suppose that we want to slide a window of length k across the array, reporting the largest value contained in each window. For example, given the array

15  10   9  16  20  14  13

Given a window of length 4, we would output

[15  10   9  16] 20  14  13   ---> Output 16
 15 [10   9  16  20] 14  13   ---> Output 20
 15  10 [ 9  16  20  14]  13  ---> Output 20
 15  10   9 [16  20  14  13]  ---> Output 20

So the result would be

16  20  20  20

I was approaching the problem by keeping track of the maximum element of the window at each point, but ran into a problem when the largest element gets slid out of the window. At that point, I couldn't think of a fast way to figure out what the largest remaining element is.

Does anyone know of an efficient algorithm for solving this problem?

Answer 1

This older question discusses how to build a queue data structure supporting insert, dequeue, and find-min all in O(1) time. Note that this is not a standard priority queue, but instead is a queue in which at any point you can find the value of the smallest element it contains in O(1) time. You could easily modify this structure to support find-max in O(1) instead of find-min, since that's more relevant to this particular problem.

Using this structure, you can solve this problem in O(n) time as follows:

1. Enqueue the first k elements of the array into the special queue.
2. For each element in the rest of the array:
   1. Use the queue's find-max operation to report the largest element of the current subrange.
   2. Dequeue an element from the queue, leaving the last k-1 elements of the old range in place.
   3. Enqueue the next element from the sequence, causing the queue to now hold the next k-element subrange of the sequence.

This takes a total of O(n) time, since you visit each array element once, enqueuing and dequeuing each at most once, and calling find-max exactly n-k times. I think this is pretty cool, since the complexity is independent of k, which doesn't initially seem like it necessarily should be possible.

Hope this helps! And thanks for asking a cool question!

Answer 2

You can achieve O(n) complexity by using Double-ended queue.

Here is C# implementation

    public static void printKMax(int[] arr, int n, int k)
    {
        Deque<int> qi = new Deque<int>();
        int i;
        for (i=0;i< k; i++) // first window of the array
        {
            while ((qi.Count > 0) && (arr[i] >= arr[qi.PeekBack()]))
            {
                qi.PopBack();
            }
            qi.PushBack(i);
        }

        for(i=k ;i< n; ++i)
        {
            Console.WriteLine(arr[qi.PeekFront()]); // the front item is the largest element in previous window.
            while (qi.Count > 0 && qi.PeekFront() <= i - k) // this is where the comparison is happening!
            {
                qi.PopFront(); //now it's out of its window k 
            }
            while(qi.Count>0 && arr[i]>=arr[qi.PeekBack()]) // repeat
            {
                qi.PopBack();
            }
            qi.PushBack(i);
        }

        Console.WriteLine(arr[qi.PeekFront()]);
    }

Answer 3

You can keep a Binary Search Tree of the current elements, for example, save them as value-occurrence pairs. Other than that, you sliding window algorithm should be good enough.

This way, select maximum (the max element in the subsection) will cost O(logL) time, L being the length of the current subsection; add new would also be O(logL). TO delete the oldest one, just search the value and decrements the count by 1, if the count goes to 0 delete it.

So the total time will be O(NlogL), N being the length of the array.

Answer 4

You could proceed like a tabu search :

Loop through the list and get the max of the 4 first ith element. Then on the next step just check if the i+1th element is superior to the max of the previous elements

• if i+1>=previous max then new max = i+1 reinialise tabu
• if i+1< previous max then if the previous max was found less than N step ago keep the previous (here is the tabu )
• if i+1< preivous max and the previous max is tabu then take the new max of the 4 i+1th elements.

I'm not sure it's clear but tell me if you have any question. below is a code in python to test it.

l=[15,10,9,16,20,14,13,11,12]
N=4
res=[-1] #initialise res
tabu=1  #initialise tabu
for k in range(0,len(l)):
#if the previous element res[-1] is higher than l[k] and not tabu then keep it
#if the previous is tabu and higher than l[k] make a new search without it
#if the previous is smaller than l[k] take the new max =l[k]

    if l[k]<res[-1] and tabu<N:
        tabu+=1
        res.append(res[-1])
    elif l[k] < res[-1] and tabu == N:
         newMax=max(l[k-N+1:k+1])
         res.append(newMax)
         tabu=N-l[k-N+1:k+1].index(newMax) #the tabu is initialized depending on the position of the newmaximum
    elif l[k] >= res[-1]:
        tabu=1
        res.append(l[k])

print res[N:] #take of the N first element

Complexity:

I updated the code thx to flolo and the complexity. it's not anymore O(N) but O(M*N)

The worst case is when you need to recalculate a maximum at each step of the loop. i e a strictly decreasing list for example.

at each step of the loop you need to recalculate the max of M elements

then the overall complexity is O(M*N)

Answer 5

The best I can come up with quickly is O(n log m). You can get that by dynamic programming.

In the first pass you find max for every element the maximum from the element itself and the next.

Now you have n maximums (window size = 2).

Now you can find on this array the maximum from every element and the overnext in this array (gives you for each element the maximum for the next 4, ie window size = 4).

Then you can do it again, and again (and every time the window size doubles).

As one clearly sees the window size grows exponentially.

Therefor the runtime is O(n log m). The implementation is a bit tricky, because you must consider the corner and special cases (esp. when the windows size should not be a power of two), but they didnt influence the asymptotic runtime.

Answer 6

Please review my code. According to me I think the Time Complexity for this algorithm is

O(l) + O(n)

    for (int i = 0; i< l;i++){
        oldHighest += arraylist[i];
    }
    int kr = FindMaxSumSubArray(arraylist, startIndex, lastIndex);



    public static int FindMaxSumSubArray(int[] arraylist, int startIndex, int lastIndex){

    int k = (startIndex + lastIndex)/2;
    k = k - startIndex;
    lastIndex = lastIndex  - startIndex;

    if(arraylist.length == 1){
        if(lcount<l){
            highestSum += arraylist[0];
            lcount++;
        }
        else if (lcount == l){
            if(highestSum >= oldHighest){
                oldHighest = highestSum;
                result = count - l + 1;
            }
            highestSum = 0;
            highestSum += arraylist[0];
            lcount = 1;
        }
        count++;
        return result;
    }

    FindMaxSumSubArray(Arrays.copyOfRange(arraylist, 0, k+1), 0, k);
    FindMaxSumSubArray(Arrays.copyOfRange(arraylist, k+1, lastIndex+1), k+1, lastIndex);

    return result;
 }

I don't understand if this is better off to do in recursion or just linearly?