Sliding Window

1. The Core Concept

• Subarray: A contiguous section of an array defined by a left and right bound.
• The Goal: Find a “valid” window based on a constraint metric (e.g., sum, count of specific elements) and a numeric restriction (e.g., ≤ target).
• Dynamic vs. Fixed: Windows can grow and shrink dynamically, or stay at a fixed length k.

2. Dynamic Sliding Window

Scenario: Find the “best” valid subarray (longest, shortest, etc.) where the size isn't predefined.

Logic

1. Expand: Add arr[right] to your tracking variable (e.g., curr_sum).
2. Validate: While the window is invalid, shrink it from the left:
   • Subtract arr[left] from your tracking variable.
   • Increment left++.
3. Update: Once valid, update your answer (e.g., max_length = max(max_length, right - left + 1)).

• Time Complexity: O(n) (each pointer moves at most n times)
• Space Complexity: O(1)

3. Fixed-Size Sliding Window

Scenario: The problem specifies a subarray length of exactly k.

Logic

1. Iterate from index k to n - 1.
2. Slide: Add the new element arr[i] and remove the element that is now outside the window arr[i - k].
3. Update: Compare the result after each shift.

4. Counting Subarrays (The Math Trick)

If a problem asks for the number of valid subarrays:

• For any valid window [left, right], the number of valid subarrays ending at right is equal to the window size: right - left + 1.
• Total Count: In each iteration, add right - left + 1 to your total ans.

Comparison Table