Sliding Window

A "subarray" is a contiguous slice of an array. If you need to find the maximum sum of any 3 consecutive numbers in an array, the naive approach is to check every possible group of 3. You start at index 0, check 0-1-2. Then start at index 1, check 1-2-3. Then start at index 2, check 2-3-4. You end up calculating the same middle numbers over and over again. This can lead to an \(O(n*k)\) time complexity.

The Sliding Window technique avoids this repetitive work. Imagine a physical picture frame (a "window") placed over the first 3 numbers. To move the window forward, you don't rebuild the whole frame. You simply subtract the number that falls out of the left side and add the new number that enters the right side. This turns the process into a blazingly fast \(O(n)\) scan!

Pattern 1: Fixed-size Window

This is when the problem gives you a specific size (e.g., "find the max sum of exactly *k* elements").

1. First, calculate the sum/result for the very first window of size k.
2. Record this as the best/maximum result so far.
3. Start a loop from k to the end of the array.
4. At each step, take your previous result, add the new element arr[i], and subtract the old element arr[i-k]. Update the max result if necessary.

Pattern 2: Dynamically-sized Window

Sometimes the window size isn't fixed. The problem might ask "find the smallest contiguous subarray whose sum is greater than or equal to S". Here, the window grows and shrinks like an accordion.

You still use a left and right pointer:

• Expand the window by moving right forward, adding each new number to a running sum.
• When the running sum meets the condition (e.g., >= S), try to make the window as small as possible by moving the left pointer forward (and subtracting those values), recording the window length each time.
• When the condition breaks, go back to expanding with the right pointer.

Even though there is a while loop inside a for loop, both the left and right pointers only move forward, meaning every element is processed at most twice. The time complexity stays \(O(n)\)! This is closely related to the two pointer technique.