Sliding Window
This concept is used when there is a requirement to use consecutive elements.
For example in the above image, the window size is 3. And with each iteration, we are moving the window by one step forward. We could perform any operation on this window, e.g., summation or multiplication of window elements.
E.g., the below implementation window stores the sum of elements.
int a[n]; // array
int k;// window size
int window; // stores sum of the elements in the window
// Assume window is initialised with sum = (a[0] + a[i] + .. +a[k-1])
// implementation of Sliding Window
for(int i=k;i<n;i++)
{
window -= a[i-k]; // removing leftmost element of window
window += a[i]; // adding new element to window
cout<<"Window sum = "<<window<<endl;
}
Bonus:
1. Window size can be dynamic based on question requirements.
2. Helps in time complexity. Without sliding window above question time
complexity would be O(n*k)
Leave a Reply