Sliding window

Question 1

What is the Sliding Window pattern and when is it used?

Answer 1

Maintains a variable-size window sliding over array/string to find subarrays.

Use Case: Contiguous subarray/substring problems (e.g., max sum)

Example: [Trapping Rain Water].

Question 2

What are the key steps in the Sliding Window pattern?

Answer 2

1. Initialize left/right pointers.
2. Expand right until condition met.
3. Shrink left to optimize.
4. Track result (e.g., max length).

Explain steps for [Trapping Rain Water] aloud.

Question 3

How does the Sliding Window pattern apply to [Trapping Rain Water]?

Answer 3

Compute water trapped between bars.

Approach: Use two pointers to track max heights, calculate water at lowe

Example: [Trapping Rain Water].

Question 4

What are the complexity and gotchas of the Sliding Window pattern?

Answer 4

Time: O(n), Space: O(1).

Gotchas: Empty array, invalid window (e.g., k=0).

List edge cases for [Trapping Rain Water] aloud.

Question 5

Code example of the Sliding Window pattern.

Answer 5

```python
from typing import List
def trap(height: List[int]) -> int:
left, right, water = 0, len(height)-1, 0
max_left, max_right = 0, 0
while left < right:
max_left = max(max_left, height[left])
max_right = max(max_right, height[right])
if max_left <= max_right:
water += max_left - height[left]
left += 1
else:
water += max_right - height[right]
right -= 1
return water
~~~