Sliding Window Technique

Generated on 2025-07-10 02:07:28 Algorithm Cheatsheet for Technical Interviews

---

Sliding Window Technique - Cheat Sheet

1. Quick Overview

The Sliding Window technique is an algorithm design paradigm used to reduce the time complexity of certain problems involving arrays, strings, or linked lists. It works by maintaining a “window” of elements that slides across the input data. It’s particularly useful when you need to perform an operation on all contiguous subarrays/substrings of a specific size.

When to Use:

• Problems requiring finding the maximum/minimum sum/average/length of a contiguous subarray/substring.
• Problems involving finding a subarray/substring that satisfies a certain condition.
• When a brute-force approach would be O(n^2) or higher.

2. Time & Space Complexity

• Time Complexity: Typically O(n), where n is the size of the input. The window slides across the entire input once.
• Space Complexity: O(1) in most cases, as it usually only involves a fixed number of variables. However, some variations might require O(k) space, where k is the size of the window.

3. Implementation

Here’s a basic implementation of the sliding window technique, finding the maximum sum of a subarray of size k:

Python:

def max_subarray_sum(arr, k):
    """
    Finds the maximum sum of a subarray of size k.

    Args:
        arr: The input array.
        k: The size of the subarray.

    Returns:
        The maximum sum of a subarray of size k, or -1 if k > len(arr).
    """
    n = len(arr)
    if k > n:
        return -1  # Invalid input

    # Initial window sum
    window_sum = sum(arr[:k])
    max_sum = window_sum

    # Slide the window
    for i in range(n - k):
        window_sum = window_sum - arr[i] + arr[i + k] #Remove left element, add right element
        max_sum = max(max_sum, window_sum)

    return max_sum

# Example Usage
arr = [1, 4, 2, 10, 2, 3, 1, 0, 20]
k = 4
result = max_subarray_sum(arr, k)
print(f"Maximum subarray sum of size {k}: {result}") #Output: Maximum subarray sum of size 4: 24
# Time Complexity: O(n)
# Space Complexity: O(1)

Java:

class SlidingWindow {
    public static int maxSubarraySum(int[] arr, int k) {
        int n = arr.length;
        if (k > n) {
            return -1; // Invalid input
        }

        // Initial window sum
        int windowSum = 0;
        for (int i = 0; i < k; i++) {
            windowSum += arr[i];
        }

        int maxSum = windowSum;

        // Slide the window
        for (int i = 0; i < n - k; i++) {
            windowSum = windowSum - arr[i] + arr[i + k];
            maxSum = Math.max(maxSum, windowSum);
        }

        return maxSum;
    }

    public static void main(String[] args) {
        int[] arr = {1, 4, 2, 10, 2, 3, 1, 0, 20};
        int k = 4;
        int result = maxSubarraySum(arr, k);
        System.out.println("Maximum subarray sum of size " + k + ": " + result); //Output: Maximum subarray sum of size 4: 24
    }
    // Time Complexity: O(n)
    // Space Complexity: O(1)
}

C++:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int maxSubarraySum(vector<int>& arr, int k) {
    int n = arr.size();
    if (k > n) {
        return -1; // Invalid input
    }

    // Initial window sum
    int windowSum = 0;
    for (int i = 0; i < k; i++) {
        windowSum += arr[i];
    }

    int maxSum = windowSum;

    // Slide the window
    for (int i = 0; i < n - k; i++) {
        windowSum = windowSum - arr[i] + arr[i + k];
        maxSum = max(maxSum, windowSum);
    }

    return maxSum;
}

int main() {
    vector<int> arr = {1, 4, 2, 10, 2, 3, 1, 0, 20};
    int k = 4;
    int result = maxSubarraySum(arr, k);
    cout << "Maximum subarray sum of size " << k << ": " << result << endl; //Output: Maximum subarray sum of size 4: 24
    return 0;
}
// Time Complexity: O(n)
// Space Complexity: O(1)

4. Common Patterns

• Fixed-Size Window: As shown above, the window size k remains constant.
• Variable-Size Window: The window size changes dynamically based on certain conditions. This is often used to find the smallest/largest subarray that satisfies a given constraint.
• Two Pointers (Shrinking/Expanding Window): Use two pointers (left and right) to define the window. Expand the window by moving the right pointer and shrink the window by moving the left pointer.

5. Pro Tips

• Pre-computation: Calculate the initial window sum or other relevant values outside the loop to avoid redundant calculations.
• Delta Updates: Instead of recalculating the entire window sum in each iteration, update it by subtracting the outgoing element and adding the incoming element. This is crucial for performance.
• Edge Cases: Always handle edge cases, such as empty input arrays, invalid window sizes (k > array length), and arrays with all negative numbers.
• Data Structures: Sometimes, using a hash map or other data structure within the sliding window can help track the frequency of elements or other relevant information.
• Think Incrementally: Focus on how the problem changes from one window position to the next. This will help you determine the necessary updates.

6. Practice Problems

1. Maximum Sum Subarray of Size K: (Covered in the implementation examples above)
2. Longest Substring Without Repeating Characters: (LeetCode #3)
3. Minimum Size Subarray Sum: (LeetCode #209)

7. Templates

These templates can be easily adapted for similar problems.

Python Template (Variable Window Size):

def sliding_window_variable(arr, target):
    """
    Template for variable window size problems.

    Args:
        arr: The input array.
        target: The target value to achieve.

    Returns:
        The result (e.g., minimum length, maximum sum, etc.).
    """
    left = 0
    current_sum = 0  # Or other relevant variable
    min_length = float('inf') # or other default value

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

        # Shrink the window while the condition is met
        while current_sum >= target: # Replace with your condition
            min_length = min(min_length, right - left + 1)
            current_sum -= arr[left]
            left += 1

    return min_length if min_length != float('inf') else 0 # Or other default return

Java Template (Variable Window Size):

class SlidingWindowVariable {
    public static int slidingWindowVariable(int[] arr, int target) {
        int left = 0;
        int currentSum = 0;
        int minLength = Integer.MAX_VALUE;

        for (int right = 0; right < arr.length; right++) {
            currentSum += arr[right];

            while (currentSum >= target) { // Replace with your condition
                minLength = Math.min(minLength, right - left + 1);
                currentSum -= arr[left];
                left++;
            }
        }

        return (minLength == Integer.MAX_VALUE) ? 0 : minLength;
    }
}

C++ Template (Variable Window Size):

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits> // For INT_MAX

using namespace std;

int slidingWindowVariable(vector<int>& arr, int target) {
    int left = 0;
    int currentSum = 0;
    int minLength = INT_MAX;

    for (int right = 0; right < arr.size(); right++) {
        currentSum += arr[right];

        while (currentSum >= target) { // Replace with your condition
            minLength = min(minLength, right - left + 1);
            currentSum -= arr[left];
            left++;
        }
    }

    return (minLength == INT_MAX) ? 0 : minLength;
}

These templates provide a starting point. Remember to adapt the conditions and calculations to fit the specific requirements of the problem you are solving. Good luck!