Sliding window - Revision history

180.211.185.233: /* Problems */

2016-06-13T07:44:34Z

‎Problems

14.139.82.6: /* Problems */

2016-06-05T13:21:33Z

‎Problems

90.153.128.17 at 15:35, 22 August 2012

2012-08-22T15:35:17Z

Brian at 03:58, 20 December 2011

2011-12-20T03:58:38Z

Brian at 03:57, 20 December 2011

2011-12-20T03:57:21Z

Brian: Created page with "A '''sliding window''' is an interval both of whose endpoints are allowed to move only forward, and never backward (or ''vice versa''). It is analogous to an actual window that o..."

2011-12-20T03:55:23Z

Created page with "A '''sliding window''' is an interval both of whose endpoints are allowed to move only forward, and never backward (or ''vice versa''). It is analogous to an actual window that o..."

New page

A '''sliding window''' is an interval both of whose endpoints are allowed to move only forward, and never backward (or ''vice versa''). It is analogous to an actual window that opens from left to right; when opening the window its left edge only moves to the right, and so does its right edge, and when closing it, the opposite is true.

However, in computer science, sliding windows are allowed to change in size as they are moving; the right edge may move without the left edge's movement, or ''vice versa''. Notice that when the right edge moves, the window becomes larger, and when the left edge moves, the window becomes smaller.

The sliding window is used in certain situations in which we need to keep track of some function whose domain is the set of intervals, with the property that the function's value can be efficiently recomputed after one of the edges moves a small amount.

A simple example is as follows: given a list of non-negative integers, we wish to find the longest interval (contiguous subsequence of the list) with the property that the sum of all the elements it contains does not exceed a bound <math>K</math>.

To solve this problem, we first observe that if we know the sum of all the elements in an interval, and we advance the left edge of the interval, then we simply exclude one element from the old interval from the new interval, and the sum decreases by the value of that element; and if we advance the right edge, then we simply include one new element, and the sum increases by the value of that element.

We then observe that for every possible position of the left edge of an interval, there is a corresponding position of the right edge such that the resulting interval is the longest interval possible with its left edge at the given position such that its sum does not exceed <math>K</math>. For example, if the array is given by <math>[9, 2, 6, 3, 1, 5, 0, 7]</math>, and our bound is <math>K = 15</math>, then the longest intervals starting at each possible position that do not go over this bound are <math>[9, 2], [2, 6, 3, 1], [6, 3, 1, 5, 0], [3, 1, 5, 0], [1, 5, 0, 7], [5, 0, 7], [0, 7], [7]</math>. Observe that as we advance the left edge, the right edge also advances. This is because when we advance the left edge, we decrease the sum, so the right edge "wants" to advance to increase the sum and bring it closer to <math>K</math> again. (Note that this doesn't work when there are negative numbers in the array.)

Here is the pseudocode. In the below, <code>A</code> is a zero-indexed array of length <code>n</code>. At each possible position for the left edge of the window, we advance the right edge as far as we can without going over the bound <code>K</code>. Then we advance the left edge. The variable <code>sum</code> keeps track of the sum so far.
<pre>
input n, A, K
best ← 0
l ← 0
r ← 0
sum ← 0
while l < n
if sum + A[r] ≤ K // then we can advance the right edge
sum ← sum + A[r]
r ← r + 1
best ← max(best, r-l)
sum ← sum - A[l] // now advance the left edge
l ← l + 1
</pre>

A similar problem asks us to find the longest interval of an array in which no element is repeated. This is solved in essentially the same way. We start with an empty window, <math>l = r = 0</math>. Then we repeatedly advance the right edge until we hit an element we've already seen somewhere in the window; at this point, we have to start advancing the left edge until we remove the previous occurrence of that value. Then the right edge starts advancing again, and so on.

==Problems==
* {{Problem|ccc96s5|CCC '96 - Maximum Distance}}
* {{Problem|ccc03s2p5|CCC '03 - Longest Substring}}
* {{SPOJ|BROKEN|Broken Keyboard @ SPOJ}}

==See also==
[[Sliding range minimum query]]

@@ Line 39: / Line 39: @@
 * {{SPOJ|KPMATRIX|Matrix @ SPOJ}}
 * {{SPOJ|HOTELS|Hotels Along the Croatian Coast @ SPOJ}}
 ==See also==
 [[Sliding range minimum query]]

@@ Line 38: / Line 38: @@
 * {{SPOJ|FSEATS|Finding Seats @ SPOJ}}
 * {{SPOJ|KPMATRIX|Matrix @ SPOJ}}
 ==See also==
 [[Sliding range minimum query]]

@@ Line 19: / Line 19: @@
 sum &larr; 0
 while l < n
-     if sum + A[r] &le; K        // then we can advance the right edge
+     // The inner 'while' loop will not change the asymptotic complexity of O(N) , because r is incremented at most N times
          sum &larr; sum + A[r]
          r &larr; r + 1

@@ Line 34: / Line 34: @@
 * {{Problem|ioi0611|IOI '06 - Deciphering the Mayan Writing}}
 * {{SPOJ|BROKEN|Broken Keyboard @ SPOJ}}
 ==See also==
 [[Sliding range minimum query]]

@@ Line 23: / Line 23: @@
          r &larr; r + 1
      best &larr; max(best, r-l)
-     sum &larr; sum - A[l]       // now advance the left edge
+     sum &larr; sum - A[l]         // now advance the left edge
      l &larr; l + 1
 </pre>
@@ Line 32: / Line 32: @@
 * {{Problem|ccc96s5|CCC '96 - Maximum Distance}}
 * {{Problem|ccc03s2p5|CCC '03 - Longest Substring}}
 * {{SPOJ|BROKEN|Broken Keyboard @ SPOJ}}
 ==See also==
 [[Sliding range minimum query]]