Sliding Window Algorithms and problems related to that..

See the code

	#include <bits/stdc++.h>
	using namespace std;
	const int N = 500005;
	int a[N];
	int main() {
	int n, k;
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
	cin >> a[i];
	}
	deque <pair <int, int> > window;
	for (int i = 0; i < n; i++) {
	// from the back of deque, if the value of last element is greater or equal than a[i]
	// then keep poping the elements.
	// Invariant : deque always remains sorted.
	// Important property due to which this trick works, is that the popped numbers are useless
	// in the next iteration as they are not longer can affect minimum.
	while (!window.empty() && window.back().first >= a[i]) {
	window.pop_back();
	}
	window.push_back (make_pair (a[i], i));
	// Now from the front of deque, pop all the elements which were out of our window.
	while (!window.empty() && window.front().second <= i - k) {
	window.pop_front();
	}
	if (i >= k - 1)
	cout << window.front().first << " ";
	}
	return 0;
	}

view raw slidingWindow.cpp hosted with ❤ by GitHub

Amortized complexity is O(n).

Problems to Solve:

• http://www.spoj.com/problems/ARRAYSUB/
• Task "sound" at http://www.boi2007.de/en/tasks
• Task "pyramid" at http://olympiads.win.tue.nl/ioi/ioi2006/contest/day1/ (medium to hard problem)
• http://wcipeg.com/problem/ccc03s2p5
• http://wcipeg.com/problem/ccc96s5
• http://wcipeg.com/problem/smac081p3
• http://wcipeg.com/problem/ccc96s5
• http://wcipeg.com/problem/ioi0611
• http://www.spoj.com/problems/BROKEN/
• http://www.spoj.com/problems/FSEATS/
• http://www.spoj.com/problems/KPMATRIX/
• http://www.spoj.com/problems/MATRIX2/
• http://www.codechef.com/problems/CHEFTOWN
• http://wcipeg.com/problem/ioi0612
• http://www.codechef.com/OCT12/problems/TEAMSIZE
• http://www.spoj.com/problems/KRECT/

References:

1. http://people.cs.uct.ac.za/~ksmith/articles/sliding_window_minimum.html
2. http://softwarelearner.blogspot.in/2011/04/minima-in-sliding-window.html
3. http://stackoverflow.com/questions/8269916/what-is-sliding-window-algorithm-examples/8269948#8269948
4. http://richardhartersworld.com/cri/2001/slidingmin.html
5. http://wcipeg.com/wiki/Sliding_window
6. http://www.geeksforgeeks.org/maximum-of-all-subarrays-of-size-k/
7. http://wcipeg.com/wiki/Sliding_range_minimum_query