Sliding Window

Introduction

The Sliding Window technique is a powerful algorithmic approach for solving problems involving arrays or strings. It efficiently processes contiguous subarrays or substrings by maintaining a “window” that slides through the data structure, avoiding redundant calculations.

In this article, we’ll explore the Sliding Window technique through practical LeetCode problems, providing clean, well-explained solutions in both C# and Python.

What is Sliding Window?

Sliding Window is a technique that maintains a subset of elements (the “window”) as it slides through an array or string. Instead of recalculating everything for each possible subarray, we efficiently update the window by adding new elements and removing old ones.

Key Concepts:

1. Window A contiguous subset of elements in the array or string that we’re currently examining.

2. Two Pointers Typically uses two pointers (left and right) to define the window boundaries.

3. Window Expansion Move the right pointer to expand the window (add elements).

4. Window Contraction Move the left pointer to contract the window (remove elements).

Types of Sliding Window:

1. Fixed Size Window The window size remains constant as it slides through the array.

2. Variable Size Window The window size changes based on certain conditions (most common).

When to Use Sliding Window:

• Subarray/Substring Problems: Finding optimal subarrays or substrings
• Contiguous Elements: Problems involving contiguous sequences
• Optimization: Finding maximum, minimum, or optimal subarrays
• String Problems: Finding substrings with specific properties
• Array Problems: Finding subarrays that meet certain criteria

Advantages:

• Efficiency: O(n) time complexity for many problems
• Space Efficient: Often uses O(1) or O(k) extra space
• Avoids Redundancy: Doesn’t recalculate overlapping windows
• Intuitive: Easy to understand and implement

Sliding Window Template

Variable Size Window Template:

int left = 0;
for (int right = 0; right < array.Length; right++) 
{
    // Expand window: add array[right]
    // Update window state
    
    while (/* window needs to shrink */) 
    {
        // Contract window: remove array[left]
        // Update window state
        left++;
    }
    
    // Update result based on current window
}

Fixed Size Window Template:

int left = 0;
for (int right = 0; right < array.Length; right++) 
{
    // Expand window: add array[right]
    
    if (right - left + 1 == windowSize) 
    {
        // Process window of fixed size
        // Update result
        // Remove array[left] and move left
        left++;
    }
}

Problem 1: Longest Substring Without Repeating Characters

Problem Statement

Given a string s, find the length of the longest substring without repeating characters.

Example

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.

Understanding the Problem

We need to find the longest substring where all characters are unique. As we expand the window, if we encounter a repeating character, we need to contract the window from the left until the character is no longer in the window.

Solution Strategy

Sliding Window with Hash Map:

1. Use two pointers: left (start of window) and right (end of window)
2. Use a dictionary to track the last index of each character
3. Expand window by moving right pointer
4. If character at right is already in window:
   • Move left to max(left, lastIndex[char] + 1) to exclude the duplicate
5. Update the maximum length seen so far
6. Update the last index of current character

C# Solution

public class Solution 
{
    public int LengthOfLongestSubstring(string s) 
    {
        int maxLength = 0;
        int startWindow = 0;
        Dictionary<char, int> charIndex = new Dictionary<char, int>();
        
        for (int i = 0; i < s.Length; i++)
        {
            char currentChar = s[i];
            
            // If character is already in current window, move start
            if (charIndex.ContainsKey(currentChar))
            {
                // Move start to after the last occurrence of this character
                startWindow = Math.Max(startWindow, charIndex[currentChar] + 1);
            }
            
            // Update last index of current character
            charIndex[currentChar] = i;
            
            // Update maximum length
            maxLength = Math.Max(maxLength, i - startWindow + 1);
        }
        
        return maxLength;
    }
}

Python 3 Solution

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        startWindow = 0
        maxLength = 0
        charIndex = {}
        
        for i in range(len(s)):
            ch = s[i]
            
            # If character is already in current window, move start
            if ch in charIndex:
                # Move start to after the last occurrence of this character
                startWindow = max(startWindow, charIndex[ch] + 1)
            
            # Update last index of current character
            charIndex[ch] = i
            
            # Update maximum length
            maxLength = max(maxLength, i - startWindow + 1)
        
        return maxLength

Complexity Analysis

• Time Complexity: O(n) where n is the length of the string
• Space Complexity: O(min(n, m)) where m is the size of the character set (dictionary size)

Key Insight

We use Math.Max(startWindow, charIndex[ch] + 1) instead of just charIndex[ch] + 1 because startWindow might have already moved past the last occurrence due to a previous duplicate character. This ensures we don’t move the window backward.

Problem 2: Minimum Size Subarray Sum

Problem Statement

Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray [numsl, numsl+1, ..., numsr-1, numsr] of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead.

Example

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.

Input: target = 4, nums = [1,4,4]
Output: 1

Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0

Understanding the Problem

We need to find the shortest contiguous subarray whose sum is at least target. We can use a sliding window that expands until the sum is sufficient, then contracts to find the minimum length.

Solution Strategy

Sliding Window with Sum Tracking:

1. Use two pointers: left (start) and right (end)
2. Expand window by moving right and subtracting from target
3. When target <= 0, the window sum is sufficient
4. Contract window from left while condition holds:
   • Update minimum length
   • Add back to target as we remove elements
   • Move left pointer
5. Return minimum length found

C# Solution

public class Solution 
{
    public int MinSubArrayLen(int target, int[] nums) 
    {
        int startWindow = 0;
        int arrayLength = nums.Length;
        int result = arrayLength + 1; // Initialize to impossible value
        
        for (int i = 0; i < arrayLength; i++)
        {
            // Expand window: subtract current element from target
            target -= nums[i];
            
            // While window sum is sufficient (target <= 0)
            while (target <= 0)
            {
                // Update minimum length
                result = Math.Min(result, i - startWindow + 1);
                
                // Contract window: add back element at start
                target += nums[startWindow];
                startWindow++;
            }
        }
        
        // Return result if found, otherwise 0
        return result % (arrayLength + 1);
    }
}

Python 3 Solution

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        startWindow = 0
        arrayLength = len(nums)
        result = arrayLength + 1  # Initialize to impossible value
        
        for i in range(arrayLength):
            # Expand window: subtract current element from target
            target -= nums[i]
            
            # While window sum is sufficient (target <= 0)
            while target <= 0:
                # Update minimum length
                result = min(result, i - startWindow + 1)
                
                # Contract window: add back element at start
                target += nums[startWindow]
                startWindow += 1
        
        # Return result if found, otherwise 0
        return result % (arrayLength + 1)

Complexity Analysis

• Time Complexity: O(n) where n is the length of nums
  • Each element is added and removed at most once
• Space Complexity: O(1) – only using a few variables

Key Insight

Instead of maintaining a separate sum variable, we modify target directly by subtracting elements as we expand and adding them back as we contract. The condition target <= 0 means the current window sum is at least the original target value.

The result % (arrayLength + 1) trick returns result if it was updated (found a valid subarray), or 0 if it remained arrayLength + 1 (no valid subarray found).

Sliding Window Patterns

Pattern 1: Expand and Contract

Used when we need to find optimal subarrays/substrings:

1. Expand window until condition is met
2. Contract window while condition still holds
3. Track optimal result

Example: Minimum Size Subarray Sum

Pattern 2: Fixed Size Window

Used when window size is predetermined:

1. Expand to fixed size
2. Process window
3. Slide by removing left and adding right

Example: Maximum sum of subarray of size k

Pattern 3: At Most/At Least K

Used for problems with constraints like “at most k distinct characters”:

1. Expand while condition is valid
2. Contract when condition is violated
3. Track result at each valid state

Example: Longest substring with at most k distinct characters

Pattern 4: Two Pointers with Hash Map

Used when tracking character/element frequencies:

1. Use hash map to track window contents
2. Expand and contract based on map state
3. Update result based on current window

Example: Longest Substring Without Repeating Characters

Key Takeaways

Sliding Window Best Practices:

1. Identify Window Boundaries Clearly define what left and right pointers represent.

2. Determine Expansion Condition When should the window expand? (usually always, or until condition met)

3. Determine Contraction Condition When should the window contract? (when condition is violated or optimal found)

4. Update Result Appropriately Decide when to update the result: during expansion, contraction, or both.

5. Handle Edge Cases Empty arrays, single elements, no valid windows, etc.

When to Use Sliding Window:

• Contiguous Subarrays/Substrings: Problems involving contiguous sequences
• Optimization Problems: Finding optimal subarrays (max/min length, sum, etc.)
• Frequency Problems: Problems involving character/element counts
• Range Queries: Problems asking about ranges that meet criteria
• O(n) Requirement: When O(n) time complexity is needed

Common Sliding Window Mistakes:

• Off-by-One Errors: Incorrect window size calculation (right - left + 1)
• Not Updating State: Forgetting to update data structures when expanding/contracting
• Wrong Contraction Condition: Contracting when should expand, or vice versa
• Missing Edge Cases: Not handling empty inputs or no valid windows
• Inefficient Updates: Recalculating entire window instead of incremental updates

Optimization Tips:

1. Use Hash Maps for Frequency Track character/element frequencies efficiently.

2. Incremental Updates Update window state incrementally rather than recalculating.

3. Early Termination Stop early if possible (e.g., found optimal solution).

4. Space Optimization Use arrays instead of hash maps when possible (for fixed character sets).

Comparison with Other Techniques

Sliding Window vs Two Pointers:

Sliding Window: Maintains a window that expands and contracts, typically for subarray/substring problems.

Two Pointers: Two pointers move toward each other or in the same direction, typically for sorted array problems.

Sliding Window vs Brute Force:

Brute Force: O(n²) or O(n³) – checks all possible subarrays.

Sliding Window: O(n) – efficiently processes subarrays by avoiding redundant calculations.

Conclusion

The Sliding Window technique is a powerful approach for solving subarray and substring problems efficiently. The key is identifying when a problem can benefit from maintaining a window that slides through the data structure.

Key patterns to remember:

• Expand and Contract: Most common pattern for optimization problems
• Fixed Size: When window size is predetermined
• Hash Map Tracking: For frequency-based problems
• Incremental Updates: Update window state efficiently

Practice identifying sliding window opportunities and mastering the expansion/contraction logic. The more you practice, the better you’ll become at recognizing when and how to apply the sliding window technique.

Remember: Sliding window is particularly effective when you need to find optimal contiguous subarrays or substrings, and it can often reduce time complexity from O(n²) to O(n).

Happy coding!