Siding window is a method for iterating over a linear collection by maintaining a window range indices (a group of consecutive elements) to satisfy the problem constraints

Sliding window is an improvement over brute force iteration to reduce the time complexity

Let's see a specific example

Sliding window maximum problem

  • Given an array a and a number k

  • Write an algorithm to find the maximum sum of k consecutive elements in a

Example

  • Input [5, 7, 2, 9, 4] and 2, expected output 13

Approach 1: Brute force

  • Iterating over a one by one element to find max sum

  • Output
13  
  • Time complexity: O(n*k)

  • Space complexity: O(1)

Approach 2: Sliding window

  • Iterating over a window by window to find max sum

  • Output
-9
  • Time complexity: O(n)

  • Space complexity: O(1)

Share to social

Giau Ngo

Giau Ngo is a software engineer, creator of HelloKoding. He loves coding, blogging, and traveling. You can find him on Twitter, GitHub and LinkedIn