Thursday, 26 December 2013

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;
}

Amortized complexity is O(n).

Problems to Solve:
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

4 comments:

  1. Thank you so much for sharing informative blog. Hope you continue to share more of your ideas. I will definitely love to read. Keep up the good work! Lorendo Portes et Fenêtres

    ReplyDelete
  2. I will visit your blog regularly for some latest post. Thanks for sharing,

    Motorized Sliding Gate

    ReplyDelete

  3. Amazing Write up!. It’s a very helpful and nice information about windows & doors. This post helped me choose the perfect family room decorating. I would like to suggest to you the best Minimal Sliding Windows & Door System. Thanks for sharing this information. Keep Posting!

    ReplyDelete