Sliding Window

Not Started

The sliding window technique maintains a window of elements and slides it across the data structure. This is optimal for problems involving subarrays, substrings, and finding patterns within contiguous sequences. It reduces time complexity from O(n²) to O(n).

Time Complexity: O(n) with two pointers moving forward

Space Complexity: O(k) for window size or hash map

Use Cases: Longest substring, maximum sum subarray, minimum window substring

Pattern: Expand window until condition met, then contract from left

Implementation Examples

# Python - Max sum subarray of size k
def max_sum_subarray(arr, k):
    """Find max sum of subarray with size k"""
    if k > len(arr):
        return 0
    
    window_sum = sum(arr[:k])
    max_sum = window_sum
    
    for i in range(k, len(arr)):
        window_sum = window_sum - arr[i - k] + arr[i]
        max_sum = max(max_sum, window_sum)
    
    return max_sum

# Example: arr = [1,4,2,10,2,3,1,0,20], k = 4
# Output: 24 (subarray [10,2,3,1,0,20] → wait, that's 6)

// C++ - Max sum subarray of size k
int maxSumSubarray(std::vector<int>& arr, int k) {
    if (k > arr.size()) return 0;
    
    int windowSum = 0;
    for (int i = 0; i < k; i++) {
        windowSum += arr[i];
    }
    
    int maxSum = windowSum;
    
    for (int i = k; i < arr.size(); i++) {
        windowSum = windowSum - arr[i - k] + arr[i];
        maxSum = std::max(maxSum, windowSum);
    }
    
    return maxSum;
}

// C# - Max sum subarray of size k
int MaxSumSubarray(int[] arr, int k) {
    if (k > arr.Length) return 0;
    
    int windowSum = 0;
    for (int i = 0; i < k; i++) {
        windowSum += arr[i];
    }
    
    int maxSum = windowSum;
    
    for (int i = k; i < arr.Length; i++) {
        windowSum = windowSum - arr[i - k] + arr[i];
        maxSum = Math.Max(maxSum, windowSum);
    }
    
    return maxSum;
}

// Java - Max sum subarray of size k
int maxSumSubarray(int[] arr, int k) {
    if (k > arr.length) return 0;
    
    int windowSum = 0;
    for (int i = 0; i < k; i++) {
        windowSum += arr[i];
    }
    
    int maxSum = windowSum;
    
    for (int i = k; i < arr.length; i++) {
        windowSum = windowSum - arr[i - k] + arr[i];
        maxSum = Math.max(maxSum, windowSum);
    }
    
    return maxSum;
}

Common Patterns

Fixed Size: Window size is constant, slide one element at a time

Variable Size: Expand/contract window based on conditions

Two Pointer Variant: Left and right pointers define the window

Optimization: Maintain running sum/frequency instead of recalculating