Sliding Window — Count vs. Existence ​

Common Interview Questions ​

1. Subarrays with K Different Integers (LC 992)

   • Problem: The helper function for this problem, at_most_k_distinct, is the canonical example of counting subarrays. It must find every single subarray that satisfies the "at most K" property.
   • Sliding Window Signal: The problem asks for a total count of subarrays, not the length of one.
   • Window State: A hash map to track frequencies of distinct elements.
   • Goal: Use the specific counting formula count += (right - left + 1) inside the main loop to accumulate the total number of valid subarrays ending at each position.

2. Permutation in String (LC 567)

   • Problem: Given two strings s1 and s2, return true if s2 contains any permutation of s1.
   • Sliding Window Signal: This is an existence problem. You don't need to find all anagrams, just determine if one exists. This uses a fixed-size window.
   • Window State: Two frequency maps to compare the pattern string and the current window.
   • Goal: As soon as a valid window is found (s_counts == p_counts), you can immediately return True without checking the rest of the string.

3. Number of Substrings Containing All Three Characters (LC 1358)

   • Problem: Given a string with only 'a', 'b', and 'c', find the number of substrings that contain at least one of each.
   • Sliding Window Signal: The request for the "number of substrings" points to a counting problem.
   • Window State: A hash map to track the counts of 'a', 'b', and 'c'. The window is valid when all three have a count > 0.
   • Goal: This is a mix of "shortest" and "counting" logic. Once the window [left, right] is valid, you know that this window, and any window that starts before left and ends at right, is also valid. The number of such windows is left + 1.

Sliding window problems can ask for the length of a valid window (e.g., longest, shortest), the count of all valid windows, or simply whether a valid window exists.

Length vs. Existence ​

This is the most common case. Finding the length of the longest/shortest valid window inherently proves existence. If a problem just asks "does a subarray exist that...", you can solve it by finding the length of the shortest such subarray. If the result is not the default initial value (e.g., float('inf')), then one exists.

Example: Check if a subarray of sum k exists. ​

You can solve this by finding the shortest subarray of sum k. If the returned length is not infinity, one must exist.

def subarray_sum_exists(nums, target):
    left = 0
    current_sum = 0
    found = False
    
    for right in range(len(nums)):
        current_sum += nums[right]
        
        while current_sum > target and left <= right:
            current_sum -= nums[left]
            left += 1
            
        if current_sum == target and right - left + 1 > 0:
            return True # Found one, no need to find the shortest
            
    return False

# You could also just call the min_subarray_len function from the 
# "longest-vs-shortest" guide and check:
# min_subarray_len(target, nums) > 0

Counting Valid Subarrays ​

This is a more advanced variation. Instead of just finding one optimal window, you need to count every single subarray that satisfies the condition.

The Key Insight: For a valid window [left, right], any subarray that ends at right and starts at or after left is also guaranteed to be valid, assuming the condition is monotonic (i.e., shrinking a valid window keeps it valid).

Therefore, for each position of the right pointer, the number of valid subarrays ending at right is right - left + 1.

Template for Counting ​

def count_valid_subarrays(nums, condition):
    left = 0
    total_count = 0
    # ... window state ...

    for right in range(len(nums)):
        # Expand window
        # ... update state ...

        # Shrink window until it is valid
        while not is_valid( ... ):
            # ... update state ...
            left += 1
        
        # At this point, the window [left, right] is the smallest valid
        # window ending at `right`. All subarrays ending at `right`
        # with a start >= `left` are also valid.
        # Number of such subarrays = (right - left + 1)
        total_count += (right - left + 1)
        
    return total_count

Example Problem: Count Subarrays with At Most K Distinct Elements ​

This was the helper function used to solve "Subarrays with K Different Integers" (LC 992).

from collections import defaultdict

def at_most_k_distinct_count(nums, k):
    if k < 0:
        return 0
        
    left = 0
    count = 0
    freq = defaultdict(int)
    
    for right in range(len(nums)):
        freq[nums[right]] += 1
        
        # Shrink until the window is valid
        while len(freq) > k:
            freq[nums[left]] -= 1
            if freq[nums[left]] == 0:
                del freq[nums[left]]
            left += 1
            
        # Add the number of valid subarrays ending at `right`
        count += (right - left + 1)
        
    return count

How the Algorithm Works ​

• Existence: The algorithm expands the window, and if the condition is ever met, it can return True immediately. It's an early-exit version of the "shortest window" problem, as we only need to find one valid instance.
• Counting: The counting algorithm uses a standard expand-and-shrink window. The critical insight happens after the window is made valid: for a valid window [left, right], we know every subarray that ends at right and starts at any index from left to right must also be valid. The number of such subarrays is right - left + 1, which we add to our total count before moving to the next right element.

Tricky Parts & Decision Points ​

1. The Counting Formula: The count += (right - left + 1) step is the trickiest part. It's essential to understand why this works: you are not just counting the one valid window [left, right], but all newly formed valid windows that end at the current right pointer.
2. Monotonicity of the Condition: The counting formula only works if the condition is monotonic. For example, if a subarray [i, j] has at most k distinct elements, then any subarray [i', j] where i' > i will also have at most k distinct elements. This property doesn't hold for "exactly K" problems, which is why they require a different approach.
3. Existence vs. Min Length: Be careful not to over-engineer. If a problem just asks for existence (True/False), you don't need to find the absolute minimum length or count anything; you can exit as soon as you find the first valid window.