Sliding Window Algorithm!

general
,
1

Can anyone help with this algorithm implementation ?
The problem asked is : given an array of size (n) and a number K find the minimum summation of K elements.

2

Do you want to find the sum of the k smallest elements of the array?
Sorting the array and taking the summation of the first k elements give the required answer easily.

If you want a better algorithm i would suggest a modified version of a quickselect algorithm where you keep partitioning the array until you get the k’th element as the pivot. Once you get this just find the summation of all elements including this and to the left of this. You can make this algorithm to run in O(N) on average case by choosing random pivots.

3

You cant reorder the elements in the array. What i want is:
ex: n=6 k=3
ar : 2 5 1 8 3 4
ans = 8 => take first three elements. if we had a loop over n and every time we sum k elements well get O(n*k) but with sliding windows we’ll get O(n) … if im correct

4
5

It will be O(n) without array modification only if all elements are continuous as far as i know. Sliding window will not work if array elements are not consecutive. Could you be a bit more clear about the problem statement?

6

As far as i can see, all your array elements need to be continuous. The principle is when your window slides ahead , subtract the element that was removed from the array(window) and add the new element to the old sum. So here is the simple algo.

1)find sum of 1st k elements, call it as sum. store this value as min.

  1. Here is rough idea:

      for i=2 to n-k: //(assume array starts from 1)
        sum = sum + arr[i+n] - arr[i] 
        if(sum < min):
              min=sum //update value of min
  return min
1 Like
7

Yes thats it thxx

8

Simply use a deque like the one demonstrated in http://www.geeksforgeeks.org/maximum-of-all-subarrays-of-size-k/