🚀 Blog 5: Sliding Window & Monotonic Queue — Expedia DSA Prep

Expedia frequently asks problems around subarray/substring properties, especially involving:

Max/min in sliding windows
Longest subarray with constraints
Substring counting with distinct characters

We’ll cover:

Sliding Window Maximum
Longest Subarray with Sum ≤ K
Longest Substring with K Distinct Characters

🔹 Problem 1: Sliding Window Maximum

Pattern: Monotonic Deque

📌 Find the maximum value in every sliding window of size k.

import java.util.*;

public class SlidingWindowMax {
    public static int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 0) return new int[0];
        Deque<Integer> dq = new LinkedList<>();
        int[] result = new int[nums.length - k + 1];

        for (int i = 0; i < nums.length; i++) {
            while (!dq.isEmpty() && dq.peekFirst() <= i - k)
                dq.pollFirst();

            while (!dq.isEmpty() && nums[dq.peekLast()] < nums[i])
                dq.pollLast();

            dq.offerLast(i);

            if (i >= k - 1)
                result[i - k + 1] = nums[dq.peekFirst()];
        }
        return result;
    }

    public static void main(String[] args) {
        int[] arr = {1,3,-1,-3,5,3,6,7};
        System.out.println(Arrays.toString(maxSlidingWindow(arr, 3)));
        // [3,3,5,5,6,7]
    }
}

✅ Time Complexity: O(N)

🔹 Problem 2: Longest Subarray with Sum ≤ K

Pattern: Prefix Sum + Monotonic Queue

📌 Find the longest subarray such that the sum ≤ K.

public class LongestSubarraySum {
    public static int longestSubarray(int[] nums, int k) {
        int n = nums.length;
        int[] prefix = new int[n + 1];
        for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];

        int ans = 0;
        Deque<Integer> dq = new LinkedList<>();

        for (int i = 0; i <= n; i++) {
            while (!dq.isEmpty() && prefix[i] - prefix[dq.peekFirst()] > k)
                dq.pollFirst();

            if (!dq.isEmpty())
                ans = Math.max(ans, i - dq.peekFirst());

            while (!dq.isEmpty() && prefix[dq.peekLast()] >= prefix[i])
                dq.pollLast();

            dq.offerLast(i);
        }
        return ans;
    }

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

✅ Time Complexity: O(N)

🔹 Problem 3: Longest Substring with K Distinct Characters

Pattern: Sliding Window with HashMap

📌 Find length of the longest substring with at most K distinct chars.

import java.util.*;

public class LongestKDistinct {
    public static int lengthOfLongestSubstringKDistinct(String s, int k) {
        Map<Character, Integer> map = new HashMap<>();
        int left = 0, maxLen = 0;

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

            while (map.size() > k) {
                char leftChar = s.charAt(left);
                map.put(leftChar, map.get(leftChar) - 1);
                if (map.get(leftChar) == 0) map.remove(leftChar);
                left++;
            }

            maxLen = Math.max(maxLen, right - left + 1);
        }
        return maxLen;
    }

    public static void main(String[] args) {
        System.out.println(lengthOfLongestSubstringKDistinct("eceba", 2)); // 3 ("ece")
    }
}