Sliding Window Pattern

🪟 Sliding Window Animation - Find Max Sum of K Elements

K = 3 | Current Sum: 8

🪟 Window

[0]

[1]

[2]

[3]

[4]

[5]

Window [2,1,5] = 8

Step 1 of 4

🎯 Explain Like I'm 5...

Imagine you have 7 candies in a row: 🍬🍭🍬🍭🍬🍭🍬. You want to find 3 candies next to each other that taste the BEST together!

🧒 Slow Way: Taste candies 1+2+3, write it down. Then start over and taste candies 2+3+4, write it down. Keep starting over each time! 😓

🧙 Smart Way (Sliding Window): Use a magic box 📦 that holds exactly 3 candies!

• Put candies 1,2,3 in the box → taste them!
• Remove candy 1 from the left, Add candy 4 on the right → taste them!
• Remove candy 2, Add candy 5 → keep sliding!

🚀 Why is it faster? You don't start over each time! You just remove one candy from the left and add one on the right. It's like sliding a window across your candies - much smarter than tasting the same candies over and over! 🪟➡️

When Should You Use This Pattern?

✓Finding something in a contiguous part of an array/string
✓Finding the maximum or minimum in a subarray
✓Finding the longest or shortest substring with a condition
✓When the problem asks about a specific window size

📝 Example 1: Maximum Sum of K Consecutive Elements

Given array [2, 1, 5, 1, 3, 2] and K=3, find the maximum sum of any 3 consecutive numbers.

Step-by-Step Thinking:

Window 1: [2, 1, 5] = 8
Window 2: [1, 5, 1] = 7
Window 3: [5, 1, 3] = 9 ← Maximum!
Window 4: [1, 3, 2] = 6

MaxSumSubarray.java

java

public class MaxSumSubarray {
    // Find maximum sum of K consecutive elements
    public static int findMaxSum(int[] arr, int k) {
        // Step 1: Calculate sum of first window
        int windowSum = 0;
        for (int i = 0; i < k; i++) {
            windowSum += arr[i];
        }
        int maxSum = windowSum;  // Track the maximum
        // Step 2: Slide the window
        for (int i = k; i < arr.length; i++) {
            // Remove leftmost element, add rightmost element
            windowSum = windowSum - arr[i - k] + arr[i];
            // Update maximum if current window is bigger
            maxSum = Math.max(maxSum, windowSum);
        }
        return maxSum;
    }
    public static void main(String[] args) {
        int[] arr = {2, 1, 5, 1, 3, 2};
        int k = 3;
        int result = findMaxSum(arr, k);
        System.out.println("Maximum sum: " + result);
        // Output: Maximum sum: 9
    }
}

📝 Example 2: Longest Substring Without Repeating Characters

Given "abcabcbb", find the length of longest substring without repeating characters. Answer: "abc" with length 3.

LongestSubstring.java

java

import java.util.HashMap;
public class LongestSubstring {
    public static int lengthOfLongestSubstring(String s) {
        // Map to store character and its index
        HashMap<Character, Integer> map = new HashMap<>();
        int maxLength = 0;
        int windowStart = 0;
        // Expand window with windowEnd
        for (int windowEnd = 0; windowEnd < s.length(); windowEnd++) {
            char rightChar = s.charAt(windowEnd);
            // If character already in window, shrink from left
            if (map.containsKey(rightChar)) {
                // Move windowStart to right of duplicate character
                windowStart = Math.max(windowStart, map.get(rightChar) + 1);
            }
            // Add character to map with its index
            map.put(rightChar, windowEnd);
            // Calculate current window size
            maxLength = Math.max(maxLength, windowEnd - windowStart + 1);
        }
        return maxLength;
    }
    public static void main(String[] args) {
        System.out.println(lengthOfLongestSubstring("abcabcbb")); // 3
        System.out.println(lengthOfLongestSubstring("bbbbb"));    // 1
        System.out.println(lengthOfLongestSubstring("pwwkew"));   // 3
    }
}

📝 Example 3: Smallest Subarray With Sum Greater Than Target

Given [2, 1, 5, 2, 3, 2] and target = 7, find the smallest subarray with sum ≥ 7. Answer: [5, 2] with length 2.

SmallestSubarray.java

java

public class SmallestSubarray {
    public static int findMinSubArray(int[] arr, int target) {
        int minLength = Integer.MAX_VALUE;
        int windowSum = 0;
        int windowStart = 0;
        for (int windowEnd = 0; windowEnd < arr.length; windowEnd++) {
            // Add next element to window
            windowSum += arr[windowEnd];
            // Shrink window as small as possible while sum >= target
            while (windowSum >= target) {
                // Update minimum length
                minLength = Math.min(minLength, windowEnd - windowStart + 1);
                // Remove leftmost element and shrink window
                windowSum -= arr[windowStart];
                windowStart++;
            }
        }
        return minLength == Integer.MAX_VALUE ? 0 : minLength;
    }
    public static void main(String[] args) {
        int[] arr = {2, 1, 5, 2, 3, 2};
        int target = 7;
        int result = findMinSubArray(arr, target);
        System.out.println("Smallest subarray length: " + result);
        // Output: Smallest subarray length: 2
    }
}

🔑 Key Points to Remember

1️⃣Two types: Fixed Size window and Dynamic Size window
2️⃣Always think: "Can I reuse calculations from the previous window?"
3️⃣Time Complexity: O(n) - each element is visited at most twice!
4️⃣Use HashMap to track elements in dynamic windows

💪 Practice Problems

• Fruits Into Baskets
• Longest Substring with K Distinct Characters
• Maximum of All Subarrays of Size K
• Minimum Window Substring
• Permutation in String