Sliding Window Method

3.1 Definition of the Sliding Window Method.

The Sliding Window Method is a technique used for solving array or string problems by moving a fixed subarray (or substring) across the data to find an optimal solution. This allows you to process elements in a fixed-size window and dynamically adjust the window based on the problem's conditions.

This technique is especially useful for tasks involving sequences of data, like arrays or strings, and helps reduce time complexity compared to more naive approaches.

Key Principles

• Initialize the window: Set the start and end of the window to initial positions.
• Slide the window: Sequentially move the window's boundaries by adding elements on one side and removing elements on the other.
• Process the window: At each step, perform the necessary calculations for the current window.

Time and space complexity of the Sliding Window Method

Time Complexity:

• O(n) — in most cases, since the pointer or window moves linearly across the array, checking each possible window position.

Space Complexity:

• O(1) — if a fixed amount of additional memory is used to store current values.
• O(k) — if it's necessary to store elements inside the current window of size k.

3.2 Finding the Maximum Sum of a Subarray.

Finding the maximum sum of a fixed-size subarray

Task:

Find a fixed-size subarray k with the maximum sum.

Solution:

Use the Sliding Window Method to maintain the current subarray sum and update the maximum sum as the window slides.

Time Complexity: O(n).

Example code in Python:

def max_sum_subarray(arr, k):
    n = len(arr)
    if n < k:
        return -1
            
    window_sum = sum(arr[:k])
    max_sum = window_sum
            
    for i in range(n - k):
        window_sum = window_sum - arr[i] + arr[i + k]
        max_sum = max(max_sum, window_sum)
            
    return max_sum
        
        

3.3 Finding All Anagrams of a Substring in a String

Task:

Find all anagrams of the given substring p in the string s.

Solution:

Use the Sliding Window Method to maintain a frequency dictionary of the current window's characters and compare it with the substring's frequency dictionary.

Time Complexity: O(n).

Example code in Python:

from collections import Counter

def find_anagrams(s, p):
    p_count = Counter(p)
    s_count = Counter()
                
    result = []
    k = len(p)
                
    for i in range(len(s)):
        s_count[s[i]] += 1
        
        if i >= k:
            if s_count[s[i - k]] == 1:
                del s_count[s[i - k]]
            else:
                s_count[s[i - k]] -= 1
                            
        if s_count == p_count:
            result.append(i - k + 1)

    return result
        

3.4 Finding the Minimum Subarray

Finding the minimum subarray with a sum exceeding a given value

Task:

Find the minimum subarray with elements' sum exceeding a given value S.

Solution:

Use the Sliding Window Method to expand the right boundary until the sum exceeds S, then shift the left boundary to minimize the subarray's length.

Time Complexity: O(n).

Example code in Python:

def min_subarray_len(S, arr):
    n = len(arr)
    min_len = float('inf')
    current_sum = 0
    left = 0
            
    for right in range(n):
        current_sum += arr[right]
                
        while current_sum >= S:
            min_len = min(min_len, right - left + 1)
            current_sum -= arr[left]
            left += 1
            
    return 0 if min_len == float('inf') else min_len
        
        

2

Task

Python SELF EN, level 59, lesson 2

Locked

Subarray

Subarray

Open

2

Task

Python SELF EN, level 59, lesson 2

Locked

Large Subarray

Large Subarray

Open