Variable-Size Sliding Windows in Java

Variable-size sliding windows represent a fundamental pattern for solving dynamic window problems where the optimal window size is not predetermined. This approach uses flexible window boundaries to efficiently process subarrays or substrings with varying constraints.

1. Pattern Restatement

Clarifying questions to ask the interviewer:

1. What are the constraints on input size (e.g., is it bounded by 10⁶ or larger)?
2. Are duplicates allowed in the input array? How should they be handled?
3. Should I return the actual subarray/window or just its length/size?
4. Can I mutate the input array during processing?
5. What is the target time complexity for follow-ups (e.g., O(n) or O(n log n))?

Restatement of the pattern: The variable-size window pattern involves finding a contiguous subarray or substring that satisfies specific criteria, where the size of the window is not fixed but determined dynamically based on constraints like sum, count, or other conditions. The window expands and contracts to efficiently explore valid substructures.

Signal words and constraint shape: Key indicators include phrases like "subarray with sum," "substring without repeating characters," "longest substring with at most K distinct characters," or "minimum window substring." These problems typically involve:

• Finding a contiguous subsequence with specific properties
• Having variable window sizes that adapt based on constraints
• Using two pointers (or sliding window) to maintain valid ranges

Assumptions made:

• The input is a linear structure (array, string) where contiguous substructures can be efficiently indexed
• There's an explicit constraint that allows for dynamic window sizing (e.g., sum threshold, character uniqueness)
• The problem is about optimization over a sliding window rather than enumeration of all valid windows

Scenario suitability: This pattern is best suited for static input scenarios where the full dataset is available upfront. It's less appropriate for streaming data where elements arrive one at a time and the window must adapt continuously without full knowledge of future elements.

The pattern works particularly well when there's a monotonic property (e.g., increasing sum as window grows) that allows for efficient expansion and contraction of the window bounds.

2. When to Use This Pattern

Signal words and constraint shapes in a problem statement that indicate this pattern:

• "Find the longest/shortest substring/array with property X"
• "Maximum/minimum window size satisfying condition"
• "Sliding window" or "variable-size window" explicitly mentioned
• Problems involving "at most K" or "exactly K" constraints
• "Subarray" or "substring" with optimization goals

Why this pattern fits better than the most common alternatives: Variable-size windows are ideal when we need to find optimal contiguous substructures with dynamic bounds. Unlike fixed-size sliding windows, this pattern allows the window to expand and contract dynamically based on constraints. Compared to two-pointer approaches or brute force, it typically achieves O(n) time complexity by avoiding redundant computations through careful expansion and contraction.

Conditions where a variation or related pattern applies instead:

• Fixed-size sliding windows when window size is predetermined (e.g., "find maximum sum of any 3 consecutive elements")
• Two-pointer techniques when we can move pointers independently (e.g., "find two elements that sum to target")
• Prefix sum techniques when we're looking for subarrays with specific sums

The core insight that makes this pattern work: The key insight is that for many optimization problems over contiguous subarrays, we can maintain a valid window and grow it until it becomes invalid, then shrink it from the left until it's valid again. This ensures we never revisit elements unnecessarily and can process each element at most twice, leading to linear time complexity.

This pattern is particularly effective when:

1. The constraint can be checked in O(1) time for a window
2. Expanding the window maintains validity conditions that can be efficiently tested
3. We're optimizing over a continuous range of elements

3. Approach Evolution

Interview communication script:

"My first instinct is to use a brute force approach where I check every possible subarray, but that's O(n²) because for each starting position, I'd need to expand and check all possible ending positions. Let me think about how to optimize this...

I notice that if I maintain a sliding window invariant, I can reduce it to O(n) by using the two-pointer technique. The key insight is that once I know a window satisfies the constraint, I can extend it to the right and only shrink it from the left when it violates the constraint. This way, each element is visited at most twice.

Let me think about what invariant I need to maintain: the window should always contain at most k distinct elements. When I add a new element, if it exceeds k distinct elements, I need to shrink the window from the left until the constraint is satisfied again.

The optimization comes from realizing that I don't need to check all subarrays - I can maintain a valid window and grow it as long as it stays valid, then shrink it when it becomes invalid."

Brute-force approach and why it is not ideal:

The brute force approach would involve checking every possible subarray to find the longest one with at most k distinct elements. For each starting position i, we would expand to the right until we have more than k distinct elements, then record the length and continue. This approach has O(n³) time complexity because:

• We have n possible starting positions
• For each starting position, we might check up to n ending positions
• Each subarray validation takes O(n) time in the worst case

Improved approach and the key optimization:

The key optimization is using a sliding window with two pointers (left and right) that maintain a valid window. The crucial insight is that we only need to expand the window when it's valid, and we can shrink it from the left only when it becomes invalid. This ensures that each element is processed at most twice - once when added to the window and once when removed.

Final approach with step-by-step reasoning:

1. Use two pointers (left and right) to maintain a sliding window
2. Use a HashMap to track the count of each element in the current window
3. Expand the right pointer and add elements to the window
4. When we have more than k distinct elements, shrink the window from the left until constraint is satisfied
5. Track the maximum valid window size throughout the process

Important invariants that must hold:

• The window always contains at most k distinct elements
• When expanding, we add elements to the HashMap and increment their counts
• When shrinking, we decrement element counts and remove entries when count reaches 0
• The window size never exceeds the maximum valid window seen so far

4. Data Structure Choice

For the variable-size window pattern, the primary data structure is a sliding window approach using two pointers (left and right) to maintain a dynamic range in the array.

Primary Data Structures Used

1. Two Pointers (int left, int right) - The core of variable-size window technique

   • Used to define the current window boundaries in the array
   • Allow for dynamic expansion and contraction of the window
   • Enable O(1) access to window endpoints without copying data

2. Array/Collection (int[] nums) - Input structure

   • Read-only access to the problem data
   • May be modified in-place if allowed by constraints

Why Each Data Structure Is Needed

The two-pointer approach is essential because:

• It enables us to maintain a "window" of elements that can grow or shrink dynamically
• We can expand the window by moving the right pointer and contract it by moving the left pointer
• This allows us to efficiently explore all valid subarrays without redundant computation

Time and Space Impact

• Time Complexity: O(n) - Each element is visited at most twice (once by left pointer, once by right pointer)
• Space Complexity: O(1) - Only using a constant amount of extra space for the pointers and variables

Helper Structures

In some implementations, we might use:

• HashMap/HashSet - To track element frequencies or uniqueness within the window (when dealing with subarray problems requiring frequency counting)
• Queue - In specific variants where we need to maintain order of elements in the current window

The two-pointer approach is preferred over fixed-size windows because it adapts to the problem constraints dynamically, making it more efficient for problems where window size isn't predetermined.

The key insight is that we don't need to store all intermediate windows - we only care about the current valid window and can efficiently move its boundaries.

5. Algorithm Walkthrough

Let me trace through the algorithm using the example nums = [1,2,3,4,5], k = 3:

Step 1: Initialize variables

• left = 0, right = 0
• sum = 0, maxSum = Integer.MIN_VALUE

Step 2: Expand window by moving right pointer

• right = 0: Add nums[0] = 1 → sum = 1
• Window size = 1 < k, continue expanding

Step 3: Continue expansion

• right = 1: Add nums[1] = 2 → sum = 3
• Window size = 2 < k, continue expanding

Step 4: Expand until window size equals k

• right = 2: Add nums[2] = 3 → sum = 6
• Window size = 3 = k, now we can compute max

Step 5: Update max and begin contraction

• maxSum = Math.max(Integer.MIN_VALUE, 6) = 6
• left = 0: Remove nums[0] = 1 → sum = 5
• Window size = 2 < k, continue expanding

Step 6: Continue expansion and contraction

• right = 3: Add nums[3] = 4 → sum = 9
• Window size = 3 = k, update max: maxSum = Math.max(6, 9) = 9
• left = 1: Remove nums[1] = 2 → sum = 7
• Window size = 2 < k, continue expanding

Step 7: Final iterations

• right = 4: Add nums[4] = 5 → sum = 12
• Window size = 3 = k, update max: maxSum = Math.max(9, 12) = 12
• left = 2: Remove nums[2] = 3 → sum = 9

Step 8: Algorithm termination

• right reaches end of array, return maxSum = 12

The key insight is that we maintain a sliding window of exactly size k, always tracking the maximum sum seen so far. The algorithm correctly handles all edge cases like arrays shorter than k by returning 0 in such cases.

graph TD
    A[Start] --> B{right < nums.length?}
    B -- Yes --> C[Add nums[right] to sum]
    C --> D{windowSize == k?}
    D -- Yes --> E[Update maxSum]
    E --> F[Remove nums[left] from sum]
    F --> G[Increment left]
    G --> H[Increment right]
    H --> B
    B -- No --> I[Increment right]
    I --> B

6. Java Solution

public class VariableSizeWindow {
    
    /**
     * Finds the length of the longest substring with at most k distinct characters
     * Uses sliding window technique with variable size
     * 
     * @param s input string
     * @param k maximum number of distinct characters allowed
     * @return length of longest valid substring
     */
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        if (s == null || s.length() == 0 || k <= 0) {
            return 0;
        }
        
        // Map to store character frequencies in current window
        Map<Character, Integer> charCount = new HashMap<>();
        
        int left = 0;           // Left pointer of sliding window
        int maxLength = 0;      // Result: maximum length found
        
        // Expand window with right pointer
        for (int right = 0; right < s.length(); right++) {
            char rightChar = s.charAt(right);
            
            // Add current character to window
            charCount.put(rightChar, charCount.getOrDefault(rightChar, 0) + 1);
            
            // Shrink window from left while we have more than k distinct chars
            while (charCount.size() > k) {
                char leftChar = s.charAt(left);
                charCount.put(leftChar, charCount.get(leftChar) - 1);
                
                // Remove character from map if count becomes 0
                if (charCount.get(leftChar) == 0) {
                    charCount.remove(leftChar);
                }
                
                left++; // Move left pointer
            }
            
            // Update maximum length if current window is valid
            maxLength = Math.max(maxLength, right - left + 1);
        }
        
        return maxLength;
    }
    
    /**
     * Finds the longest substring with at most k distinct characters
     * Returns the actual substring, not just length
     * 
     * @param s input string
     * @param k maximum number of distinct characters allowed
     * @return longest valid substring
     */
    public String longestSubstringKDistinct(String s, int k) {
        if (s == null || s.length() == 0 || k <= 0) {
            return "";
        }
        
        Map<Character, Integer> charCount = new HashMap<>();
        int left = 0;
        int maxLength = 0;
        int bestStart = 0; // Track start index of longest substring
        
        for (int right = 0; right < s.length(); right++) {
            char rightChar = s.charAt(right);
            charCount.put(rightChar, charCount.getOrDefault(rightChar, 0) + 1);
            
            while (charCount.size() > k) {
                char leftChar = s.charAt(left);
                charCount.put(leftChar, charCount.get(leftChar) - 1);
                
                if (charCount.get(leftChar) == 0) {
                    charCount.remove(leftChar);
                }
                
                left++;
            }
            
            // Update best substring if current window is longer
            if (right - left + 1 > maxLength) {
                maxLength = right - left + 1;
                bestStart = left;
            }
        }
        
        return s.substring(bestStart, bestStart + maxLength);
    }
}

This solution implements the sliding window technique for variable-size windows. It uses a HashMap to track character frequencies in the current window, expanding the right boundary while maintaining at most k distinct characters. When the constraint is violated, it shrinks the window from the left until valid again. The key insight is that we only need to track character counts, not the actual characters in window, making it efficient for this pattern.

7. Complexity Analysis

Time Complexity: O(n)

The algorithm uses a sliding window approach with two pointers (left and right) that traverse the array exactly once. Each element is visited at most twice - once by the right pointer and once by the left pointer when shrinking the window. Since we perform constant-time operations at each step (updating sums, checking conditions, updating maximum), the overall time complexity is linear.

Space Complexity: O(1)

The solution uses only a constant amount of extra space regardless of input size:

• Two integer pointers (left and right)
• Two integer variables (currentSum and maxLen)
• A few scalar variables for tracking indices and conditions

No additional data structures like arrays, hash maps, or stacks are required. The space usage remains constant as the input size grows.

Why These Bounds Are Correct

The linear time bound is optimal for this problem because we must examine each element at least once to determine the maximum valid subarray length. The space bound is optimal because we only need to maintain state about the current window and the best solution found so far, which can be represented with a constant number of variables.

The solution is near-optimal as it achieves the theoretical lower bound for time complexity (O(n)) and space complexity (O(1)) for this class of variable-size window problems where we're looking for a maximum-length subarray satisfying a constraint.

The algorithm's efficiency comes from avoiding redundant computations through the sliding window technique, ensuring each element is processed a minimal number of times.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty array: Handle gracefully with early return or zero-length window
• Single element: Verify that the sliding window logic works correctly with size 1
• Null input: If input validation is required, handle null pointer exceptions

Duplicate Values and Repeated States

• All identical elements: The algorithm should still correctly identify valid windows despite duplicates
• Repeated patterns: Ensure that window boundaries are properly tracked to avoid missing optimal solutions

Boundary Conditions

• Window size equals array length: The entire array is one valid window
• Window size of 0: Should return appropriate default or throw meaningful exception
• Array with negative numbers: The logic for window expansion/shrinking must handle negative sums correctly

Common Implementation Mistakes

• Off-by-one errors in window expansion: Starting with left = 0 and right = 0 but not properly handling the initial window size
• Incorrect condition checking: Forgetting to check if current window meets criteria before updating result, or checking the wrong condition (e.g., sum vs. count)
• Not resetting window state properly: When shrinking the window, ensure all necessary variables are reset or updated correctly
• Integer overflow in sum calculations: For very large arrays, sum operations might overflow; consider using long or handling overflow explicitly
• Inconsistent window size tracking: Mixing up the meaning of right - left + 1 vs. right - left in window size calculations

Additional Pitfalls

• Assuming sorted input: The variable-size window pattern works on unsorted arrays, so don't make assumptions about order
• Incorrect result update timing: Updating the optimal window too early or too late in the iteration can lead to incorrect results
• Memory leaks in custom data structures: If using collections like LinkedList or ArrayList, ensure proper cleanup when needed

9. Alternative Approaches

There are several alternative approaches to solving variable-size window problems, each with different trade-offs:

1. Fixed-Size Sliding Window Approach: If we can determine a maximum window size beforehand, we could use a fixed-size sliding window with a queue or circular buffer. However, this approach requires knowing the upper bound on window size, which isn't given in variable-size window problems. This would be inefficient for problems where the optimal window size varies significantly.

2. Binary Search on Window Size: We could binary search over possible window sizes and for each size, check if a valid solution exists using a fixed-size sliding window. This approach would have O(log(max_window_size) × n) time complexity, which is less efficient than our optimal O(n) solution.

3. Two-Pointer with Manual Tracking: Instead of using a deque, we could manually track the window bounds with two pointers and maintain additional data structures to track the minimum element in the current window. This approach is more error-prone and requires careful handling of edge cases where elements are removed from the window.

4. Priority Queue Approach: Using a min-heap to track minimum elements in the current window. While this can work, it has O(log n) insertion and deletion operations, making the overall complexity O(n log n), which is worse than our O(n) deque-based solution.

The deque-based approach is preferred because it maintains the optimal O(1) amortized time complexity for operations while ensuring we always have access to the minimum element in constant time. The key insight is that for variable-size windows, we need to efficiently maintain and query the minimum element across all valid window states, which the deque approach handles optimally by maintaining a monotonic structure.

The main trade-off with alternatives is between simplicity of implementation and time complexity. Our chosen approach provides the best balance for this specific pattern, where we're looking to minimize the maximum element across all valid windows.

10. Test Cases

import java.util.*;

public class VariableSizeWindowTestCases {
    
    public static void main(String[] args) {
        // Test Case 1: Basic example from problem description
        int[] nums1 = {1, 2, 3, 2, 1, 4, 5};
        int k1 = 3;
        int threshold1 = 4;
        // Expected: [2, 3, 4] - subarrays [1,2,3], [2,3,2], [3,2,1] have averages >= 4
        System.out.println("Test 1: " + Arrays.toString(solve(nums1, k1, threshold1)));
        
        // Test Case 2: Empty array
        int[] nums2 = {};
        int k2 = 1;
        int threshold2 = 1;
        // Expected: []
        System.out.println("Test 2: " + Arrays.toString(solve(nums2, k2, threshold2)));
        
        // Test Case 3: Single element array
        int[] nums3 = {5};
        int k3 = 1;
        int threshold3 = 5;
        // Expected: [0]
        System.out.println("Test 3: " + Arrays.toString(solve(nums3, k3, threshold3)));
        
        // Test Case 4: All elements same
        int[] nums4 = {3, 3, 3, 3, 3};
        int k4 = 2;
        int threshold4 = 3;
        // Expected: [0, 1, 2, 3]
        System.out.println("Test 4: " + Arrays.toString(solve(nums4, k4, threshold4)));
        
        // Test Case 5: No valid subarrays
        int[] nums5 = {1, 2, 3, 4, 5};
        int k5 = 2;
        int threshold5 = 10;
        // Expected: []
        System.out.println("Test 5: " + Arrays.toString(solve(nums5, k5, threshold5)));
        
        // Test Case 6: Large numbers
        int[] nums6 = {1000000, 2000000, 3000000};
        int k6 = 2;
        int threshold6 = 1500000;
        // Expected: [0, 1]
        System.out.println("Test 6: " + Arrays.toString(solve(nums6, k6, threshold6)));
        
        // Test Case 7: With duplicates in valid subarrays
        int[] nums7 = {1, 2, 3, 2, 3, 4};
        int k7 = 3;
        int threshold7 = 2;
        // Expected: [0, 1, 2, 3]
        System.out.println("Test 7: " + Arrays.toString(solve(nums7, k7, threshold7)));
    }
    
    // Placeholder for actual solution method - see Section 6
    public static int[] solve(int[] nums, int k, int threshold) {
        // Implementation would go here
        return new int[0];
    }
}

Sample Test Cases:

1. Basic functionality: Array [1,2,3,2,1,4,5] with k=3, threshold=4 should return indices [2,3,4]
2. Edge case - empty array: Empty input should return empty result
3. Edge case - single element: Single element array with matching threshold should return index [0]
4. All same elements: When all elements are identical, many subarrays should qualify
5. No valid subarrays: When no subarray meets threshold, return empty result
6. Large numbers: Test with large integer values to ensure overflow handling
7. Duplicate valid subarrays: Multiple valid subarrays with same elements

Tricky Cases:

• Subarrays that straddle the boundary between valid and invalid
• Arrays with mixed positive/negative numbers where average calculation matters
• Very large arrays that test performance limits

Boundary Cases:

• k equals array length (entire array is one window)
• k larger than array length (no valid windows possible)
• Threshold equals minimum element value in array
• Empty input arrays with zero-length windows

11. Final Summary

The core idea is to use a variable-size sliding window technique with two pointers to efficiently find the longest substring without repeating characters in linear time. This solution works by maintaining a window that expands when no duplicates are found and contracts when duplicates are encountered, ensuring we always track the maximum valid window size. The approach is optimal because it makes exactly one pass through the string while using a hash map to achieve O(1) character lookups, resulting in an overall time complexity of O(n) where n is the length of the input string.