Mastering the Sliding Window Technique in Python

The sliding window technique is a powerful tool for solving problems related to arrays or lists, particularly when dealing with subarrays of a fixed size or when certain conditions need to be met within a subarray. This technique is implemented using two pointers. This post will delve into the sliding window algorithm, its implementation, and why it is efficient in terms of time and space complexity.

What is a Subarray?

Before we start discussing sliding window let's see what is a subarray. A subarray is a contiguous portion of an array. A subarray can be defined by two indices, the start and end. In other words, it is a sequence of elements within an array that are adjacent to each other and maintain their order as they appear in the original array. For example, consider the array [1, 2, 3, 4]. Some subarrays of this array include:

• [1], [2], [3], [4]

• [1, 2], [2, 3], [3, 4]

• [1, 2, 3], [2, 3, 4]
  

• [1, 2, 3, 4]

Subarrays are often used in problems where the goal is to find specific properties or conditions within contiguous elements of an array. The sliding window technique leverages this concept to efficiently solve such problems by dynamically adjusting the window of elements being considered.

What is the Meaning of a Window and Sliding in the Sliding Window Technique in Python?

In the context of the sliding window algorithm, the terms "window" and "sliding" have specific meanings:

Window

A window refers to a subset of elements within the array that is being examined or processed at any given time. This subset is contiguous, meaning all elements within the window are adjacent to each other in the array. The size of the window can be fixed or variable, depending on the problem requirements.

For example, if we have an array [1, 3, 5, 7, 9] and we are examining subarrays of size 3, then [1, 3, 5] is one such window.

Sliding

Sliding refers to the process of moving the window across the array to consider different subsets of elements. Instead of recalculating the properties of the entire subarray from scratch for each new position of the window, the algorithm updates the properties incrementally as the window moves.

For example, given the same array [1, 3, 5, 7, 9] and a window of size 3, if our initial window is [1, 3, 5], sliding the window to the right by one position would give us [3, 5, 7]. The sliding process involves:

1. Adding the new element that comes into the window (7 in this case).

2. Removing the element that goes out of the window (1 in this case).

This incremental adjustment makes the sliding window technique efficient by reducing redundant calculations, thus optimizing the algorithm's performance.

When Should We Use Sliding Window ?

The sliding window technique is particularly useful when:

1. We need to find a subarray of fixed size or variable size that meets certain conditions like a constant metric involved.

2. Problems involve contiguous subarrays.

3. We want to optimize time complexity from O(n^2) to O(n).

Common problems where sliding window is used include finding the maximum or minimum sum of a subarray of size k, finding the longest subarray with a sum equal to k, and more.

The Algorithm

The sliding window algorithm typically involves maintaining a window that slides over the input data to maintain the current subarray or subset of elements that meet the criteria. The window is adjusted dynamically based on the conditions specified in the problem.

General Explanation of the Sliding Window Code

def fn(arr):
    left = 0
    for right in range(len(arr)):
        # Do some logic to "add" element at arr[right] to the window

        while WINDOW_IS_INVALID:
            # Do some logic to "remove" element at arr[left] from the window
            left += 1

        # Do some logic to update the answer

Explanation

Initialization: We start by initializing left to 0. The left pointer represents the start of the window.

Expanding the Window: We use a for loop to iterate through the array with the right pointer, which represents the end of the window. For each iteration, we add the element at arr[right] to the current window. This step involves performing some logic to incorporate the new element into the window's current state or sum.

Shrinking the Window: While the current window does not meet the required conditions (i.e., WINDOW_IS_INVALID), we need to adjust the window by removing elements from the left. This involves: Performing some logic to remove the element at arr[left] from the window. Incrementing the left pointer to shrink the window from the left side. This step ensures that the window only contains elements that satisfy the given condition.

Updating the Answer: After adjusting the window, we perform some logic to update the answer. This typically involves checking if the current window is the best solution found so far (e.g., longest subarray, maximum sum, etc.).

Why Is Sliding Window Efficient ?

The sliding window technique is highly efficient because it reduces the time complexity of problems involving subarrays from O(n^2) to O(n). To understand this, we need to delve into the concept of amortized analysis.

Time Complexity: O(n^2) vs. O(n)

In a naive approach, you might consider all possible subarrays to solve a problem, leading to a time complexity of O(n^2). This is because for each element, you might iterate through the remaining elements to calculate sums or check conditions, resulting in nested loops.

The sliding window technique, however, avoids this redundancy by dynamically adjusting a single window that moves across the array. Instead of re-calculating properties of the subarray from scratch, it updates these properties incrementally.

Amortized Analysis

Amortized analysis is a technique used in computer science to analyze the time complexity of algorithms. It provides an average time per operation over a sequence of operations, ensuring that the average is low even if some operations are costly. The idea is to spread out the high cost of expensive operations over many cheaper ones, giving a more realistic measure of an algorithm's performance.

In the above graph:

1. X-Axis (Operations): This axis represents the sequence of operations performed by the algorithm.

2. Y-Axis (Cost): This axis indicates the cost associated with each operation.
   

3. Cost per Operation: This line shows the actual cost of each operation. Notice how some operations have low costs (e.g., 1 or 2) while others have very high costs (e.g., 10). The fluctuation in costs reflects the varying computational effort needed for different operations.
   

4. Amortized Cost : This line represents the average cost per operation up to that point in the sequence. It is calculated by summing the costs of all operations performed so far and dividing by the number of operations.

Understanding Amortized Analysis:

• In the sequence, we see some operations have high costs (spikes) while others are low. If we were to look only at the worst-case costs (the spikes), it might seem like the algorithm is inefficient.

• However, amortized analysis smooths out these spikes by averaging the costs over all operations. This average (amortized cost) line is more stable and shows that, on average, each operation is inexpensive, even though some operations are costly.

Amortized analysis helps us understand the average time complexity of an algorithm over a sequence of operations, even if some individual operations might take longer. In the case of the sliding window:

1. Expansion of the Window: The right pointer iterates through each element exactly once, contributing to O(n) operations.
   

2. Shrinking of the Window: The left pointer also moves from the beginning to the end of the array, but each element is considered for removal only once.
   

Although the left pointer might move multiple steps in a single iteration of the outer loop, the total number of movements of left over the entire algorithm is bounded by n. This ensures that each element is added and removed from the window at most once.

Combining the Operations

When we combine the operations of both right and left pointers, we see that each pointer moves a total of n steps. Hence, the overall time complexity is O(n).

Problem 1 : Finding the Longest Subarray with Sum <= k

Given an array of positive integers nums and an integer k, the task is to find the length of the longest subarray whose sum is less than or equal to k. This is a common problem where the sliding window technique can be efficiently applied to achieve an optimal solution.

Problem Statement

Input:

• An array of positive integers nums.

• An integer k.
  

Output:

• The length of the longest subarray with a sum is less than or equal to k.

nums = [1, 2, 3, 4, 5]
k = 7

In this example, the longest subarray with a sum less than or equal to 7 is [1,2,3] 

Step	Array	Start	End	Current Sum	Max Length	Action
1	[1,2,3,4,5]	0	0	1	1	Add 1 to current sum
2	[1,2,3,4,5]	0	1	3	2	Add 2 to current sum
3	[1,2,3,4,5]	0	2	6	3	Add 3 to current sum
4	[1,2,3,4,5]	0	3	10	3	Exceeds k, adjust start
	[1,2,3,4,5]	1	3	9	3	Subtract 1 from current sum
	[1,2,3,4,5]	2	3	7	2	Subtract 2 from current sum
5	[1,2,3,4,5]	2	4	12	2	Add 5 to current sum
	[1,2,3,4,5]	3	4	9	2	Exceeds k, adjust start
	[1,2,3,4,5]	4	4	5	2	Subtract 4 from current sum

Using Sliding Window to Solve the Problem

The sliding window technique is well-suited for this problem because it allows us to efficiently manage the sum of the subarray as the window moves through the array.

Here's how we can solve this problem step-by-step using the sliding window approach:

Initialize Pointers and Variables:

• left pointer to mark the start of the window.

• curr_sum to keep track of the current sum of the window.

• max_length to store the maximum length of the subarray found. Expand the Window:

• Iterate through the array with the right pointer.

• Add the element at nums[right] to curr_sum. Shrink the Window:

• If curr_sum exceeds k, move the left pointer to the right, subtracting nums[left] from curr_sum until curr_sum is less than or equal to k. Update the Maximum Length:

• After adjusting the window, update max_length with the length of the current valid subarray.
  

def longest_subarray(nums, k):
    left = 0
    curr_sum = 0
    max_length = 0

    for right in range(len(nums)):
        curr_sum += nums[right]
        
        while curr_sum > k:
            curr_sum -= nums[left]
            left += 1
        
        max_length = max(max_length, right - left + 1)
    
    return max_length

# Example usage
nums = [1, 2, 3, 4, 5]
k = 7
print(longest_subarray(nums, k))  # Output: 3

Explanation:

• Initialization: We start with left at 0, curr_sum at 0, and max_length at 0.

• Expanding the Window: For each element in nums, add it to curr_sum.

• Shrinking the Window: If curr_sum exceeds k, increment left and adjust curr_sum until it is equal to k.

• Updating the Maximum Length: Continuously update max_length with the length of the current valid subarray.
  

Problem 2 : Longest Substring with One Flip

Given a binary string s (a string containing only "0" and "1"), you may choose to flip at most one "0" to "1". The task is to find the length of the longest substring that contains only "1" after performing this flip.

Problem Statement

Input:

• A binary string s.

Output:

• The length of the longest substring that contains only "1" after flipping at most one "0".

Example:

s = "1101100111"

In this example, by flipping the "0" at index 2, the string becomes 1111100111, and the longest substring of "1"s is of length 5.

Step	String	Start/left	End/right	Zero Count	Max Length	Action
1	[1, 1, 0, 1, 0, 0, 1, 1, 0]	0	0	0	1	Increment end
2	[1, 1, 0, 1, 0, 0, 1, 1, 0]	0	1	0	2	Increment end
3	[1, 1, 0, 1, 0, 0, 1, 1, 0]	0	2	1	3	Increment end and zero_count
4	[1, 1, 0, 1, 0, 0, 1, 1, 0]	0	3	1	4	Increment end
..	So on	..	..	..	..	So on
8	[1, 1, 0, 1, 0, 0, 1, 1, 0]	5	7	1	4	Increment end
9	[1, 1, 0, 1, 0, 0, 1, 1, 0]	8	8	1	4	Adjust start, start = 8

Using Sliding Window to Solve the Problem

The sliding window technique is effective for this problem because it allows us to dynamically manage the window of characters while keeping track of the number of "0"s that can be flipped.

Here's how we can solve this problem step-by-step using the sliding window approach:

Initialize Pointers and Variables:

• left pointer to mark the start of the window.

• max_length to store the maximum length of the substring found.

• zeros_count to keep track of the number of "0"s in the current window. Expand the Window:

• Iterate through the string with the right pointer.

• If the character at s[right] is "0", increment zeros_count. Shrink the Window:

• If zeros_count exceeds 1, move the left pointer to the right until zeros_count is 1 or less, decrementing zeros_count as needed. Update the Maximum Length:

• After adjusting the window, update max_length with the length of the current valid substring.

def longest_substring_with_flip(s):
    left = 0
    max_length = 0
    zeros_count = 0

    for right in range(len(s)):
        if s[right] == '0':
            zeros_count += 1
        
        while zeros_count > 1:
            if s[left] == '0':
                zeros_count -= 1
            left += 1
        
        max_length = max(max_length, right - left + 1)
    
    return max_length

# Example usage
s = "1101100111"
print(longest_substring_with_flip(s))  # Output: 5

Explanation:

• Initialization: We start with left at 0, max_length at 0, and zeros_count at 0.

• Expanding the Window: For each character in s, if it is "0", we increment zeros_count.

• Shrinking the Window: If zeros_count exceeds 1, we increment left and adjust zeros_count until it is 1 or less.

• Updating the Maximum Length: Continuously update max_length with the length of the current valid substring.

Note on right - left + 1

In the sliding window technique, the expression right - left + 1 is crucial for calculating the length of the current window. Let's break down what this expression denotes and why it is used.

Understanding right - left + 1

• right: This is the current position of the right pointer, which represents the end of the window.
  

• left: This is the current position of the left pointer, which represents the start of the window.

The length of the current window (subarray or substring) is determined by the number of elements (or characters) between the left and right pointers, inclusive. The expression right - left + 1 accounts for this:

• right - left: This gives the distance between the right and left pointers, but it is zero-indexed.
  

• +1: Adding one adjusts for zero-indexing, ensuring that the count includes both the start (left) and the end (right) elements of the window.

Example

Consider the array [1, 2, 3, 4, 5] with left at index 1 and right at index 3. The subarray within this window is [2, 3, 4].

• right - left: 3 - 1 = 2

• right - left + 1: 2 + 1 = 3
  

Thus, right - left + 1 correctly calculates the length of the subarray as 3.

Why It Matters

In problems involving subarrays or substrings, knowing the length of the current window is often essential for:

• Updating the Answer: When we need to find the maximum or minimum length of a valid subarray/substring.

• Condition Checking: Ensuring the current window satisfies certain conditions (e.g., sum constraints, character counts).
  

By using right - left + 1, we can efficiently determine the size of the window without needing to iterate through its elements, thus maintaining the optimal O(n) time complexity of the sliding window technique.

General Explanation of the Sliding Window Code for Fixed Window Size

The sliding window technique for a fixed window size is a specific variation that focuses on maintaining a window of a constant size k while sliding it across the array. This approach is useful for problems where you need to perform operations on subarrays of a fixed length. Here is a breakdown of the general structure of the code:

def fn(arr, k):
    curr = some data to track the window

    # Build the first window
    for i in range(k):
        # Do something with curr or other variables to build the first window

    ans = # answer variable, probably equal to curr here depending on the problem
    for i in range(k, len(arr)):
        # Add arr[i] to window
        # Remove arr[i - k] from window
        # Update ans

    return ans

Explanation

1. Initialization: curr is initialized to track the current state of the window. This could be the sum of elements, a count of certain values, etc., depending on the problem.
   

2. Build the First Window: We iterate through the first k elements of the array to build the initial window. This involves performing necessary operations on curr or other variables to set up the first window.
   

3. Initialize the Answer: ans is initialized to store the result, which is typically set to the initial value of curr.
   

4. Slide the Window: We iterate from k to the end of the array. For each new element arr[i] that enters the window, we add it to curr. Simultaneously, we remove the element arr[i - k] that exits the window from curr. We then update ans based on the new state of curr.

Problem 3: Finding the Maximum Sum of a Subarray of Fixed Length k

Given an integer array nums and an integer k, the task is to find the sum of the subarray with the largest sum where the length of the subarray is exactly k. This problem can be efficiently solved using the sliding window technique, specifically designed for a fixed window size.

Problem Statement

Input:

• An integer array nums.

• An integer k.
  

Output:

• The sum of the subarray with the largest sum, where the subarray length is k.

Example:

nums = [1, 4, 2, 10, 23, 3, 1, 0, 20]
k = 4

In this example, the subarray with the largest sum of length 4 is [4, 2, 10, 23], which sums to 39.

Using Sliding Window to Solve the Problem

The sliding window technique is effective for this problem because it allows us to calculate the sum of a fixed-size window in linear time by adjusting the sum dynamically as the window slides across the array.

Here's how we can solve this problem step-by-step using the sliding window approach:

Initialize Pointers and Variables:

• curr_sum to keep track of the current sum of the window.

• max_sum to store the maximum sum of any window found. Build the First Window:

• Iterate through the first k elements to calculate the initial sum and store it in curr_sum.

• Initialize max_sum with curr_sum. Slide the Window:

• Iterate from k to the end of the array.

• For each new element nums[i] that enters the window, add it to curr_sum.

• Remove the element nums[i - k] that exits the window from curr_sum.

• Update max_sum if curr_sum is greater than the current max_sum.

def max_sum_subarray(nums, k):
    curr_sum = 0
    # Build the first window
    for i in range(k):
        curr_sum += nums[i]
    max_sum = curr_sum

    # Slide the window
    for i in range(k, len(nums)):
        curr_sum += nums[i] - nums[i - k]
        max_sum = max(max_sum, curr_sum)
    
    return max_sum

# Example usage
nums = [1, 4, 2, 10, 23, 3, 1, 0, 20]
k = 4
print(max_sum_subarray(nums, k))  # Output: 39

Explanation:

• Initialization: curr_sum is initialized to 0.
  

• Build the First Window: The sum of the first k elements is calculated and stored in curr_sum.
  

• Initialize the Answer: max_sum is initialized to curr_sum.
  

• Slide the Window: For each new element nums[i], it is added to curr_sum. The element that exits the window nums[i - k] is subtracted from curr_sum. max_sum is updated to be the maximum of its current value and curr_sum.

Conclusion

The sliding window technique is a versatile and efficient method for solving a wide range of problems involving subarrays or substrings in Python. By dynamically adjusting the window size and leveraging incremental updates, this technique optimizes the time complexity from O(n^2) to O(n), making it a powerful tool for any developer's arsenal. Whether you're working with fixed or variable window sizes, understanding and applying the sliding window approach can significantly enhance your problem-solving skills and algorithmic efficiency.