Sliding Windows

From structure to motion

In Introduction to Data Structures, we focused on choosing the right shape for data. In Recursion, we looked at solving a problem by breaking it into smaller calls.

Now we shift to a different kind of pattern: moving through linear data efficiently.

Sliding windows are most useful when a problem asks about a contiguous block inside an array or string:

• longest substring with some property
• maximum sum of k elements
• smallest subarray meeting a condition
• count of valid contiguous ranges

The core upgrade is this: instead of recomputing each block from scratch, we reuse work as the window moves.

A window is a live segment

A sliding window is usually represented by two indexes:

array:  [2, 1, 5, 1, 3, 2]
index:   0  1  2  3  4  5
             L-----R
window:     [1, 5, 1]

The window contains elements from left to right, inclusive.

The pattern works because we maintain a summary of the current window:

• current sum
• frequency map
• count of distinct characters
• product
• number of violations

Then we move one boundary and update the summary in O(1) or near O(1) time.

That maintained summary is the heart of the pattern.

Which problem is the clearest sliding window candidate?

When the size is known

If the problem says exactly k elements, use a fixed-size window.

Example: maximum sum of any contiguous subarray of size k.

Naive approach:

• compute every size-k sum separately
• each sum costs O(k)
• total cost: O(n * k)

Sliding window approach:

• build the first window once
• move right by one
• subtract the element that left
• add the element that entered
• total cost: O(n)

This is the same engineering instinct you use in Java systems work: keep the right running state instead of recomputing it.

```java
public class Main {
    public static int maxSumOfSizeK(int[] nums, int k) {
        if (nums == null || nums.length < k || k <= 0) {
            throw new IllegalArgumentException("Invalid input");
        }

        int windowSum = 0;
        for (int i = 0; i < k; i++) {
            windowSum += nums[i];
        }

        int best = windowSum;

        for (int right = k; right < nums.length; right++) {
            int left = right - k;
            windowSum -= nums[left];
            windowSum += nums[right];
            best = Math.max(best, windowSum);
        }

        return best;
    }

    public static void main(String[] args) {
        int[] nums = {2, 1, 5, 1, 3, 2};
        int k = 3;
        System.out.println(maxSumOfSizeK(nums, k)); // 9: [5, 1, 3]
    }
}
```

For an inclusive window using indexes left and right, fill in the Java expression for the current window size:

size = ______

When the size is discovered

Some problems do not give a fixed k. Instead, the window grows and shrinks until it satisfies a condition.

Common wording:

• longest substring without repeating characters
• smallest subarray with sum at least target
• longest subarray with at most k distinct values

The rhythm is usually:

1. Expand right to include a new element.
2. Update window state.
3. While the window is invalid, move left.
4. Record the best valid answer.

For strings, a Map or array-backed frequency table is often the state.

```java
import java.util.HashSet;
import java.util.Set;

public class Main {
    public static int longestUniqueSubstring(String s) {
        Set<Character> seen = new HashSet<>();
        int left = 0;
        int best = 0;

        for (int right = 0; right < s.length(); right++) {
            char incoming = s.charAt(right);

            while (seen.contains(incoming)) {
                seen.remove(s.charAt(left));
                left++;
            }

            seen.add(incoming);
            best = Math.max(best, right - left + 1);
        }

        return best;
    }

    public static void main(String[] args) {
        String s = "abcabcbb";
        System.out.println(longestUniqueSubstring(s)); // 3: "abc"
    }
}
```

True or false: In a sliding window solution, the window only expands; shrinking the left boundary means it is no longer a sliding window.

The invariant keeps you honest

A sliding window solution should have a sentence that is always true after your loop cleanup.

Examples:

• windowSum equals the sum of elements from left to right.
• seen contains exactly the characters currently inside the window.
• The window contains no duplicates.
• The product of the window is less than k.

A strong invariant prevents off-by-one bugs and tells you when to update the answer.

Fixed-size invariant

After each iteration, the window has exactly k elements.

Variable-size invariant

After shrinking, the window is valid.

Later, when you reach Dynamic Programming, you will also track state carefully—but sliding windows are about maintaining state over a moving contiguous segment.

Sometimes one right edge gives many answers

For some variable-window problems, once the current window is valid, every suffix ending at right may also be valid.

Example: count contiguous subarrays whose product is less than k.

If nums are positive and the window [left..right] has product < k, then these windows ending at right are also valid:

[left..right]
[left+1..right]
[left+2..right]
...
[right..right]

That count is:

right - left + 1

This is a powerful sliding window move: count many windows without listing them.

```java
public class Main {
    public static int countSubarraysProductLessThanK(int[] nums, int k) {
        if (k <= 1) return 0;

        int left = 0;
        int product = 1;
        int count = 0;

        for (int right = 0; right < nums.length; right++) {
            product *= nums[right];

            while (product >= k) {
                product /= nums[left];
                left++;
            }

            count += right - left + 1;
        }

        return count;
    }

    public static void main(String[] args) {
        int[] nums = {10, 5, 2, 6};
        int k = 100;
        System.out.println(countSubarraysProductLessThanK(nums, k)); // 8
    }
}
```

You are solving: longest substring with at most 2 distinct characters.

Your current window has 3 distinct characters after adding s.charAt(right). What should the algorithm do next?