Talk with You Series #2

Intro

Today we gonna kick off our overview about concepts which are used to tackle various algorithmic problems. An understanding of a certain concept might give you an intuition from which angle to start thinking about the potential solution.

There are different but not too much concepts out there. Today I will invest your attention into sliding window concept.

Sliding Window

The concept of the sliding window is a bit more involved, than at first sight. I will demonstrate that within practical examples. For now, keep in mind, conceptual idea is that we will have some window which we have to move. Let's start from the example right away.

Assume you have an array of integers and predefined size of the subarrays. You are asked to find such a subarray (aka window) which sum of values would be maximum among others.

array = [1, 2, 3]
window_size = 2

# conceptually
subarray_1 = [1, 2] --> sum 3
subarray_2 = [2, 3] --> sum 5

maximum_sum = 5

Well, looks quite straightforward:
(1) sliding window of size 2
(2) 2 subarrays
(3) count the sum of each
(4) find the max between them

Let's implement it.

def foo(array: List[int], size: int) -> int:
    maximum = float("-inf")

    for idx in range(size, len(array)+1):
        left, right = idx-size, idx
        window = array[left:right]
        maximum = max(maximum, sum(window))

    return maximum 

Well, seems we've just efficiently used the concept of sliding window. Actually, not exactly. We might get "proof" of that by understanding the time complexity of the solution.

The complexity will be O(l)*O(w), where l is amount of windows in array and w is amount of elements in window. In other words, we need to traverse l windows and for each l-th window we need to calculate the sum of w elements.

What is questionable in here? Let's conceptually depict the iterations to answer the question.

array = [1, 2, 3, 4]
window_size = 3

iterations
1 2 3 4 5
|___|
  |___|
    |___|  

The answer is that even though we're sliding the array, on each iteration we need to "recalculate" k-1 elements which were already calculated on the previous iteration.

Basically, this insight should suggest us to ask a question:

"is there a way to take advantage of calculations from previous step?"

The answer is yes. We can get the sum of elements of the window by adding and subtracting the first and the next after the window elements. Let me put this idea into the code.

def foo(array: List[int] = None, size: int = 0) -> int
    window_start, max_, window_sum_ = 0, float("-inf"), 0
    for window_end in range(len(array)):
        if window_end > size - 1:
            window_sum_ -= array[window_start]
            window_start += 1
        window_sum_ += array[window_end]
        max_ = max(max_, window_sum_)
    return max_

assert foo(array=[1, 2, 3, 4], size=3) == 9

Here we might see, at the point when we constructed the subarray of length of size, we started subtracting the very first element from the window sum, what allows us to reuse calculations from the previous step.

Now, we might say we efficiently utilised the concept of sliding window whereas we got a proof checking the time complexity, which reduced from O(l*w) to O(l), where l is the amount of windows we will slide.

The major idea which I'd like to highlight, sliding window concept is not just about slicing the iterable with the window of specific size.

Let me give you some problems, where we will learn how to detect the problem might involve a sliding window concept as well as what exactly you might do with the window itself.

Problems Overview

Since I'm talking here just about concepts, I'd skip "how to count something inside of the window".

Problem one

Given an array, find the average of all contiguous subarrays of size K in it.

1. Sliding window ? - contiguous subarrays the first keyword, meaning we should take care of windows, which would represent a contiguous subarray(s).
2. Do we know the size of sliding window ? - yeap, K, we got the size of window, which should be the length of K.
3. What exactly are we supposed to manage/check within sliding window ? - find the average of ...

Good, now we might define the approach the way: iterate over the input array with the window of size K. On each iteration count the average of window ...

Problem two

Given an array of positive numbers and a positive number K, find the maximum sum of any contiguous subarray of size K.

1. Sliding window ? - contiguous subarrays again, the first keyword, meaning we should take care of windows, which would represent a contiguous subarray(s).
2. Do we know the size of sliding window ? - yeap, K, we got the size of window, which should be the length of K.
3. What exactly are we supposed to manage/check within sliding window ? - .. the sum ...

Now: traverse the input array with the window of size K. On each iteration count the sum of window ...

Problem three

Given an array of positive numbers and a positive number S, find the length of the smallest contiguous subarray whose sum is greater than or equal to S.

1. Sliding window ? - contiguous subarrays again, the first keyword, meaning we should take care of windows, which would represent a contiguous subarray(s).
2. Do we know the size of sliding window ? - actually no, we need to figure it out.
3. What exactly are we supposed to manage/check within sliding window ? - ... sum is >= to S ...

Now, we might define the approach the way: "firstly, iterate over input array and construct such a first window, which would satisfy the conditions (sum is >= to S). Once done, move window, managing window start and end ..."

Problem four

Given a string, find the length of the longest substring in it with no more than K distinct characters.

1. Sliding window ? - longest substring, the first keyword, meaning we should take care of windows, which would represent a substrings.
2. Do we know the size of sliding window ? - no, we need to figure it out.
3. What exactly are we supposed to manage/check within sliding window ? - ... amount of distinct characters ...

The approach in here is a bit more involved, thus I'll skip it here.

Problem five

Given an array of integers where each integer represents a fruit tree, you are given two baskets, and your goal is to put the maximum number of fruits in each basket. The only restriction is that each basket can have only one type of fruit.
You can start with any tree, but you cant skip a tree once you have started. You will pick one fruit from each tree until you cannot, i.e., you will stop when you have to pick from a third fruit type.
Write a function to return the maximum number of fruits in both baskets.

Seems not that obvious, let's simplify the conditions first.

There is an input array. Array might contain only 2 distinct digits (buckets). You are asked to find such contiguous subarray whose length would be the maximum.

Now it's times easier to see we might work with sliding window concept.

1. Sliding window ? - contiguous subarray
2. Do we know the size of sliding window ? - no, we need to figure it out.
3. What exactly are we supposed to manage/check within sliding window ? - ... whether digits are distinct and the length of the window ...

Problem six

Given a string and a pattern, find out if the string contains any permutation of the pattern.

Firstly, we do have 2 strings, original and pattern. We know we have somehow compare original and pattern, what lead to the idea, we need construct the window of size of the pattern and further perform permutations check. This means, we might use sliding window concept.

Outro

When you deal with sliding window keep in mind following questions:

• do you understand the size of the window
• do you understand how to construct the window
• do you understand how to move/shrink the window
• do you understand what is valid/invalid window
• do you understand how to make invalid window valid one

The above is the detailed content of Talk with You Series #2. For more information, please follow other related articles on the PHP Chinese website!