Sliding Window Techniques

The techniques used in the sliding window are at the core of efficient algorithm design.

More so for solving problems involving arrays, strings, or sequences.

As a seasoned software engineer with years of experience in competitive programming and real-world problem-solving, I’ve used sliding windows to optimize countless solutions.

Let me explain in:-

• simple
• digestible steps
• complete with optimized Python code
• detailed comments, and 
• practical examples.

Whether you’re a beginner or an experienced coder, this guide will help you master sliding windows and apply them effectively.

What Are Sliding Window Techniques?

Sliding window techniques are used to solve problems where you need to analyze a subset of elements in an array or string.

We slide the "window"—a range of elements—through the data. This enables us to identify a range of values that meet a specified requirement, ultimately resulting in the intended answer.

Types of sliding windows:

• 1. Fixed-Size Sliding Window: The window's size is constant.
• 2. Variable-Size Sliding Window: The requirements of the problem determine the dynamic changes in the window's size.

In addition to being effective, the methods decrease complexity in time from O(n²) to O(n).

Fixed-Size Sliding Window: Maximum Sum of a Subarray

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

We’ll use a fixed-size sliding window to compute the maximum sum efficiently.

def max_sum_subarray(arr, k):

   """
   Finds the maximum sum of a subarray of size k.

   Args:
      arr (list): The input array of integers.
      k (int): The size of the subarray.

   Returns:
      int: The maximum sum of any subarray of size k.
   """
   n = len(arr)
   if n < k:
      return -1  # Invalid input

   # Compute the sum of the first window
   window_sum = sum(arr[:k])
   
   max_sum = window_sum

   # Slide the window through the array
   for i in range(k, n):
       window_sum += arr[i] - arr[i - k]  # Add the new element and remove the old one
       max_sum = max(max_sum, window_sum)

   return max_sum

# Example
arr = [1, 4, 2, 10, 2, 3, 1, 0, 20]
k = 4
print(max_sum_subarray(arr, k))  # Output: 24 (Subarray: [10, 2, 3, 1])

What did we do?

• 1. First Setup: Determine the total of the first `k` components.
• 2. Sliding the Window: Subtract the element that is no longer in the window from the window sum and add each new element.
• 3. Update Maximum Sum: Note the highest sum that was reached.

Variable-Size Sliding Window

Let’s explore the variable-size sliding window with the help of an example:-

Smallest Subarray with Sum ≥ Target 

Determine the length of the smallest subarray whose sum is >= to the target given an array of positive integers and a target sum.

We’ll use a variable-size sliding window to adjust the window size dynamically based on the sum.

def smallest_subarray_with_sum_target(arr, target):

   """
   Finds the length of the smallest subarray with a sum is greater than or equal to the target.

   Args:
      arr (list): The input array of positive integers.
      target (int): The target sum.

   Returns:
      int: The length of the smallest subarray or zero if no such subarray exists.
   """
    n = len(arr)
    Initialize with a large value
    min_length = float('inf')  
    Current window sum
    window_sum = 0
    left = 0  # Left pointer of the window

    for right in range(n):
      window_sum += arr[right]  # Expand the window

      while window_sum >= target:
         
         # Update the minimum length
         min_length = min(min_length, right - left + 1)

         # Shrink the window from the left
         window_sum -= arr[left]
         left += 1

   return min_length if min_length != float('inf') else 0


# Example
arr = [2, 3, 1, 2, 4, 3]
target = 7

# Output: 2 (Subarray: [4, 3])
print(smallest_subarray_with_sum_target(arr, target))  

What did we do?

• 1. Initial Setup: Set up variables and pointers to monitor the minimum length and window sum.

• 2. Extend the Window: Until the window sum reaches or surpasses the goal, add elements to it.

• 3. Shrink the Window: Reduce the window size from the left to find the smallest valid subarray.

Advanced Example: Longest Substring Without Repeating Characters

We’ll use a sliding window with a set to track unique characters.

def longest_substring_without_repeating(s):

   """
   Finds the length of the longest substring without repeating characters.

   Args:
      s (str): The input string.

   Returns:
      int: The length of the longest substring without repeating characters.
   """

   char_set = set() # Set to track unique characters
   left = 0  # Left pointer of the window
   max_length = 0 # Maximum length of the substring

   for right in range(len(s)):
      while s[right] in char_set:
          # Shrink the window if a duplicate is found
          char_set.remove(s[left])
          left += 1
      char_set.add(s[right])

      # Expand the window
      max_length = max(max_length, right - left + 1)  # Update the maximum length

    return max_length

# Example
s = "abcabcbb"
print(longest_substring_without_repeating(s)) # Output: 3

What have we done?

• 1. Initial Setup: To track distinct characters in the window, use a set.
• 2. Extend the Window: Include additional characters in the set.
• 3. Shrink the Window: If a duplicate character is detected, remove it from the left.

Why Sliding Windows Are a Game-Changer

Sliding window techniques are incredibly powerful for solving problems efficiently.

Time complexity can often be reduced from O(n²) to O(n) by keeping a window of items and moving it through the data.

Because of this, the sliding-window technique is essential for both real-world applications and coding interviews.

What to Do Next

It’s time to practice! Try solving these problems on platforms like LeetCode or HackerRank:

• 1. Maximum Sum Subarray of Size K (Fixed-Size Window).
• 2. Smallest Subarray with Sum ≥ Target (Variable-Size Window).
• 3. Longest Substring Without Repeating Characters (Advanced Window).

By mastering these techniques, you’ll be well-equipped to tackle a wide range of algorithmic challenges.

Happy coding!