Sliding window algorithm

Help you have good picture and easy for understanding about Sliding Window Algorithm

I. What is sliding window?

In general, sliding window is technical use to reduce nested loop and increase performance for operation.

Think about it like range of windows in the bus, each window will maintain an element, and after move window to next element, recalculate window condition again, until this window satisfy target of problem.

II. When use sliding window algorithm

We use sliding window in case the problem we solve relative with:

Sub Set, Sub Array, Sub String, Array, String, Set, Largest Sum, Largest Medium Sum, Max Sum, Min Sum

III. The art of sliding window

The art of sliding window technical is keep previous calculation to avoid recalculate again, and this will help reduce complexity of code from O(n²) to O(n).

Let see example:

Find the maximum of k consecutive numbers in array:

array = [1, 12, -5, -6, 50, 3]

k = 4

expected output: maxSum = 51

1. Naive Approach

func findMaxSumKConsecutiveNumbers(array: [Int], k: Int) -> Int {
  
  var maxSum = Int.min
  for i in 0..<(array.count - k + 1) {
    var sum: Int = 0
    for j in i..<(i+k) {
      sum = sum + array[j]
    }
    if sum > maxSum {
      maxSum = sum
    }
  }
  return maxSum
}

You can see the complexity of about code is O(n * k), near same O(n²)

This implementation will slow when n too big, k too big also.

Let optimize implementation with sliding window algorithm.

2. Time of sliding window

Assume windowSum is sum of k elements after each of iteraction.

In above image, after each of moving, the windowSum will recalculate again by:

Add new value and subtract previous value to window sum:

• windowSum = windowSum + 50 –1

func findMaxSumKConsecutiveNumbersUsingSlidingWindow(array: [Int], k: Int) -> Int {
  var windowSum = 0
  // Calculate first window value
  for i in 0..<k {
    windowSum = windowSum + array[i]
  }
  var maxSum = Int.min
  for i in 1..<(array.count - k + 1) {
    if windowSum > maxSum {
      maxSum = windowSum
    }
    windowSum = windowSum + array[i + k - 1] - array[i - 1]
  }
  return maxSum
}

Let see, we done job, our optimization is better, the complexity now just O(n)

Sliding window obviously is one of the best algorithm for optimize, it avoid nested loop, it’s really useful and worth for us.