Sliding Window Technique

A paradigm to optimize algorithms complexities.

So I was going to explain this concept to a friend earlier this week then I thought I could write about it because many other friends might gain from it. Let’s get started.😎

I am assuming you have knowledge of calculating the time and space complexities of solutions.”If you’re not, you can learn about it here

Sliding window Algorithm is a variation of two pointer approach for solving arrays and strings problems. Using this technique helps decrease time complexities from O(n³) to O(n²) or from O(n²) to O(n). The subarray is visualized like a sliding window as it movies from one end of the array to another.

When do we use this pattern?

No, We definitely can’t the throwing sliding window on every problem we see huh.

that’s bad really 😔

1. When we are solving problems related to ordered or iterable data structures. e.g Arrays, Strings, Linked lists.
2. When we are sure that we have to cover the whole space of a given data structure. e.g Iterating through a list of numbers.
3. When we have solutions related to problems of the above specifications that run in O(n³) or O(n²) time.
4. Problems related to subarrays, minimum, maximum, longest, shortest, etc.

There Are 2 Variants Of Sliding Window Problems.

CONSTANT WINDOW VARIANT.

The subarray(Window) has constant numbers of elements, In the image below the number of elements in the window is 3. Let’s solve a few problems.

IMAGE A.

Problems :

1. Consider this problem: Given this array

int array[] = new int[]{1, 4, 7, 3, 2, 4, 1, 0};
int k = 3

Let’s calculate the sum of each subarray of size 3 :

INTUITION

From Image A, we want to calculate the sum of each sub-array of size 3 in the array. Calculating it :

subarray A = 1 + 4 + 7 = 12
subarray B = 4 + 7 + 3 = 14 
...

Let’s put it into code :

BRUTE FORCE APPROACH

While we iterate over the elements in the array, we would iterate over the elements in each subarray to get the sums respectively.

Result is

[12, 14, 12, 9, 7, 5]

This approach is not efficient because we had to iterate inside another iteration. Therefore the time complexity for the above solution is

 O(n-k) * k ~ O(n*k) 

where the number of items in the subarray is k, and n is the number of items in the array.

SLIDING WINDOW APPROACH

Result is :

[12, 14, 12, 9, 7, 5]

The time complexity for the above solution is O(n - k) ~ O(n) because we looped over the array items y n — k times.

2. Sliding Window Maximum: leetcode239

I’ll advise taking some minutes to look at this leetcode problem and solve it by coming up with a lazy approach and a sliding window approach, heh, that’s a hint right there lol 😉

BRUTE FORCE APPROACH

The time complexity for the above solution is O(n * k * log k).

How?

Iterating through the array = o(n)

Copying the range of values sized k = O(k)

Adding each item in the subarray into the PriorityQueue = log(k)

The time complexity for the above solution is O(n * log n).

DYNAMIC WINDOW APPROACH

The subarray(Window) is dynamic i.e the numbers of elements in the subarray changes, by how much? well, that depends on the problem and your implementation. Basically, we are increasing the size of the subarray until a certain condition is met. We would get a better context from the Image and problems below.

IMAGE B

1. Minimum Size Subarray Sum: leetcode209

Take a look at the leetcode problem statement first to have a better understanding of what we are trying to do... we need to calculate the minimum size of the subarray that gives us a certain sum, we are increasing the size of the subarray until the sum of all the elements in the subarray is greater or equal to that certain sum, that way we can record the size of the subarray remove some elements add some while within being cautious of the constraints.

2. Longest Substring Without Repeating Characters: Leetcode 3

Just like we did before, let’s try to solve this leetcode problem on our own then check the solution later.

Oh well, I hope we enjoyed the whole process, I did and I can’t wait to come up with more topics to write on. Thanks.

If there are any questions you can catch me on twitter 😎 and shout out to thegirlobsessedwithtech for helping out with the designs.
✌🏽