Sliding Window

Can a sliding window be static?

No, a “sliding window” by definition is not static. The term refers to a set of elements that “slides” over the data - that is, the window moves by removing an element from one end and adding a new one at the other end. This is typically used in array or list manipulation problems where you need to track a subset of the elements (the “window”) as it moves through the array.

If a window does not move (i.e., it is “static”), then it is not technically a “sliding window”. It’s just a subset or segment of the data.

However, the size of the sliding window can be static or dynamic. A static-size sliding window maintains the same number of elements as it moves, while a dynamic-size sliding window can grow or shrink based on certain conditions. But in both cases, the window itself still “slides” over the data.

Can a sliding window size be fixed?

Yes, a sliding window’s size can be fixed. This is often the case when you’re dealing with problems where you’re asked to find or calculate something over a specific number of elements continuously in a list or an array.

In such a case, you would slide your window of a fixed size across your data, always keeping the same number of elements in the window. This type of fixed-size window is often used in problems related to finding maximum/minimum sums in k-size subarrays, longest continuous sequences, or generally when the problem specifies a certain length of subarray or substring to consider.

However, there are also problems where the size of the sliding window can be variable. The size of the window can increase or decrease based on certain conditions. These types of problems often involve finding optimal lengths of substrings or subarrays that satisfy certain conditions.

Here’s a simple example of how to implement a fixed-size sliding window using Python:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

def sliding_window(arr, window_size):
    # Initialize the starting index of the sliding window
    start = 0

    # Slide the window through the list
    while start + window_size - 1 < len(arr):
        # Print out the current window
        print(arr[start:start + window_size])

        # Move the window forward
        start += 1

# Testing the function
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
window_size = 3
sliding_window(arr, window_size)

In this example, we are defining a function sliding_window that takes a list arr and an integer window_size as arguments. It starts with the window at the beginning of the list, prints the elements in the window, and then slides the window one element to the right, repeating the process until the window reaches the end of the list.

Can a sliding window size be dynamic?

Yes, the size of a sliding window can be dynamic and it’s very common in many problems. In a dynamic sliding window problem, the size of the window can expand or contract based on certain conditions.

One common use case for a dynamic sliding window is when you’re trying to find a contiguous subset of an array that meets a certain condition. For instance, if you’re trying to find the smallest contiguous subarray with a sum greater than a certain target, you could start with a window of size 0 at the beginning of the array and then expand the window until the sum is greater than the target. If the sum is greater than the target, you could then contract the window from the left until the sum is less than or equal to the target again. This process continues until you’ve examined all potential windows in the array.

Here is an example problem: “Minimum Size Subarray Sum” (LeetCode 209): Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray [numsl, numsl+1, …, numsr-1, numsr] of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead.

So, the dynamic sliding window technique can be a very powerful tool when the problem involves optimizing something over all contiguous subarrays or substrings of an array or string.

Creating a dynamic sliding window in Python can be a bit trickier than a fixed-size sliding window because the size of the window can change based on certain conditions. However, the overall concept is still quite similar.

Here’s an example of a dynamic sliding window that increases in size each time it encounters an odd number:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

def dynamic_sliding_window(arr):
    window_start = 0
    window_size = 1

    while window_start + window_size - 1 < len(arr):
        window = arr[window_start : window_start + window_size]
        print(window)

        # Increase the window size if the last number in the window is odd
        if window[-1] % 2 != 0:
            window_size += 1

        # Move the window forward
        window_start += 1

# Test the function
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
dynamic_sliding_window(arr)

In this example, the sliding window starts with a size of 1 and increases in size each time it encounters an odd number. The window slides one element to the right after each iteration, similar to the fixed-size sliding window.

What are the leetcode problems that can be solved using sliding window size that is dynamic?

Several LeetCode problems can be solved using a dynamic sliding window technique, where the size of the window can change based on certain conditions. Here are some examples:

  1. “Longest Substring Without Repeating Characters” (LeetCode 3): Given a string, find the length of the longest substring without repeating characters. Here, the sliding window size increases as long as no repeating characters are found and shrinks when a repeating character is encountered.

  2. “Minimum Window Substring” (LeetCode 76): Given two strings s and t, return the minimum window in s which will contain all the characters in t. If there is no such window in s that covers all characters in t, return the empty string “”. The sliding window size changes to find the smallest possible window that contains all the characters.

  3. “Sliding Window Maximum” (LeetCode 239): Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window. This problem uses a dynamic window to keep track of the maximum value in the current window.

  4. “Fruit Into Baskets” (LeetCode 904): In a row of trees, the i-th tree produces fruit with type tree[i]. You start at any tree of your choice, then repeatedly perform the following steps:

    • Add one piece of fruit from this tree to your baskets. If you cannot, stop.
    • Move to the next tree to the right of the current tree. If there is no tree to the right, stop.

    You have two baskets, and each basket can carry any quantity of fruit, but you want each basket to only carry one type of fruit each. What is the total amount of fruit you can collect with this procedure?

  5. “Substring with Concatenation of All Words” (LeetCode 30): You are given a string s and an array of strings words of the same length. Return all starting indices of substring(s) in s that is a concatenation of each word in words exactly once, in any order, and without any intervening characters. You can return the answer in any order.

In all these problems, the size of the sliding window is dynamic - it increases or decreases based on certain conditions in the problem statement.

What are the leetcode problems that can be solved using sliding window size that is fixed?

Several LeetCode problems can be solved using a fixed sliding window technique. Here are some examples:

  1. “Maximum Average Subarray I” (LeetCode 643): Given an array consisting of n integers, find the contiguous subarray of given length k that has the maximum average value. And you need to output the maximum average value. This is a classic fixed-size sliding window problem as the length of the subarray is fixed.

  2. “Find All Anagrams in a String” (LeetCode 438): Given a string s and a non-empty string p, find all the start indices of p’s anagrams in s. Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100. The order of output does not matter. This can be solved with a fixed size sliding window, where the window size is the length of string p.

  3. “Sliding Window Maximum” (LeetCode 239): Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.

  4. “Binary Subarrays With Sum” (LeetCode 930): In an array A of 0s and 1s, how many non-empty subarrays have sum S? This problem can be solved with a fixed-size sliding window when the sum S of the sliding window is reached.

  5. “Subarray Product Less Than K” (LeetCode 713): Your are given an array of positive integers nums. Count and print the number of (contiguous) subarrays where the product of all the numbers in the subarray is less than k. This problem uses a sliding window where the size of the window expands whenever the product is less than k and contracts whenever the product is greater than or equal to k.

In all these problems, the size of the sliding window is fixed - it either stays the same or changes based on certain conditions in the problem statement.

Is the criteria that make a subarray “valid” in sliding window problems an invariant?

In the context of sliding window problems, an invariant is a condition that remains true throughout the execution of the algorithm. The criteria that define whether a subarray is “valid” can be considered an invariant if they remain consistent throughout the algorithm.

For example, in a problem where you need to find the smallest subarray with a sum greater than a given target, the criteria for a “valid” subarray might be that the sum of the elements within the window must be greater than the target value. As you slide the window through the array, these criteria remain the same, even though the elements within the window may change.

So yes, the criteria that make a subarray “valid” can be viewed as an invariant within the context of the specific problem you are solving. They provide the consistent rules and conditions that guide the movement and resizing of the sliding window as you iterate through the array.

Are you talking about the loop invariant here?

Yes, I was referring to the concept of a loop invariant in the context of the sliding window algorithm. A loop invariant is a property or condition that holds before and after each iteration of a loop.

In the sliding window problems, the criteria that make a subarray “valid” could be seen as a loop invariant, especially if the algorithm uses a loop to slide the window through the array. The validity criteria would remain consistent or invariant across each iteration of the loop, serving as a guide for how the window should be moved or resized.

It helps in maintaining the consistency and correctness of the algorithm, allowing you to reason about the behavior of the code and prove its correctness.

Given an array of positive integers nums and an integer k, return the number of subarrays where the product of all the elements in the subarray is strictly less than k.

For example, given the input nums = [10, 5, 2, 6], k = 100, the answer is 8. The subarrays with products less than k are:

[10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6]

if k <= 1, can we have any valid windows?

No, if ( k \leq 1 ), you cannot have any valid subarrays where the product of all the elements in the subarray is strictly less than ( k ). Since the given array consists of positive integers, the minimum product you can achieve with any non-empty subarray is 1 (if there’s an element 1 in the array). Therefore, if ( k ) is less than or equal to 1, no subarray will satisfy the condition of having a product strictly less than ( k ), and the result would be 0 valid subarrays.

Let’s go through an example to make the concept clearer.

Consider the array nums = [2, 3, 4] and ( k = 1 ).

We want to find subarrays where the product of all elements in the subarray is strictly less than ( k ).

Since ( k = 1 ), we are looking for subarrays where the product of all elements is strictly less than 1.

Now, let’s look at some potential subarrays:

  • [2]: The product is 2, which is not less than 1.
  • [3]: The product is 3, which is not less than 1.
  • [4]: The product is 4, which is not less than 1.
  • [2, 3]: The product is 6, which is not less than 1.
  • [3, 4]: The product is 12, which is not less than 1.
  • [2, 3, 4]: The product is 24, which is not less than 1.

As you can see, no matter which subarray we choose, the product of its elements will never be less than 1 since all the numbers in the array are positive integers. Therefore, in this case, there are no valid subarrays that meet the given condition, and the result is 0.

If you have an array of positive integers, and you’re looking for subarrays where the product is less than 1, you won’t find any such subarrays if ( k \leq 1 ). The positive integers will always multiply to a value greater than or equal to 1, so the condition for valid subarrays cannot be met.

The only thing we know about the input is : array of positive integers (it could contain multiple 1s for instance)

You are correct, and I appreciate your clarification. Since the array could contain positive integers including 1, let’s explore a different example that incorporates this possibility.

Consider the array nums = [1, 2, 1, 1] and ( k = 1 ).

Again, we are looking for subarrays where the product of all elements is strictly less than 1.

Since ( k = 1 ), and all elements in the array are positive integers, no product of any subarray containing the number 2 or more will be less than 1.

However, if the array contains the integer 1, the product of any subarray containing only 1’s will be equal to 1, and thus still not less than 1.

In this case, we find that the result remains the same: there are no valid subarrays that meet the given condition, and the result is 0.

So even with the possibility of the array containing the integer 1, if ( k \leq 1 ), there cannot be any valid subarrays where the product of all elements is strictly less than ( k ).

The reason is that the product will at least be 1, even if we have multiple 1s in the input. So it cannot be less than 1.

Yes, you’ve succinctly summarized the key point. If the array consists of positive integers, including multiple 1s, the product of any subarray will be at least 1. Therefore, if ( k \leq 1 ), there cannot be any valid subarrays where the product of all elements is strictly less than ( k ).

I am having difficulty in understanding the formula that is derived here:

If a problem asks for the number of subarrays that fit some constraint, we can still use sliding window, but we need to use a neat math trick to calculate the number of subarrays.

Let’s say that we are using the sliding window algorithm we have learned and currently have a window (left, right). How many valid windows end at index right?

There’s the current window (left, right), then (left + 1, right), (left + 2, right), and so on until (right, right) (only the element at right).

You can fix the right bound and then choose any value between left and right inclusive for the left bound. Therefore, the number of valid windows ending at index right is equal to the size of the window, which we know is right - left + 1.

The formula described here is determining the number of valid subarrays or windows that end at a given index ( \text{right} ). It’s a way of translating the flexibility we have with a sliding window into a concrete count of subarrays.

  1. Fix the Right Bound: We’re looking at all subarrays that end at the index ( \text{right} ). So we fix this right bound and explore the possible left bounds.

  2. Possible Left Bounds: The left bound can be at ( \text{left} ), ( \text{left} + 1 ), ( \text{left} + 2 ), … all the way to ( \text{right} ). This provides a range of valid windows. Essentially, we can take just the element at ( \text{right} ), or add the element just before it, and so on, back to the initial ( \text{left} ).

  3. Counting the Valid Windows: Since there are ( \text{right} - \text{left} + 1 ) options for the left bound (including both ends), that means there are ( \text{right} - \text{left} + 1 ) valid subarrays or windows that end at the index ( \text{right} ).

Here’s an example to illustrate:

  • Suppose our current window is at indices ( \text{left} = 2 ) and ( \text{right} = 5 ).
  • The subarrays ending at ( \text{right} ) include:
    • ( (2, 5) ) (original window)
    • ( (3, 5) ) (shift left by one)
    • ( (4, 5) ) (shift left by two)
    • ( (5, 5) ) (just the element at right)
  • The total count of valid windows ending at ( \text{right} ) is ( 5 - 2 + 1 = 4 ), matching our enumeration of options.

In a sliding window problem, this counting allows you to accumulate the contribution of a window dynamically as you expand and contract it, thus leading to an efficient solution.

No, the formula ( \text{right} - \text{left} + 1 ) in this context is not a known mathematical equation in a broader sense. It’s a simple expression that captures the size of the current window or subarray in the specific context of a sliding window algorithm.

In the context of algorithms and programming, this expression is a common way to calculate the length of a segment, range, or window given the starting and ending indices. It has a straightforward interpretation but doesn’t correspond to a named theorem or equation in mathematics.

Yes, the “+1” in the formula ( \text{right} - \text{left} + 1 ) accounts for the fact that the array is 0-indexed, and you are including both the left and right bounds of the window.

Consider an example where the left index is 2, and the right index is 4 in a 0-indexed array:

  • The element at index 2 is the first element in the window.
  • The element at index 3 is the second element in the window.
  • The element at index 4 is the third element in the window.

So the size of the window is ( \text{right} - \text{left} + 1 = 4 - 2 + 1 = 3 ), corresponding to the three elements in the window. If the array were 1-indexed, you would simply subtract the left from the right to get the size, but the “+1” is necessary to correctly handle 0-indexed arrays.

Let’s break down the concept using a simple example:

Imagine you have an array, and you are asked to look at sections of it that contain exactly ( k ) elements. These sections are often referred to as “windows.”

Fixed Length ( k )

When a problem specifies a fixed window length of ( k ), it means every window you look at must contain exactly ( k ) elements.

Why It’s Easy

This constraint makes things easier because you know the exact size of every window you need to look at, so there’s no ambiguity.

How It Works

  1. Build the First Window: You start by looking at the first ( k ) elements of the array (from index 0 to ( k - 1 )).

  2. Slide the Window: After that, you move the window one step to the right by adding one new element on the right end and removing one element from the left end. This keeps the window size at ( k ).

Example with ( k = 2 )

Let’s say you have an array, and you’re looking at windows of size 2 (( k = 2 )).

  • First, you look at elements at indices [0, 1].
  • Then you want to add the element at index 2. Your window becomes [0, 1, 2].
  • But wait, the window size must be 2, so you need to remove the element at index 0.
  • Your new window is [1, 2], still with ( k = 2 ) elements.

Conclusion

The fixed length ( k ) makes the problem more straightforward because you know exactly how large each window should be. You keep adding one element to the right and removing one from the left, so the window “slides” across the array without changing size.

The expression (i - k) is used to calculate the index of the element that should be removed from the window as it slides to the right. Here’s an explanation of why that is:

  • (i): This is the current index where the new element is being added to the window. As you slide the window to the right, (i) moves one step at a time.

  • (k): This is the fixed size of the window, or how many elements should be in the window at any given time.

  • (i - k): By subtracting the window size (k) from the current index (i), you find the index of the element that is now “outside” the window on the left side. This is the element that must be removed to keep the window size at (k).

Example:

Let’s say you have an array and (k = 3), meaning the window size is 3.

  1. Start: Window includes elements at indices [0, 1, 2].
  2. Slide: Add element at index 3, so now you have [0, 1, 2, 3].
  3. Remove: To keep the window size at 3, you must remove the element at index (i - k = 3 - 3 = 0). Now your window is [1, 2, 3].

So the expression (i - k) is a way to find the index of the element that must be removed as the window slides to the right. It ensures that the window always contains exactly (k) elements.