Home/

...

/

Introduction

Introduction

Some learning resources for the Sliding Window pattern

Real-world problems

Many problems in the real world share the sliding window pattern. For example:

  • Telecommunications: Find the maximum number of users connected to a cellular network’s base station in every kk milliseconds sliding window.
  • E-commerce: Given a dataset of product IDs in the order they were viewed by the user, and a list of products that are likely to be similar, find how many times these products occur together in the dataset.
  • Video streaming: Given a stream of numbers representing the number of buffering events in a given user session, calculate the median number of buffering events in a one-minute interval.
  • Social media content mining: Given the lists of topics that two users have posted about, find the shortest sequence of posts by one user that includes all the topics that the other user has posted about.

Dry-run templates

This is the better, more efficient, solution suggested in the lesson:

Press + to interact
Python 3.5
def find_averages_of_subarrays(K, arr):
  result = []
  windowSum, windowStart = 0.0, 0
  for windowEnd in range(len(arr)):
    windowSum += arr[windowEnd]  # add the next element
    # slide the window, we don't need to slide if we've not hit the required window size of 'k'
    if windowEnd >= K - 1:
      result.append(windowSum / K)  # calculate the average
      windowSum -= arr[windowStart]  # subtract the element going out
      windowStart += 1  # slide the window ahead
  return result
def main():
  result = find_averages_of_subarrays(5, [1, 3, 2, 6, -1, 4, 1, 8, 2])
  print("Averages of subarrays of size K: " + str(result))
main()

To help students understand how the solution works, they may be encouraged to run through the provided solution with the following sample inputs:

Sample Input #1

K=5, Array: {1, 3, 2, 6, -1, 4, 1}

Iteration number

Line number

windowStart

windowEnd

windowSum

result[]

-

2 - 3

0

-

0.0

[]

1

4 - 5

0

0

1.0

[]

2

4 - 5

0

1

4.0

[]

3

4 - 5

0

2

6.0

[]

4

4 - 5

0

3

12.0

[]

5

4 - 5

0

4

11.0

[]

5

7 - 10

1

4

10.0

[2.2]

6

4 - 5

1

5

14.0

[2.2]

6

7 - 10

2

5

11.0

[2.2, 2.8]

7

4 - 5

2

6

12.0

[2.2, 2.8]

7

7 - 10

3

6

10.0

[2.2, 2.8, 2.4]

Sample Input #2

K=2, Array: {20, 0, 0, -1, 0, 5, 10, -10}

Iteration number

Line number

windowStart

windowEnd

windowSum

result[]

-

2 - 3

0

-

0

[]

1

4 - 5

0

0

20.0

[]

2

4 - 5

0

1

20.0

[]

2

7 - 10

1

1

0.0

[10.0]

3

4 - 5

1

2

0.0

[10.0]

3

7 - 10

2

2

0.0

[10.0, 0.0]

4

4 - 5

2

3

-1.0

[10.0, 0.0]

4

7 - 10

3

3

-1.0

[10.0, 0.0, -0.5]

5

4 - 5

3

4

-1.0

[10.0, 0.0, -0.5]

5

7 - 10

4

4

0.0

[10.0, 0.0, -0.5, -0.5]

6

4 - 5

4

5

5.0

[10.0, 0.0, -0.5, -0.5]

6

7 - 10

5

5

5.0

[10.0, 0.0, -0.5, -0.5, 2.5]

7

4 - 5

5

6

15.0

[10.0, 0.0, -0.5, -0.5, 2.5]

7

7 - 10

6

6

10.0

[10.0, 0.0, -0.5, -0.5, 2.5, 7.5]

8

4 - 5

6

7

0.0

[10.0, 0.0, -0.5, -0.5, 2.5, 7.5]

8

7 - 10

7

7

-10.0

[10.0, 0.0, -0.5, -0.5, 2.5, 7.5, 0.0]

Step-by-step solution construction

The first step in solving any problem that exhibits the sliding window property is to set up the code that iterates through the given array and considers the correct set of contiguous elements as the window in each iteration.

Question to ask learners: how many times will line 20 execute given an array of 99 elements and a window size of 55?

Press + to interact
Python 3.5
def printArraywithSlicedMarkers(array, sliceStart, sliceEnd, sliceOpening, sliceEnding):
  out = "["
  for i in range(len(array)):
    if sliceStart == i:
      out+=sliceOpening
    sliceEnding = '»' if sliceEnd == i else ''
    out+=str(array[i]) + sliceEnding + ", "
  out = out[0:len(out) - 2]
  out += "]"
  return out
def find_averages_of_subarrays(K, arr):
  result = []
  windowSum, windowStart = 0.0, 0
  for windowEnd in range(len(arr)):
    print("\nLoop index:", windowEnd)
    windowSum += arr[windowEnd]  # add the next element
    # slide the window, we don't need to slide if we've not hit the required window size of 'k'
    if windowEnd >= K - 1:
      print("Window starts at index", windowStart, ":", printArraywithSlicedMarkers(arr, windowStart, windowEnd, '«', '»'))
      windowStart += 1  # slide the window ahead
  return result
def main():
  inputArray = [1, 3, 2, 6, -1, 4, 1, 8, 2]
  print("Window Size: 5, input array: ", inputArray);
  result = find_averages_of_subarrays(5, inputArray)
  print("\nAverages of subarrays of size K: ", str(result))
main()

In the code snippet above, we use a custom method, printArrayWithSliceMarkers, to place markers around the current sliding window in each iteration.

Though we have not yet written any code to calculate the average of each window, we already know for sure that we have the correct window in each iteration.

Let’s add some logic to calculate the average of each window. As a first step, let’s calculate the sum of the contents of the current window (see line 10):

Press + to interact
Python 3.5
def printArraywithSlicedMarkers(array, sliceStart, sliceEnd, sliceOpening, sliceEnding):
  out = "["
  for i in range(len(array)):
    if sliceStart == i:
      out+=sliceOpening
    sliceEnding = '»' if sliceEnd == i else ''
    out+=str(array[i]) + sliceEnding + ", "
  out = out[0:len(out) - 2]
  out += "]"
  return out
def find_averages_of_subarrays(K, arr):
  result = []
  windowSum, windowStart = 0.0, 0
  for windowEnd in range(len(arr)):
    print("\nLoop index:", windowEnd)
    windowSum += arr[windowEnd]  # add the next element
    # slide the window, we don't need to slide if we've not hit the required window size of 'k'
    if windowEnd >= K - 1:
      print("Window starts at index", windowStart, ":", printArraywithSlicedMarkers(arr, windowStart, windowEnd, '«', '»'))
      print("Sum of current window:", windowSum)
      windowStart += 1  # slide the window ahead
  return result
def main():
  inputArray = [1, 3, 2, 6, -1, 4, 1, 8, 2]
  print("Window Size: 5, input array: ", inputArray);
  result = find_averages_of_subarrays(5, inputArray)
  print("\nAverages of subarrays of size K: ", str(result))
main()

The problem here is that though we drop the first value from the window at every step, we don’t subtract its value from the current window sum. So, the sum only increases in value (at least as long as the incoming value is positive), even though, clearly, this should not be the case.

Let’s now add code (see line 22) to subtract the value dropping out of the window:

Press + to interact
Python 3.5
def printArraywithSlicedMarkers(array, sliceStart, sliceEnd, sliceOpening, sliceEnding):
  out = "["
  for i in range(len(array)):
    if sliceStart == i:
      out+=sliceOpening
    sliceEnding = '»' if sliceEnd == i else ''
    out+=str(array[i]) + sliceEnding + ", "
  out = out[0:len(out) - 2]
  out += "]"
  return out
def find_averages_of_subarrays(K, arr):
  result = []
  windowSum, windowStart = 0.0, 0
  for windowEnd in range(len(arr)):
    print("\nLoop index:", windowEnd)
    windowSum += arr[windowEnd]  # add the next element
    # slide the window, we don't need to slide if we've not hit the required window size of 'k'
    if windowEnd >= K - 1:
      print("Window starts at index", windowStart, ":", printArraywithSlicedMarkers(arr, windowStart, windowEnd, '«', '»'))
      print("Sum of current window:", windowSum)
      windowSum -= arr[windowStart]
      windowStart += 1  # slide the window ahead
  return result
def main():
  inputArray = [1, 3, 2, 6, -1, 4, 1, 8, 2]
  print("Window Size: 5, input array: ", inputArray);
  result = find_averages_of_subarrays(5, inputArray)
  print("\nAverages of subarrays of size K: ", str(result))
main()

The formula for the average of a set of values is: sum of valuesnumber of values\frac{sum \space of \space values} {number \space of \space values}

So, if we simply divide the windowSum by the size of the window (K) , we’ll get the average of the values in the current window:

Press + to interact
Python 3.5
def printArraywithSlicedMarkers(array, sliceStart, sliceEnd, sliceOpening, sliceEnding):
  out = "["
  for i in range(len(array)):
    if sliceStart == i:
      out+=sliceOpening
    sliceEnding = '»' if sliceEnd == i else ''
    out+=str(array[i]) + sliceEnding + ", "
  out = out[0:len(out) - 2]
  out += "]"
  return out
def find_averages_of_subarrays(K, arr):
  result = []
  windowSum, windowStart = 0.0, 0
  for windowEnd in range(len(arr)):
    print("\nLoop index:", windowEnd)
    windowSum += arr[windowEnd]  # add the next element
    # slide the window, we don't need to slide if we've not hit the required window size of 'k'
    if windowEnd >= K - 1:
      windowAvg = windowSum/K; 
      print("Window starts at index", windowStart, ":", printArraywithSlicedMarkers(arr, windowStart, windowEnd, '«', '»'))
      print("Sum of current window:", windowSum, ", Average of current window:", windowAvg)
      windowSum -= arr[windowStart]; # subtract the element dropping out of the window
      windowStart += 1  # slide the window ahead
  return result
def main():
  inputArray = [1, 3, 2, 6, -1, 4, 1, 8, 2]
  print("Window Size: 5, input array: ", inputArray);
  result = find_averages_of_subarrays(5, inputArray)
  print("\nAverages of subarrays of size K: ", str(result))
main()

All that remains now is to store the calculated average of each window in the result array. We will adopt the convention that the average of a window starting at the ithi^{th} index in the input array will be stored at the ithi^{th} index in the result array.

Students may be asked to predict how many averages will be stored in result given an input array of 99 elements and a window of size 55.

Press + to interact
Python 3.5
def printArraywithSlicedMarkers(array, sliceStart, sliceEnd, sliceOpening, sliceEnding):
  out = "["
  for i in range(len(array)):
    if sliceStart == i:
      out+=sliceOpening
    sliceEnding = '»' if sliceEnd == i else ''
    out+=str(array[i]) + sliceEnding + ", "
  out = out[0:len(out) - 2]
  out += "]"
  return out
def find_averages_of_subarrays(K, arr):
  result = []
  windowSum, windowStart = 0.0, 0
  for windowEnd in range(len(arr)):
    print("\nLoop index:", windowEnd)
    windowSum += arr[windowEnd]  # add the next element
    # slide the window, we don't need to slide if we've not hit the required window size of 'k'
    if windowEnd >= K - 1:
      result.append(windowSum/K); 
      print("Window starts at index", windowStart, ":", printArraywithSlicedMarkers(arr, windowStart, windowEnd, '«', '»'))
      print("Sum of current window:", windowSum, ", Average of current window:", result[windowStart])
      print("result: ", result)
      windowSum -= arr[windowStart]; # subtract the element dropping out of the window
      windowStart += 1  # slide the window ahead
  return result
def main():
  inputArray = [1, 3, 2, 6, -1, 4, 1, 8, 2]
  print("Window Size: 5, input array: ", inputArray);
  result = find_averages_of_subarrays(5, inputArray)
  print("\nAverages of subarrays of size K: ", str(result))
main()