Sliding Window for Subarray Problems

Concept 1: The Core Idea of the Sliding Window

The sliding window pattern is an algorithmic technique used for problems that ask for something about a contiguous subarray or substring (e.g., the longest, shortest, or one that satisfies a certain property).

Technical Explanation

At its heart, the sliding window pattern is about transforming a brute-force approach that uses nested loops into a single-pass approach. Instead of re-computing values for every possible subarray, we maintain a "window" (a subarray defined by a start and end pointer) and slide it across the data. As the window slides, we efficiently update our state by adding the new element that enters the window and removing the old element that leaves it. This avoids redundant calculations and typically reduces time complexity from $O(N^2)$ or $O(N\cdot K)$ down to $O(N)$.

Problems solvable with this pattern usually involve keywords like "subarray," "substring," "contiguous," "longest," "shortest," or finding a "maximum/minimum" within a certain range.

Metaphor: The Buffet Plate

As described in the "Mastering the Sliding Window Technique" article, imagine you're at a buffet with a plate that can only hold a certain number of items. You move along the buffet line, adding new food items to your plate while removing others to make space. The collection of food on your plate at any given moment is your "window." Instead of emptying your plate and starting over at every step, you intelligently swap items as you move. This is far more efficient.

Concept 2: Fixed-Length Sliding Window

The simplest form of the pattern is when the window size is fixed. The problem will explicitly give you a size, often denoted as k.

Technical Explanation

The process for a fixed-length window is straightforward:

1. Build the initial window: Compute the value (e.g., sum, average) for the first k elements. This is your initial state.
2. Slide and update: Iterate from the k-th element to the end of the array. In each iteration:
   • Add the new element entering the window (at index i).
   • Remove the element leaving the window (at index i-k).
   • Update your result (e.g., check for a new maximum sum).

This technique ensures you only perform two operations per step (one addition, one subtraction) instead of re-calculating the sum of k elements each time.

Metaphor: The Cardboard Viewfinder

Imagine you have a long panoramic photograph and a cardboard cutout with a fixed-width rectangular hole in it. To inspect the photo, you place the cutout over the start of the image (your initial window). Then, you slide it smoothly to the right, one inch at a time. With each slide, you see a new inch of the photo on the right, while an inch on the left disappears from view. Your view is always the same fixed width.

Python Code Snippet: Maximum Average Subarray

Let's solve a classic problem: Given an array and an integer k, find the maximum average of all contiguous subarrays of size k.

Here's the implementation, reflecting the logic from the video:

from typing import List

def findMaxAverage(nums: List[int], k: int) -> float:
    """
    Finds the maximum average of a subarray of size k.
    This demonstrates a fixed-length sliding window.
    Time Complexity: O(N)
    Space Complexity: O(1)
    """
    
    # 1. Build the initial window sum
    current_sum = sum(nums[:k])
    max_sum = current_sum
    
    # 2. Slide the window from k to the end of the array
    for i in range(k, len(nums)):
        # Add the new element entering the window
        # and remove the element leaving the window
        current_sum += nums[i] - nums[i - k]
        
        # Update the maximum sum found so far
        max_sum = max(max_sum, current_sum)
        
    # The maximum average is the maximum sum divided by k
    return max_sum / k

# Example from the video
nums = [1, 12, -5, -6, 50, 3]
k = 4
print(f"The maximum average is: {findMaxAverage(nums, k)}") # Expected: 12.75

Concept 3: Variable-Length Sliding Window

This is the more dynamic and common variant. Here, the window grows and shrinks based on a certain constraint. The goal is often to find the longest or shortest subarray that satisfies the condition.

Technical Explanation

This pattern uses two pointers, start and end, which define the current window.

1. Expand: The end pointer always moves to the right, expanding the window one element at a time.
2. Check Constraint: After adding a new element, check if the window is still valid according to the problem's constraint (e.g., "contains no repeating characters").
3. Contract: If the window becomes invalid, move the start pointer to the right, shrinking the window from the left until it becomes valid again.
4. Update Result: Usually, you update your answer (e.g., max_length) right after the expansion phase, when the window is valid.

Metaphor: The Elastic Ruler

You have an elastic ruler that you're laying over a sequence of numbers. You start with the ruler collapsed at the beginning. You stretch the end of the ruler (end pointer) to the right, covering more numbers. At some point, you might violate a rule (e.g., "the numbers covered cannot sum to more than 100"). When that happens, you must contract the ruler from its start (start pointer) until the rule is satisfied again. You keep track of the longest valid length the ruler ever reached.

Python Code Snippet: Longest Substring Without Repeating Characters

This is a quintessential interview problem. Given a string, find the length of the longest substring without any repeating characters.

The code below implements this logic. Notice the for loop for the end pointer (expansion) and the nested while loop for the start pointer (contraction).

def lengthOfLongestSubstring(s: str) -> int:
    """
    Finds the length of the longest substring without repeating characters.
    This demonstrates a variable-length sliding window.
    Time Complexity: O(N) - each character is visited by start and end pointers at most once.
    Space Complexity: O(K) - where K is the number of unique characters in the alphabet.
    """
    char_set = set()
    start = 0
    max_length = 0
    
    for end in range(len(s)):
        # Contract phase: if the new character is already in our window,
        # shrink the window from the left until the duplicate is removed.
        while s[end] in char_set:
            char_set.remove(s[start])
            start += 1
            
        # Expand phase: add the new character to our window.
        char_set.add(s[end])
        
        # Update result: calculate the length of the current valid window.
        max_length = max(max_length, end - start + 1)
        
    return max_length

# Example from the video
s = "abcabcbb"
print(f"The length of the longest substring is: {lengthOfLongestSubstring(s)}") # Expected: 3

Concept 4: The Generic Sliding Window Template

Most variable-length sliding window problems can be solved using a generic template. Understanding this template is key to recognizing and solving these problems quickly in an interview.

Technical Explanation

The core structure is almost always the same. You just need to plug in the specific logic for your problem's constraints.

Here's the generalized Python template:

def sliding_window_template(arr, k): # k is an example parameter for a constraint
    start = 0
    result = 0
    
    # Define a data structure to maintain the state of the window
    window_state = {} # e.g., a hash map for counts, a set for existence

    for end in range(len(arr)):
        # 1. EXPAND the window by adding the right element
        # Update window_state with arr[end]
        
        # 2. CONTRACT the window if the constraint is violated
        while constraint_is_violated(window_state, k):
            # Update window_state by removing arr[start]
            start += 1
            
        # 3. UPDATE the result after ensuring the window is valid
        # result = max(result, end - start + 1) or some other calculation
        
    return result

# Helper function to be defined based on the problem
def constraint_is_violated(window_state, k):
    # e.g., for "longest substring with at most k distinct characters"
    # return len(window_state) > k
    pass

This template embodies the core logic: expand, check, contract. By internalizing this, you can focus on defining the window_state and the constraint_is_violated condition, which is the heart of any specific problem.

Concept 5: Advanced Application - Sliding Window Maximum

What if the problem requires finding the maximum value within each sliding window of a fixed size k? A naive approach would be to re-scan each window, leading to an $O(N\cdot K)$ complexity. We can do better.

Technical Explanation

To achieve $O(N)$ time, we need a way to find the maximum of the current window in $O(1)$ time. This is a perfect use case for a double-ended queue (deque). The deque will not store the elements themselves, but their indices. We will maintain a special property: the deque will always store indices in decreasing order of their corresponding values in the array. This is called a monotonic queue.

The logic is as follows:

1. Deque Maintenance (Monotonicity): Before adding a new element's index to the deque, we remove all indices from the end of the deque that correspond to values smaller than the new element's value. This ensures the decreasing-value property is maintained.
2. Window Boundary: Before adding a new index, we check if the index at the front of the deque has fallen out of the current window's left boundary. If it has, we remove it.
3. Maximum Element: Because of the monotonic property, the index at the front of the deque always corresponds to the maximum element in the current window.

Metaphor: The "Tallest in Line" Audition

Imagine a line of people auditioning to be the "tallest person in the current group of 3".

• A new person (end pointer) is about to join the line. Before they do, they look at the people already in line, starting from the back. They tell everyone shorter than them to leave, because those people can never be the tallest as long as the new, taller person is around.
• The new person then joins the back of the line.
• The judge checks if the person at the very front of the line has been waiting too long (i.e., has slid out of the window of 3). If so, that person leaves.
• The person currently at the front of the line is always the tallest in the current group.

Python Code Snippet: Sliding Window Maximum

This is a hard-level interview question, and the deque solution is the optimal one expected.

import collections

def maxSlidingWindow(nums: List[int], k: int) -> List[int]:
    """
    Finds the maximum value in each sliding window of size k.
    This demonstrates an advanced sliding window with a deque.
    Time Complexity: O(N) - each element is added/removed from deque once.
    Space Complexity: O(K) - deque stores at most k elements.
    """
    output = []
    q = collections.deque()  # Stores indices
    
    for i in range(len(nums)):
        # 1. Remove indices from the front that are out of the window's bounds
        if q and q[0] == i - k:
            q.popleft()
            
        # 2. Maintain monotonic decreasing property.
        # Remove indices from the back that correspond to smaller elements.
        while q and nums[q[-1]] < nums[i]:
            q.pop()
            
        q.append(i)
        
        # 3. The front of the queue is the max of the current window.
        # Add to output once the window is at least size k.
        if i >= k - 1:
            output.append(nums[q[0]])
            
    return output

# Example
nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
print(f"Sliding window maximums: {maxSlidingWindow(nums, k)}") # Expected: [3, 3, 5, 5, 6, 7]

Conclusion

Today you mastered the sliding window, a vital pattern for optimizing solutions from quadratic to linear time. This is a huge leap in efficiency and something that interviewers at top tech companies specifically look for.

Key Takeaways:

• Sliding Window Pattern: Reduces nested loops to a single pass for problems on contiguous subarrays/substrings.
• Fixed-Length Window: The simplest variant, where you slide a window of a constant size k by adding one new element and removing one old element per step.
• Variable-Length Window: A more common pattern using start and end pointers. The window expands with end and contracts with start to maintain a specific constraint.
• The Template: The expand -> check constraint -> contract loop is a powerful, reusable template for solving most variable-length window problems.
• Advanced Use with Deques: For problems like finding the maximum in each window, a deque can be used to maintain a monotonic queue, allowing for $O(1)$ lookups of the window's max/min and an overall $O(N)$ solution.

Preview of the Next Lesson

The sliding window pattern uses two pointers to define the boundaries of a sub-array. In our next lesson, we will explore the Two-Pointer Technique more broadly. We'll see how two pointers can be used in other powerful ways, such as moving towards each other from opposite ends of an array, or moving through a list at different speeds (the "fast and slow pointer" method) to solve an entirely different set of problems on arrays and linked lists.