Minimum sliding Window Problem can be solved in O(n) rather easily

minimum sliding window algorithem

Several solutions to the minumum sliding window Problem actually create complexity but in my opinion it can solved with rather ease while still maintaining the time and Memory complexity at O(n).

The idea is to basically create a temporary sum and Keep adding the new elements and subtracting the old elements as we scan the Array while keeping record of the last biggest sum window by storing its index.

So we need to scan the Array only once and without any additional array.

# include <iostream>
using namespace::std;

const int datalentgh=16;
int data[datalentgh]= {2, 3, 10, 12, 6, 2, 5, 1,9,8,1,5,3,8,9,9};

void main()
for(int i=0;i<datalentgh;i++)
cout<<data[i]<<" ";
// we create the variables for temporary sum, temporary starting index and for final starting index of the window and its sum. 
int sum, tsum,start,tstart, k;
for(int i=0; i < k ; i++)
for(int i=k; i < datalentgh ; i++)
tsum= tsum - data[i-k];
tsum= tsum + data[i];


cout<<endl<<endl<<" Starting Index of Minimum Window is "<<start+1<<" and the number at that index is "<<data[start+1] <<" and sum is "<<sum<<endl;


Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.