Wednesday, September 03, 2008

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

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;
sum=tsum=start=tstart=0;
k=3;
for(int i=0; i < k ; i++)
sum+=data[i];
tsum=sum;
for(int i=k; i < datalentgh ; i++)
{
tsum= tsum - data[i-k];
tsum= tsum + data[i];
tstart=i-k;
if(tsum>sum)
{
sum=tsum;
start=tstart;
}



}

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;

system("pause");
}
 

No comments: