SLIDING WINDOW ALGORITHM

The sliding window technique is a way to solve problems that involve finding a specific pattern or set of elements within an array or a string. Instead of checking every possible combination of elements, which can be very time-consuming, the sliding window approach uses a "window" that moves across the data structure, checking for the desired pattern or condition as it goes. The sliding window is a problem-solving technique that's designed to transform two nested loops into a single loop. It applies to arrays or lists. These problems are painless to solve using a brute force approach in O(n2) or O(n3). However, the sliding window technique can reduce the time complexity to O(n).

The sliding window technique is particularly useful when you're dealing with problems that involve finding a continuous subarray, substring, or sequence that satisfies a certain condition. By using a window and sliding it across the data structure, you can efficiently check all possible subarrays or substrings without having to enumerate them explicitly, which can be computationally expensive.

This technique can help solve problems like finding the longest substring with unique characters, finding the smallest subarray whose sum is greater than a target value, or finding the maximum sum of any contiguous subarray (also known as the "maximum subarray problem").

When should the sliding window algorithm

More specifically, you should consider using the sliding window algorithm when your problem meets the following criteria:

1. Contiguous Substructure: The problem requires finding a contiguous subarray, substring, or sequence within a larger data structure (e.g., an array or a string). The substructure should not have any gaps or discontinuities.
2. Window-based Condition: The condition or constraint the substructure needs to satisfy can be evaluated based on the elements within a window (a subarray or substring of a specific size) that slides over the data structure.
3. Additive or Multiplicative Properties: The condition often involves additive or multiplicative properties, such as finding a subarray with a specific sum, product, or average value.
4. Frequency-based Conditions: The condition may also involve finding a substructure with a specific frequency or count of elements satisfying a certain property (e.g., finding the longest substring with at most k distinct characters).
5. Optimal Substructure and Overlapping Subproblems: The problem should exhibit an optimal substructure property, where the solution can be constructed from solutions to subproblems, and there may be overlapping subproblems that can be optimized using the sliding window technique.
6. Time Complexity Optimization: The sliding window algorithm should improve time complexity over brute-force approaches, typically achieving linear or near-linear time complexity.

If your problem meets these criteria, the sliding window algorithm can be an efficient approach to solving it. However, if the problem does not involve contiguous substructures, or if the condition cannot be evaluated efficiently for each window position, other techniques like dynamic programming, divide and conquer, or advanced data structures may be more appropriate.

CASE STUDY

Given the list of flowers: ['rose', 'sunflower', 'tulip', 'tulip', 'rose', 'tulip', 'sunflower', 'tulip', 'tulip', 'tulip', 'sunflower', 'rose', 'tulip', 'tulip']

We need to find the indices of the longest continuous stretch of three flowers of the same type using the sliding window technique.

Here's the approach:

Step 1: Initialize the Window We start with a window size of 3 to find the longest continuous stretch of three flowers of the same type. The initial window contains the first three elements of the list: Window: ['rose', 'sunflower', 'tulip']

Step 2: Check the Condition We check if the current window satisfies the condition, which is having three flowers of the same type. Since the current window has three different flower types, it does not satisfy the condition.

Step 3: Slide the Window Since the condition is not satisfied, we slide the window one step to the right by removing the leftmost element ('rose') and adding the next element from the list ('tulip'). Window: ['sunflower', 'tulip', 'tulip']

Step 4: Check the Condition Again We check if the new window satisfies the condition. This time, the window does not have the same flowers, so the condition is not satisfied.

Step 5: Slide the Window and Repeat We continue sliding the window one step at a time and checking the condition of each new window.

Here's the sequence of windows as we slide along the list:

• ['tulip', 'tulip', 'rose'] (2 tulips, condition not satisfied)
• ['tulip', 'rose', 'tulip'] (2 tulips, condition not satisfied)
• ['rose', 'tulip', 'sunflower'] (3 different types, condition not satisfied)
• ['tulip', 'sunflower', 'tulip'] (2 tulips, condition not satisfied)
• ['sunflower', 'tulip', 'tulip'] (2 tulips, condition not satisfied)
• ['tulip', 'tulip', 'tulip'] (3 tulips, condition satisfied, update the result)
• ['tulip', 'tulip', 'sunflower'] (2 tulips, condition not satisfied)
• ['tulip', 'sunflower', 'rose'] (3 different types, condition not satisfied)
• ['sunflower', 'rose', 'tulip'] (3 different types, condition not satisfied)
• ['rose', 'tulip', 'tulip'] (2 tulips, condition not satisfied)

Step 7: Return the Result After sliding the window through the entire list, we return the indices of the longest continuous stretches of three flowers of the same type (7, 8, 9).

Let's solve a Leetcode sliding window problem.

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

Input: [3, 5, 2, 1, 7], k=2
Output: 8        

SOLUTION:

Step 1: Initialize the Window Since the problem requires finding the maximum sum of any contiguous subarray of size k, we will start with a window of size k. The initial window will contain the first k elements of the array.

Window: [3, 5] Window Sum: 3 + 5 = 8

Step 2: Initialize the Maximum Sum We will initialize the maximum sum variable with the sum of the initial window, as it is the only subarray of size k we have seen so far.

Maximum Sum = 8

Step 3: Slide the Window We will now slide the window one step to the right by removing the leftmost element from the window and adding the next element from the array.

Window: [5, 2] Window Sum: 5 + 2 = 7

Step 4: Update the Maximum Sum We will compare the current window sum with the maximum sum seen so far. If the current window sum is greater, we will update the maximum sum.

Current Window Sum (7) < Maximum Sum (8) Maximum Sum remains unchanged (8)

Step 5: Slide the Window Again We will slide the window one more step to the right.

Window: [2, 1] Window Sum: 2 + 1 = 3

Step 6: Update the Maximum Sum We will compare the current window sum with the maximum sum seen so far.

Current Window Sum (3) < Maximum Sum (8) Maximum Sum remains unchanged (8)

Step 7: Slide the Window and Repeat We will continue sliding the window one step at a time until we reach the end of the array, updating the maximum sum whenever a larger sum is encountered.

Window: [1, 7] Window Sum: 1 + 7 = 8

Current Window Sum (8) = Maximum Sum (8) Maximum Sum remains unchanged (8)

Step 8: Return the Result After sliding the window through the entire array, we will return the maximum sum found, which is 8.

CODE:

def max_sum_subarray(arr, k):
    # Initialize the window sum
    window_sum = sum(arr[:k])
    
    # Initialize the maximum sum
    max_sum = window_sum
    
    # Slide the window
    for i in range(k, len(arr)):
        # Remove the leftmost element from the window
        window_sum -= arr[i - k]
        
        # Add the rightmost element to the window
        window_sum += arr[i]
        
        # Update the maximum sum
        max_sum = max(max_sum, window_sum)
    
    return max_sum

# Example usage
arr = [3, 5, 2, 1, 7]
k = 2
result = max_sum_subarray(arr, k)
print(f"Maximum sum of any contiguous subarray of size {k}: {result}")        

THANK YOU!