Sliding Window Technique Using Python

The sliding window technique is a powerful approach to solve problems involving arrays or lists. It reduces the time complexity for specific types of problems, particularly those that require you to perform operations on contiguous subsets of a list or array.

This article explores how to implement the sliding window technique in Python using lists. We’ll go over various methods with example code and outputs to clearly demonstrate the practical application of the sliding window in Python.

Here’s a simple example to give you an idea of the goal; calculating the sum of consecutive elements:

my_list = [1, 2, 3, 4, 5, 6]
window_size = 3

# Calculate the sum of each sliding window of size 3
for i in range(len(my_list) - window_size + 1):
    window = my_list[i:i+window_size]
    print(f"Window: {window}, Sum: {sum(window)}")

Window: [1, 2, 3], Sum: 6
Window: [2, 3, 4], Sum: 9
Window: [3, 4, 5], Sum: 12
Window: [4, 5, 6], Sum: 15

Method 1: Basic Sliding Window Implementation

This method involves a simple iteration through the list using a fixed window size. We slide the window one element at a time and perform an operation on the elements within the current window.

def sliding_window_sum(nums, k):
    """
    Calculates the sum of each sliding window of size k in the list nums.
    """
    if len(nums) < k:
        return "Window size is larger than the list"

    result = []
    for i in range(len(nums) - k + 1):
        window_sum = sum(nums[i:i+k])
        result.append(window_sum)
    return result

# Example usage
my_list = [1, 2, 3, 4, 5, 6]
window_size = 3
sums = sliding_window_sum(my_list, window_size)
print(f"Sliding window sums: {sums}")

Sliding window sums: [6, 9, 12, 15]

Explanation: The sliding_window_sum function takes a list nums and a window size k as input. It iterates through the list, calculating the sum of each window using list slicing nums[i:i+k]. The resulting sums are stored in the result list and returned.

Method 2: Optimized Sliding Window for Sum Calculation

This method optimizes the sum calculation by updating the sum as the window slides instead of recalculating it each time. This reduces redundant calculations and improves efficiency.

def optimized_sliding_window_sum(nums, k):
    """
    Calculates the sum of each sliding window of size k in the list nums,
    optimizing the sum calculation.
    """
    if len(nums) < k:
        return "Window size is larger than the list"

    result = []
    window_sum = sum(nums[:k])  # Initial window sum
    result.append(window_sum)

    for i in range(len(nums) - k):
        window_sum = window_sum - nums[i] + nums[i+k]  # Update the sum
        result.append(window_sum)
    return result

# Example usage
my_list = [1, 2, 3, 4, 5, 6]
window_size = 3
sums = optimized_sliding_window_sum(my_list, window_size)
print(f"Optimized sliding window sums: {sums}")

Optimized sliding window sums: [6, 9, 12, 15]

Explanation: In this optimized version, we first calculate the sum of the initial window. Then, for each subsequent window, we subtract the element that is leaving the window (nums[i]) and add the element that is entering the window (nums[i+k]). This avoids recalculating the entire sum for each window, significantly improving performance, especially for large lists and window sizes.

Method 3: Sliding Window for Finding Maximum Value

The sliding window technique can also be used to find the maximum value within each window. This requires maintaining the maximum value as the window slides.

def sliding_window_maximum(nums, k):
    """
    Finds the maximum value in each sliding window of size k in the list nums.
    """
    if len(nums) < k:
        return "Window size is larger than the list"

    result = []
    for i in range(len(nums) - k + 1):
        window = nums[i:i+k]
        max_value = max(window)
        result.append(max_value)
    return result

# Example usage
my_list = [1, 3, -1, -3, 5, 3, 6, 7]
window_size = 3
max_values = sliding_window_maximum(my_list, window_size)
print(f"Sliding window maximums: {max_values}")

Sliding window maximums: [3, 3, 5, 5, 6, 7]

Explanation: This code iterates through the list and finds the maximum value within each sliding window using the built-in max() function. The maximum value for each window is then added to the result list.

Method 4: Sliding Window with Deque for Maximum Value (Optimized)

Using a deque (double-ended queue) can further optimize finding the maximum value in each sliding window. The deque helps maintain a sorted (decreasing order) list of indices of potential maximum elements within the window. This allows for O(1) retrieval of the maximum value.

from collections import deque

def sliding_window_maximum_deque(nums, k):
    """
    Finds the maximum value in each sliding window of size k in the list nums,
    using a deque for optimization.
    """
    if not nums:
        return []
    if k > len(nums):
        return [max(nums)]

    result = []
    deque_indices = deque()

    for i in range(len(nums)):
        # Remove elements outside the window
        while deque_indices and deque_indices[0] <= i - k:
            deque_indices.popleft()

        # Remove elements smaller than the current element from the deque
        while deque_indices and nums[deque_indices[-1]] <= nums[i]:
            deque_indices.pop()

        deque_indices.append(i)

        # Add the maximum value of the current window to the result
        if i >= k - 1:
            result.append(nums[deque_indices[0]])

    return result

# Example usage
my_list = [1, 3, -1, -3, 5, 3, 6, 7]
window_size = 3
max_values = sliding_window_maximum_deque(my_list, window_size)
print(f"Optimized sliding window maximums (deque): {max_values}")

Optimized sliding window maximums (deque): [3, 3, 5, 5, 6, 7]

Explanation:

1. We initialize a deque called deque_indices to store indices of elements within the current window.
2. For each element in the list, we first remove any indices from the front of the deque that are outside the current window (deque_indices[0] <= i - k).
3. Then, we remove any indices from the back of the deque whose corresponding elements are smaller than the current element (nums[deque_indices[-1]] <= nums[i]). This ensures that the deque maintains a decreasing order of element values.
4. We append the index of the current element to the deque.
5. Finally, if the current index is at least k - 1, we append the maximum value of the current window (nums[deque_indices[0]]) to the result list.

This optimization reduces the time complexity to O(n), where n is the length of the list.

Method 5: Sliding Window for Finding the Longest Substring

The sliding window technique can also be used for string-related problems such as finding the longest substring with certain properties. Here we find the longest substring with at most `k` distinct characters.

def longest_substring_with_k_distinct_characters(s, k):
    """
    Finds the longest substring with at most k distinct characters.
    """
    if not s or k == 0:
        return ""

    start = 0
    max_length = 0
    max_substring = ""
    char_frequency = {}

    for end in range(len(s)):
        right_char = s[end]
        if right_char not in char_frequency:
            char_frequency[right_char] = 0
        char_frequency[right_char] += 1

        while len(char_frequency) > k:
            left_char = s[start]
            char_frequency[left_char] -= 1
            if char_frequency[left_char] == 0:
                del char_frequency[left_char]
            start += 1

        if end - start + 1 > max_length:
            max_length = end - start + 1
            max_substring = s[start:end + 1]

    return max_substring

# Example Usage
input_string = "araaci"
k_distinct = 2
result = longest_substring_with_k_distinct_characters(input_string, k_distinct)
print(f"Longest substring with {k_distinct} distinct characters: {result}")

input_string = "cbbebi"
k_distinct = 3
result = longest_substring_with_k_distinct_characters(input_string, k_distinct)
print(f"Longest substring with {k_distinct} distinct characters: {result}")

Longest substring with 2 distinct characters: araa
Longest substring with 3 distinct characters: cbbeb

Explanation:

1. We use a dictionary char_frequency to keep track of the frequency of characters in the current window.
2. The start pointer marks the beginning of the window, and the end pointer iterates through the string.
3. We expand the window by adding the character at the end pointer to the char_frequency.
4. If the number of distinct characters in the char_frequency exceeds k, we shrink the window from the left by incrementing the start pointer until the number of distinct characters is at most k.
5. During the window expansion, we keep track of the maximum length and the corresponding substring.

This code finds the longest substring containing at most k distinct characters by adjusting the window's start and end points based on the distinct character count.