Cracking the Coding Interview: Part 2 – The Sliding Window Pattern

In this second part of our series, we dive into one of the most versatile patterns for solving coding interview questions: the Sliding Window. This technique is incredibly useful for optimizing problems involving subarrays or substrings of contiguous elements, such as maximizing sums, finding specific conditions within a sequence, or working with substrings in strings.

Before we dive in, if you’re serious about preparing for coding interviews, I highly recommend checking out this article on the Top 10 Essential Books for Cracking Coding Interviews (Ranked from Beginner to Advanced). It includes key resources like Cracking the Coding Interview that are perfect for building the skills you need to succeed in technical interviews.

Overview of the Sliding Window Pattern

The Sliding Window pattern is a technique that allows you to efficiently solve problems where you need to consider a subset of data from a larger dataset (like a subarray of an array or a substring of a string). Instead of recalculating the subset every time you move the window, this technique maintains a running total or condition, sliding across the data to minimize unnecessary work.

When to Use Sliding Window:

• The problem involves contiguous subarrays or substrings.
• You need to find the maximum or minimum sum, count, or other conditions within a sliding range of the dataset.
• It involves a fixed window size or requires a dynamic window that expands or shrinks.

---

Types of Sliding Window Approaches

1. Fixed Size Sliding Window

• What it is: A window of a fixed size that slides across the array or string while maintaining a running condition like sum or product.
• Example: Find the maximum sum of a subarray of size k.

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

def max_sum_subarray(arr, k):
    # Initialize variables to store the maximum sum and the current window sum.
    max_sum = 0
    window_sum = 0

    # First, calculate the sum of the initial window (first 'k' elements).
    for i in range(k):
        window_sum += arr[i]

    # Set the max_sum to the initial window's sum.
    max_sum = window_sum

    # Now, slide the window across the array. 
    # Start from the kth element and move until the end of the array.
    for i in range(k, len(arr)):
        # Slide the window by subtracting the element that is no longer in the window 
        # (arr[i - k]) and adding the new element (arr[i]).
        window_sum += arr[i] - arr[i - k]

        # Update max_sum if the current window sum is greater than the previous max_sum.
        max_sum = max(max_sum, window_sum)

    # Return the maximum sum found.
    return max_sum

Explanation:

• A window of size k is initialized.
• As the window moves across the array, the sliding effect is achieved by subtracting the element that is no longer in the window and adding the new element that enters the window.
• This optimizes the problem from a brute force approach of O(n*k) to O(n), as we no longer need to sum up the entire window for each iteration.

---

2. Dynamic Sliding Window

• What it is: This is used when the window size is not fixed. The window expands or contracts based on the problem’s requirements (like satisfying a sum or condition).
• Example: Find the smallest subarray with a sum greater than or equal to S.

Example Problem: Given an array of integers and a number S, find the smallest contiguous subarray whose sum is greater than or equal to S.

  def smallest_subarray_with_sum(arr, S):
    # Initialize variables:
    # window_sum: to store the sum of the current window.
    # min_length: to store the length of the smallest subarray found.
    # window_start: the starting index of the sliding window.
    window_sum = 0
    min_length = float('inf')  # Start with a large number to compare minimum lengths.
    window_start = 0

    # Iterate over the array with window_end being the right boundary of the window.
    for window_end in range(len(arr)):
        # Add the current element to the window_sum.
        window_sum += arr[window_end]

        # While the current window's sum is greater than or equal to S:
        while window_sum >= S:
            # Calculate the current window size and update min_length if smaller.
            min_length = min(min_length, window_end - window_start + 1)

            # Shrink the window from the left by removing the element at window_start.
            window_sum -= arr[window_start]

            # Move the start of the window to the right.
            window_start += 1

    # If min_length was updated, return it; otherwise, return 0 (meaning no valid subarray was found).
    return min_length if min_length != float('inf') else 0

Explanation:

• The window expands by increasing window_end until the sum exceeds or equals S.
• Once the condition is satisfied, the window starts contracting from the left (window_start) to find the minimum subarray size.
• This approach is efficient because it reduces the problem from O(n^2) to O(n), by avoiding recomputations.

---

Steps to Implement Sliding Window Solutions

1. Define the window boundaries: You need to define the start and end of the window.

2. Set an initial condition: For fixed windows, initialize the sum/product/condition for the first window. For dynamic windows, the initial condition depends on the problem’s goal.

3. Slide the window:

   • For fixed window size: Shift the window by adding the next element and removing the element that is no longer in the window.
   • For dynamic windows: Expand or contract the window based on the condition you’re trying to satisfy.

4. Check and update results: After each window movement, update the result (such as maximum sum, minimum length, etc.) as necessary.

---

Common Interview Questions Using Sliding Window

1. Longest Substring Without Repeating Characters

   • Problem: Given a string s, find the length of the longest substring without repeating characters.
   • Pattern: Use a dynamic sliding window to expand until a duplicate character is found, then contract the window until the condition is satisfied.

2. Maximum Sum Subarray of Size K

   • Problem: Given an array of integers and an integer k, find the maximum sum of any subarray of size k.
   • Pattern: Use a fixed size sliding window to maintain the sum of k elements and update the maximum sum as you slide the window across the array.

3. Smallest Subarray with a Given Sum

   • Problem: Given an array of positive integers and a number S, find the length of the smallest contiguous subarray whose sum is greater than or equal to S.
   • Pattern: Use a dynamic sliding window that expands to find a valid subarray and contracts to minimize its length.

---

Sliding Window Hacks for Interviews

1. Think in terms of the window boundaries: Start by thinking about where the window should start and end. This helps you identify the exact range you're working with.

2. Use a hashmap or set for dynamic windows: When dealing with substrings or unique elements, use a set to track the elements in the window.

3. Start with brute-force and then optimize: In some problems, starting with a brute-force approach (like checking every possible subarray) can help you visualize how a sliding window would reduce unnecessary work.

4. Look for optimal conditions: If the problem has an optimization component (like minimizing or maximizing a sum or length), sliding window may be a good fit.

---

Conclusion

The Sliding Window pattern is a powerful tool for solving many coding interview problems, especially those involving sequences like arrays or strings. By mastering both fixed-size and dynamic sliding windows, you can tackle a wide range of problems more efficiently.

In the next article, we’ll explore the Two Pointer Technique, another highly effective strategy that often complements the sliding window approach in problems that involve pairs or comparisons between elements.

Stay tuned for Part 3!