What is Sliding Window Algorithm? Examples?

Sliding Window Algorithm: An Efficient Approach to Subarray Problems

Explore the Sliding Window algorithm, a powerful technique for efficiently solving problems that involve finding subarrays or substrings with specific properties. Learn its core concept, advantages, and practical applications with examples.

The Sliding Window algorithm is a technique used to solve problems that require finding subarrays or substrings in a data set (like an array or string) that satisfy a certain condition. Instead of re-evaluating each subarray from scratch, which can be inefficient, the sliding window approach maintains a 'window' of elements that 'slides' over the data, adding new elements and removing old ones, thus optimizing computations.

Core Concept of Sliding Window

At its heart, the sliding window algorithm involves two pointers, typically left and right, defining the boundaries of the current window. The right pointer expands the window by including new elements, and the left pointer contracts the window by removing elements from the beginning. This dynamic adjustment ensures that the window always contains elements relevant to the current computation. The key is to perform calculations on the current window and update them incrementally as the window slides, rather than recalculating for every possible subarray.

Visualization of a sliding window moving across an array.

When to Use Sliding Window

The Sliding Window algorithm is particularly effective in problems where you need to find:

• The longest/shortest subarray/substring that meets a condition.
• The number of subarrays/substrings that meet a condition.
• Subarrays/substrings with a specific sum, product, or character frequency.

Example: Maximum Sum Subarray of Fixed Size K

Let's consider a classic problem: given an array of integers and an integer k, find the maximum sum of any contiguous subarray of size k. A brute-force approach would involve iterating through all possible subarrays of size k, calculating their sum, and finding the maximum, leading to O(n*k) time complexity. The sliding window approach can solve this in O(n) time.

Tab 1

First, calculate the sum of the first k elements to initialize the window sum.

Tab 2

Then, iterate from the k-th element to the end of the array.

Tab 3

In each iteration, subtract the element leaving the window (at i - k) and add the new element entering the window (at i).

Tab 4

Update the maximum sum encountered so far.

def max_sum_subarray_fixed_size(arr, k):
    if k > len(arr):
        return 0

    window_sum = sum(arr[:k])
    max_sum = window_sum

    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k] # Slide window
        max_sum = max(max_sum, window_sum)

    return max_sum

# Example usage:
arr = [1, 4, 2, 10, 2, 3, 1, 0, 20]
k = 3
print(f"Maximum sum of subarray of size {k}: {max_sum_subarray_fixed_size(arr, k)}") # Output: 22 (from [10, 2, 3, 1, 0, 20])

Python implementation for finding the maximum sum subarray of a fixed size k.

function maxSumSubarrayFixedSize(arr, k) {
    if (k > arr.length) {
        return 0;
    }

    let windowSum = 0;
    for (let i = 0; i < k; i++) {
        windowSum += arr[i];
    }

    let maxSum = windowSum;

    for (let i = k; i < arr.length; i++) {
        windowSum += arr[i] - arr[i - k]; // Slide window
        maxSum = Math.max(maxSum, windowSum);
    }

    return maxSum;
}

// Example usage:
const arr = [1, 4, 2, 10, 2, 3, 1, 0, 20];
const k = 3;
console.log(`Maximum sum of subarray of size ${k}: ${maxSumSubarrayFixedSize(arr, k)}`); // Output: 22

JavaScript implementation for finding the maximum sum subarray of a fixed size k.

Example: Longest Substring Without Repeating Characters

This is a classic variable-size sliding window problem. Given a string s, find the length of the longest substring without repeating characters. Here, the window size is not fixed; it expands and contracts based on the condition (no repeating characters). We use a hash set to keep track of characters in the current window.

Flowchart for longest substring without repeating characters.

def length_of_longest_substring(s):
    char_set = set()
    left = 0
    max_len = 0

    for right in range(len(s)):
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
        char_set.add(s[right])
        max_len = max(max_len, right - left + 1)
    return max_len

# Example usage:
print(f"Longest substring without repeating characters in 'abcabcbb': {length_of_longest_substring('abcabcbb')}") # Output: 3 ('abc')
print(f"Longest substring without repeating characters in 'bbbbb': {length_of_longest_substring('bbbbb')}")      # Output: 1 ('b')
print(f"Longest substring without repeating characters in 'pwwkew': {length_of_longest_substring('pwwkew')}")      # Output: 3 ('wke')

Python solution for the longest substring without repeating characters.

The Sliding Window algorithm is a versatile and powerful technique that significantly improves the efficiency of many array and string problems. By understanding its core principles and practicing with various problem types, you can effectively apply it to optimize your solutions.