Pattern 02: Sliding Window

0. The Template (Copy-Paste Skeleton)

There are exactly two window templates. Decide first: is the window size fixed or variable? Everything else follows.

// TEMPLATE A — FIXED-SIZE window of length k
int fixedWindow(int[] nums, int k) {
    int sum = 0, best = Integer.MIN_VALUE;

    for (int i = 0; i < nums.length; i++) {
        sum += nums[i];                        // 1. ADD the incoming element
        if (i >= k) sum -= nums[i - k];        // 2. REMOVE the one that fell out
        if (i >= k - 1) best = Math.max(best, sum);   // 3. RECORD once the window is full
    }
    return best;
}

// TEMPLATE B — VARIABLE-SIZE window (the workhorse: longest/shortest satisfying a condition)
int variableWindow(int[] nums) {
    int left = 0, best = 0;
    // ... window state: a running sum, a HashMap<Character,Integer> counts, etc.

    for (int right = 0; right < nums.length; right++) {
        add(nums[right]);                      // 1. EXPAND: absorb the right element

        while (windowIsInvalid()) {            // 2. SHRINK until the window is legal again
            remove(nums[left]);
            left++;
        }

        best = Math.max(best, right - left + 1);   // 3. RECORD — LONGEST: outside the while
    }
    return best;
}

The single most important knob: where you record the answer

Goal	while condition	Record where
Longest valid window	while (INVALID) — shrink until legal	after the while loop
Shortest valid window	while (VALID) — shrink while still legal	inside the while loop, before shrinking

Getting this backwards is the #1 sliding-window bug. Say it out loud before you type: “longest → shrink until valid, record after; shortest → shrink while valid, record inside.”

Why it’s O(n) despite the nested while

left only ever moves forward and never passes right. Across the whole run it advances at most n times total → amortised O(1) per step, O(n) overall.

Common window state

Problem type	State to maintain
sum / average	running int sum
distinct characters	HashMap<Character,Integer> or int[128] counts
“at most k distinct”	map size
“at most k zeros / flips”	a zeroCount counter
max/min inside window	monotonic Deque → see 21-Stacks-And-Queues

---

1. Pattern Identification & Logic

How to Identify (Interview Triggers)

• “Find the longest/shortest substring/subarray” with a condition
• “Contiguous” elements or subarray mentioned
• “At most K distinct” or “exactly K” constraints
• Window size is fixed or variable
• “Maximum sum of subarray of size K”

The Algorithm (Pseudocode)

Fixed-size Window:

for right = 0 to n-1:
    add array[right] to window
    if window_size == k:
        record result
        remove array[right - k + 1] from window

Variable-size Window (Shrinkable):

left = 0
for right = 0 to n-1:
    expand window by including array[right]

    while (window is invalid):
        shrink window by removing array[left]
        left++

    update result with current window

The ‘Trick’ to Know

• The window never moves backward. Both left and right only move forward, giving O(n) total despite the nested while loop.
• For “exact K” problems, use the trick: exactlyK = atMostK(K) - atMostK(K-1).

---

2. Java Implementation (Brute Force vs. Optimal)

Example Problem: Longest Substring Without Repeating Characters - LC 3

Brute Force: O(n^3)

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int maxLen = 0;
        for (int i = 0; i < s.length(); i++) {
            for (int j = i; j < s.length(); j++) {
                if (hasAllUnique(s, i, j)) {
                    maxLen = Math.max(maxLen, j - i + 1);
                } else {
                    break;
                }
            }
        }
        return maxLen;
    }

    private boolean hasAllUnique(String s, int start, int end) {
        Set<Character> set = new HashSet<>();
        for (int i = start; i <= end; i++) {
            if (!set.add(s.charAt(i))) return false;
        }
        return true;
    }
}

Optimal: Sliding Window with HashMap - O(n)

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> lastSeen = new HashMap<>();
        int maxLen = 0;
        int left = 0;

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

            if (lastSeen.containsKey(c) && lastSeen.get(c) >= left) {
                left = lastSeen.get(c) + 1;
            }

            lastSeen.put(c, right);
            maxLen = Math.max(maxLen, right - left + 1);
        }

        return maxLen;
    }
}

Java Architecture Insights

• HashMap<Character, Integer> over HashSet: Storing the index lets us jump left directly to the duplicate’s next position instead of shrinking one-by-one.
• s.charAt(i) vs toCharArray(): charAt() avoids creating a new array. For very hot loops, toCharArray() can be slightly faster due to fewer bounds checks.
• Why not int[128] instead of HashMap? For ASCII-only inputs, int[128] is faster (no hashing overhead) and uses less memory.

---

3. Mental Model & Visualization

ASCII Diagram (s = “abcabcbb”)

Step 1: [a] b c a b c b b    left=0, right=0, maxLen=1
Step 2: [a b] c a b c b b    left=0, right=1, maxLen=2
Step 3: [a b c] a b c b b    left=0, right=2, maxLen=3
Step 4:  a [b c a] b c b b   left=1, right=3, maxLen=3  ('a' repeated, left jumps)
Step 5:  a b [c a b] c b b   left=2, right=4, maxLen=3
Step 6:  a b c [a b c] b b   left=3, right=5, maxLen=3
Step 7:  a b c a b [c b] b   left=5, right=6, maxLen=3  ('b' repeated)
Step 8:  a b c a b c [b] b   left=6, right=7, maxLen=3  ('b' repeated)

Answer: 3

Senior Mental Trigger

“Contiguous subarray/substring with a constraint = expand right, shrink left.”

---

4. Curated Problem Lists

Commonly Asked (Bread & Butter)

#	Problem	Difficulty
LC 3	Longest Substring Without Repeating Characters	Medium
LC 209	Minimum Size Subarray Sum	Medium
LC 643	Maximum Average Subarray I	Easy
LC 219	Contains Duplicate II	Easy
LC 1004	Max Consecutive Ones III	Medium

FAANG ‘Aha!’ Level (Hard/Unintuitive)

#	Problem	Difficulty
LC 76	Minimum Window Substring	Hard
LC 239	Sliding Window Maximum	Hard
LC 424	Longest Repeating Character Replacement	Medium
LC 567	Permutation in String	Medium
LC 992	Subarrays with K Different Integers	Hard

---

5. Time & Space Complexity Table

Approach	Time	Space	Notes
Brute Force	O(n^3)	O(n)	Check every substring + uniqueness
Sliding Window	O(n)	O(k)	k = size of character set