Originally published on Medium.
In the realm of algorithmic problem-solving, the Sliding Window technique stands out for its efficiency and elegance, especially in handling array or list-related challenges. This approach is particularly useful when dealing with problems that require examining a subset of elements in a sequence. In this article, we’ll delve into the Sliding Window pattern, exploring its concept through five practical coding examples in Python.
The Sliding Window technique involves creating a ‘window’ over a portion of the data structure (like an array or a list) and then moving that window throughout the data to capture different subsets of elements. This method is highly effective for problems requiring the analysis of contiguous sequences of data within a larger set. Imagine you have a row of toys, and you’re only allowed to look at a few at a time through a cardboard tube (your “window”). You slide this tube along the row to see different sets of toys.
Example 1: Maximum Sum Subarray of Size K
def max_sum_subarray_of_size_k(nums, k):
max_sum, window_sum, window_start = 0, 0, 0
for window_end in range(len(nums)):
window_sum += nums[window_end] # Add the next element
# Slide the window, no need to slide if we've not hit the required window size of 'k'
if window_end >= k - 1:
max_sum = max(max_sum, window_sum)
window_sum -= nums[window_start] # Subtract the element going out
window_start += 1 # Slide the window ahead
return max_sum
The “sliding window” technique demonstrated in the code efficiently finds the maximum sum of any contiguous subarray of size `k` within an array `nums`. It initializes variables to track the current window’s sum (`window_sum`), the maximum sum found (`max_sum`), and the starting index of the current window (`window_start`). The algorithm iterates through `nums`, expanding the window by adding new elements to `window_sum` and checking if the window has reached the desired size `k`. If it has, the algorithm potentially updates `max_sum` with the current `window_sum`, then slides the window forward by one element, both by removing the element at the start of the window from `window_sum` and incrementing `window_start`. Finally, the algorithm returns `max_sum`, representing the largest sum found in any `k`-sized subarray within `nums`.
Example 2: Finding the longest substring with at most two distinct characters
def smallest_subarray_with_given_sum (s, arr):
window_start, window_sum = 0, 0
min_length = float('inf')
for window_end in range(len(arr)):
window_sum += arr[window_end]
while window_sum > s and window_start <= window_end:
window_sum -= arr[window_start]
window_start += 1
if window_sum == s:
min_length = min(min_length, window_end - window_start + 1)
window_sum -= arr[window_start]
window_start += 1
return min_length if min_length != float('inf') else 0
The code employs the “sliding window” technique to determine the length of the smallest subarray within an array `arr` whose sum exactly equals a specified value `s`. It initializes variables to keep track of the current window’s sum (`window_sum`), the smallest subarray length found (`min_length`), and the starting index of the current window (`window_start`). As the algorithm iterates through `arr`, it expands the window by adding elements to `window_sum`. If `window_sum` exceeds `s`, the algorithm shrinks the window from the beginning, updating `window_sum` by subtracting the outgoing elements, until `window_sum` is no longer greater than `s`. When `window_sum` equals `s`, the algorithm updates `min_length` with the size of the current window, if it’s smaller than previously found lengths, and then moves the window forward by one element to search for other potential subarrays. Ultimately, the algorithm returns `min_length`, which reflects the length of the smallest contiguous subarray summing to `s`, or 0 if no such subarray exists. This method is particularly useful in identifying the most compact sequence within an array that meets a precise sum requirement.
Example 3: Longest Substring with Maximum K Distinct Characters
def longest_substring_with_k_distinct(s,k):
window_start, max_length = 0, 0
char_index_map = {}
for window_end in range(len(s)):
right_char = s[window_end]
char_index_map[right_char] = window_end
if(len(char_index_map) > k):
left_char_index = min(char_index_map.values())
del char_index_map[s[left_char_index]]
window_start = left_char_index + 1
max_length = max(max_length, window_end - window_start + 1)
return max_length
In this solution, we use the “sliding window” technique to identify the longest substring containing at most K distinct characters in a given string. We track each character’s latest position using a dictionary and adjust the window’s boundaries accordingly. If the window contains more than K distinct characters, we reduce it from the left, removing the earliest occurring character. This continues until the entire string is examined, ensuring the identification of the longest valid substring. This method is both efficient and straightforward, effectively addressing this typical string manipulation challenge.