Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Finding maximum for every window of size k in an array

Tags:

algorithm

Given an array of size n and k, how do you find the maximum for every contiguous subarray of size k?

For example

arr = 1 5 2 6 3 1 24 7 k = 3 ans = 5 6 6 6 24 24 

I was thinking of having an array of size k and each step evict the last element out and add the new element and find maximum among that. It leads to a running time of O(nk). Is there a better way to do this?

like image 286
shreyasva Avatar asked Nov 07 '11 01:11

shreyasva


People also ask

How many windows should exist in an array with N elements and window size k?

There can be a total of N – K + 1 sliding window and there are K elements in each window.

How do you find the maximum element in a subarray?

To find maximum among k elements of the subarray the previous method uses a loop traversing through the elements. To reduce that time the idea is to use an AVL tree which returns the maximum element in log n time. So, traverse through the array and keep k elements in the BST and print the maximum in every iteration.

How do you calculate Subarray size k?

Given an array arr[], an integer K and a Sum. The task is to check if there exists any subarray with K elements whose sum is equal to the given sum. If any of the subarray with size K has the sum equal to the given sum then print YES otherwise print NO.

What is kadane algorithm?

Kadane's algorithm is an iterative dynamic programming algorithm in which we search for a maximum sum contiguous subarray within a one-dimensional numeric array.


2 Answers

You have heard about doing it in O(n) using dequeue.

Well that is a well known algorithm for this question to do in O(n).

The method i am telling is quite simple and has time complexity O(n).

Your Sample Input: n=10 , W = 3  10 3 1 -2 5 6 0 9 8 -1 2 0  Answer = 5 6 6 9 9 9 8 2 

Concept: Dynamic Programming

Algorithm:

  1. N is number of elements in an array and W is window size. So, Window number = N-W+1
  2. Now divide array into blocks of W starting from index 1.

    Here divide into blocks of size 'W'=3. For your sample input:

    divided blocks

  3. We have divided into blocks because we will calculate maximum in 2 ways A.) by traversing from left to right B.) by traversing from right to left. but how ??

  4. Firstly, Traversing from Left to Right. For each element ai in block we will find maximum till that element ai starting from START of Block to END of that block. So here,

    LR

  5. Secondly, Traversing from Right to Left. For each element 'ai' in block we will find maximum till that element 'ai' starting from END of Block to START of that block. So Here,

    RL

  6. Now we have to find maximum for each subarray or window of size 'W'. So, starting from index = 1 to index = N-W+1 .

    max_val[index] = max(RL[index], LR[index+w-1]);

    LR + RL

     for index=1: max_val[1] = max(RL[1],LR[3]) = max(5,5)= 5 

Simliarly, for all index i, (i<=(n-k+1)), value at RL[i] and LR[i+w-1] are compared and maximum among those two is answer for that subarray.

So Final Answer : 5 6 6 9 9 9 8 2

Time Complexity: O(n)

Implementation code:

// Shashank Jain #include <iostream> #include <cstdio> #include <cstring> #include <algorithm>  #define LIM 100001   using namespace std;  int arr[LIM]; // Input Array int LR[LIM]; // maximum from Left to Right int RL[LIM]; // maximum from Right to left int max_val[LIM]; // number of subarrays(windows) will be n-k+1  int main(){     int n, w, i, k; // 'n' is number of elements in array                     // 'w' is Window's Size      cin >> n >> w;      k = n - w + 1; // 'K' is number of Windows      for(i = 1; i <= n; i++)         cin >> arr[i];      for(i = 1; i <= n; i++){ // for maximum Left to Right         if(i % w == 1) // that means START of a block             LR[i] = arr[i];         else             LR[i] = max(LR[i - 1], arr[i]);             }      for(i = n; i >= 1; i--){ // for maximum Right to Left         if(i == n) // Maybe the last block is not of size 'W'.              RL[i] = arr[i];          else if(i % w == 0) // that means END of a block             RL[i] = arr[i];         else             RL[i] = max(RL[i+1], arr[i]);     }      for(i = 1; i <= k; i++)    // maximum         max_val[i] = max(RL[i], LR[i + w - 1]);      for(i = 1; i <= k ; i++)         cout << max_val[i] << " ";      cout << endl;      return 0; }   

Running Code Link


I'll try to proof: (by @johnchen902)

If k % w != 1 (k is not the begin of a block)

Let k* = The begin of block containing k ans[k] = max( arr[k], arr[k + 1], arr[k + 2], ..., arr[k + w - 1])        = max( max( arr[k],  arr[k + 1],  arr[k + 2],  ..., arr[k*]),                max( arr[k*], arr[k* + 1], arr[k* + 2], ..., arr[k + w - 1]) )        = max( RL[k], LR[k+w-1] ) 

Otherwise (k is the begin of a block)

ans[k] = max( arr[k], arr[k + 1], arr[k + 2], ..., arr[k + w - 1])        = RL[k] = LR[k+w-1]        = max( RL[k], LR[k+w-1] ) 
like image 176
S J Avatar answered Oct 22 '22 15:10

S J


Dynamic programming approach is very neatly explained by Shashank Jain. I would like to explain how to do the same using dequeue. The key is to maintain the max element at the top of the queue(for a window ) and discarding the useless elements and we also need to discard the elements that are out of index of current window.
useless elements = If Current element is greater than the last element of queue than the last element of queue is useless .
Note : We are storing the index in queue not the element itself. It will be more clear from the code itself.
1. If Current element is greater than the last element of queue than the last element of queue is useless . We need to delete that last element. (and keep deleting until the last element of queue is smaller than current element).
2. If if current_index - k >= q.front() that means we are going out of window so we need to delete the element from front of queue.

vector<int> max_sub_deque(vector<int> &A,int k) {     deque<int> q;     for(int i=0;i<k;i++)     {         while(!q.empty() && A[i] >= A[q.back()])             q.pop_back();         q.push_back(i);     }     vector<int> res;     for(int i=k;i<A.size();i++)     {         res.push_back(A[q.front()]);         while(!q.empty() && A[i] >= A[q.back()] )             q.pop_back();         while(!q.empty() && q.front() <= i-k)             q.pop_front();         q.push_back(i);      }     res.push_back(A[q.front()]);     return res; } 


Since each element is enqueued and dequeued atmost 1 time to time complexity is
O(n+n) = O(2n) = O(n).
And the size of queue can not exceed the limit k . so space complexity = O(k).

like image 40
Ankit Maurya Avatar answered Oct 22 '22 15:10

Ankit Maurya