🚀 Day 1: Mastering the Sliding Window Pattern (Amazon Interview Series)

Amazon loves to test how efficiently you can process subarrays and substrings. Brute force often leads to O(n²) or worse. The Sliding Window Pattern is the key to cracking these problems in O(n).

---

🔑 What is the Sliding Window Pattern?

The Sliding Window technique uses two pointers (usually left and right) to represent a window (subarray or substring). As we expand the window, we add elements; as we shrink it, we remove elements. This eliminates unnecessary recomputation.

When to use?

• Problems involving subarrays/substrings
• Need to calculate maximum, minimum, longest, shortest for consecutive elements
• Constraints on window size or unique characters/elements

---

📝 Problem 1: Maximum Sum Subarray of Size K

👉 Amazon-style phrasing:
You are given an array of integers and an integer k. Find the maximum sum of any contiguous subarray of size k.

Java Solution

public class MaxSumSubarray {
    public static int maxSumSubarray(int[] arr, int k) {
        int windowSum = 0, maxSum = 0;
        int left = 0;

        for (int right = 0; right < arr.length; right++) {
            windowSum += arr[right]; // expand

            // once we reach window size
            if (right >= k - 1) {
                maxSum = Math.max(maxSum, windowSum);
                windowSum -= arr[left]; // shrink
                left++;
            }
        }
        return maxSum;
    }

    public static void main(String[] args) {
        int[] arr = {2, 1, 5, 1, 3, 2};
        System.out.println(maxSumSubarray(arr, 3)); // Output: 9
    }
}

✅ Time Complexity: O(n)
✅ Why Amazon likes it: Optimizing rolling sums without recalculating from scratch.

---

📝 Problem 2: Longest Substring Without Repeating Characters

👉 Amazon-style phrasing:
Given a string s, find the length of the longest substring without repeating characters.

Java Solution

import java.util.*;

public class LongestSubstring {
    public static int lengthOfLongestSubstring(String s) {
        Set<Character> seen = new HashSet<>();
        int left = 0, maxLen = 0;

        for (int right = 0; right < s.length(); right++) {
            while (seen.contains(s.charAt(right))) {
                seen.remove(s.charAt(left)); // shrink
                left++;
            }
            seen.add(s.charAt(right));
            maxLen = Math.max(maxLen, right - left + 1);
        }
        return maxLen;
    }

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

✅ Time Complexity: O(n)
✅ Why Amazon likes it: Checks if you can optimize substring uniqueness checks with hashing and window movement.

---

📝 Problem 3: Minimum Window Substring

👉 Amazon-style phrasing:
Given strings s and t, return the minimum window substring of s that contains all characters in t.

Java Solution

import java.util.*;

public class MinWindowSubstring {
    public static String minWindow(String s, String t) {
        Map<Character, Integer> need = new HashMap<>();
        for (char c : t.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }

        Map<Character, Integer> window = new HashMap<>();
        int left = 0, have = 0, needCount = need.size();
        int minLen = Integer.MAX_VALUE, start = 0;

        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            window.put(c, window.getOrDefault(c, 0) + 1);

            if (need.containsKey(c) && window.get(c).intValue() == need.get(c).intValue()) {
                have++;
            }

            while (have == needCount) {
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    start = left;
                }
                char remove = s.charAt(left);
                window.put(remove, window.get(remove) - 1);
                if (need.containsKey(remove) && window.get(remove) < need.get(remove)) {
                    have--;
                }
                left++;
            }
        }
        return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
    }

    public static void main(String[] args) {
        String s = "ADOBECODEBANC", t = "ABC";
        System.out.println(minWindow(s, t)); // Output: "BANC"
    }
}

✅ Time Complexity: O(n)
✅ Why Amazon likes it: Combines window expansion + contraction while tracking counts (classic Amazon favorite).

---

🎯 Key Takeaways

• Sliding Window transforms O(n²) into O(n).
• Master variations: fixed window, variable window, with hash maps/sets.
• Amazon often wraps these problems in real-world contexts (log processing, traffic monitoring, recommendation systems).

---

📅 Next in the series (Day 2):
👉 Two Pointers Pattern – used in problems like 3Sum, Container With Most Water, and Move Zeroes.