Sliding Window Pattern – All Problems with Step-by-Step Iteration (Java)
Sliding Window is a powerful technique to solve contiguous subarray and substring problems efficiently by avoiding repeated calculations.
Problem Statement
Given arrays and strings, solve multiple classic problems involving contiguous subarrays or substrings using fixed-size and variable-size sliding window techniques.
Examples:
Input: [2,1,5,1,3,2], k = 3 Output: Max Sum Subarray = 9 Input: "ADOBECODEBANC", "ABC" Output: BANC
Approaches Used
- Fixed Size Sliding Window
- Variable Size Sliding Window
Java Code Implementation
import java.util.*;
public class SlidingWindowAllProblems {
/* =====================================================
1. Maximum Sum Subarray of Size K
===================================================== */
static int maxSumSubarray(int[] arr, int k) {
int sum = 0;
for (int i = 0; i < k; i++) sum += arr[i];
int max = sum;
for (int i = k; i < arr.length; i++) {
sum += arr[i] - arr[i - k];
max = Math.max(max, sum);
}
return max;
}
/* =====================================================
2. First Negative Number in Every Window
===================================================== */
static void firstNegativeInWindow(int[] arr, int k) {
Deque dq = new ArrayDeque<>();
for (int i = 0; i < arr.length; i++) {
if (arr[i] < 0) dq.addLast(i);
if (!dq.isEmpty() && dq.peekFirst() <= i - k)
dq.pollFirst();
if (i >= k - 1)
System.out.print(dq.isEmpty() ? "0 " : arr[dq.peekFirst()] + " ");
}
System.out.println();
}
/* =====================================================
3. Count Distinct Elements in Every Window
===================================================== */
static void countDistinct(int[] arr, int k) {
Map map = new HashMap<>();
for (int i = 0; i < k; i++)
map.put(arr[i], map.getOrDefault(arr[i], 0) + 1);
System.out.print(map.size() + " ");
for (int i = k; i < arr.length; i++) {
int left = arr[i - k];
map.put(left, map.get(left) - 1);
if (map.get(left) == 0) map.remove(left);
map.put(arr[i], map.getOrDefault(arr[i], 0) + 1);
System.out.print(map.size() + " ");
}
System.out.println();
}
/* =====================================================
4. Average of Subarrays of Size K
===================================================== */
static void averageSubarrays(int[] arr, int k) {
int sum = 0;
for (int i = 0; i < k; i++) sum += arr[i];
System.out.print((double) sum / k + " ");
for (int i = k; i < arr.length; i++) {
sum += arr[i] - arr[i - k];
System.out.print((double) sum / k + " ");
}
System.out.println();
}
/* =====================================================
5. Maximum of All Subarrays of Size K
===================================================== */
static void maxOfSubarrays(int[] arr, int k) {
Deque dq = new ArrayDeque<>();
for (int i = 0; i < arr.length; i++) {
while (!dq.isEmpty() && arr[dq.peekLast()] <= arr[i])
dq.pollLast();
dq.addLast(i);
if (dq.peekFirst() <= i - k)
dq.pollFirst();
if (i >= k - 1)
System.out.print(arr[dq.peekFirst()] + " ");
}
System.out.println();
}
/* =====================================================
6. Longest Substring Without Repeating Characters
===================================================== */
static int longestUniqueSubstring(String s) {
boolean[] freq = new boolean[256];
int start = 0, max = 0;
for (int end = 0; end < s.length(); end++) {
while (freq[s.charAt(end)]) {
freq[s.charAt(start)] = false;
start++;
}
freq[s.charAt(end)] = true;
max = Math.max(max, end - start + 1);
}
return max;
}
/* =====================================================
7. Longest Substring with K Distinct Characters
===================================================== */
static int longestKDistinct(String s, int k) {
Map map = new HashMap<>();
int start = 0, max = 0;
for (int end = 0; end < s.length(); end++) {
map.put(s.charAt(end), map.getOrDefault(s.charAt(end), 0) + 1);
while (map.size() > k) {
char left = s.charAt(start++);
map.put(left, map.get(left) - 1);
if (map.get(left) == 0) map.remove(left);
}
max = Math.max(max, end - start + 1);
}
return max;
}
/* =====================================================
8. Smallest Subarray with Sum >= K
===================================================== */
static int smallestSubarray(int[] arr, int k) {
int start = 0, sum = 0, minLen = Integer.MAX_VALUE;
for (int end = 0; end < arr.length; end++) {
sum += arr[end];
while (sum >= k) {
minLen = Math.min(minLen, end - start + 1);
sum -= arr[start++];
}
}
return minLen == Integer.MAX_VALUE ? 0 : minLen;
}
/* =====================================================
9. Minimum Window Substring
===================================================== */
static String minWindow(String s, String t) {
Map map = new HashMap<>();
for (char c : t.toCharArray())
map.put(c, map.getOrDefault(c, 0) + 1);
int start = 0, count = map.size();
int minLen = Integer.MAX_VALUE, minStart = 0;
for (int end = 0; end < s.length(); end++) {
char c = s.charAt(end);
if (map.containsKey(c)) {
map.put(c, map.get(c) - 1);
if (map.get(c) == 0) count--;
}
while (count == 0) {
if (end - start + 1 < minLen) {
minLen = end - start + 1;
minStart = start;
}
char left = s.charAt(start++);
if (map.containsKey(left)) {
map.put(left, map.get(left) + 1);
if (map.get(left) > 0) count++;
}
}
}
return minLen == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart + minLen);
}
/* =====================================================
MAIN METHOD – MULTIPLE INPUTS
===================================================== */
public static void main(String[] args) {
System.out.println("Max Sum Subarray: " +
maxSumSubarray(new int[]{2,1,5,1,3,2}, 3));
System.out.print("First Negative: ");
firstNegativeInWindow(new int[]{12,-1,-7,8,-15,30,16,28}, 3);
System.out.print("Distinct Count: ");
countDistinct(new int[]{1,2,1,3,4,2,3}, 4);
System.out.print("Averages: ");
averageSubarrays(new int[]{1,3,2,6,-1,4,1,8,2}, 5);
System.out.print("Max of Subarrays: ");
maxOfSubarrays(new int[]{1,3,-1,-3,5,3,6,7}, 3);
System.out.println("Longest Unique Substring: " +
longestUniqueSubstring("abcabcbb"));
System.out.println("Longest K Distinct: " +
longestKDistinct("aabacbebebe", 3));
System.out.println("Smallest Subarray >= 7: " +
smallestSubarray(new int[]{2,3,1,2,4,3}, 7));
System.out.println("Minimum Window Substring: " +
minWindow("ADOBECODEBANC", "ABC"));
}
}
Explanation
1. Maximum Sum Subarray of Size K
Input: [2,1,5,1,3,2], k = 3
- Initial window: [2,1,5] → sum = 8
- Slide window → add 1, remove 2 → [1,5,1] → sum = 7
- Slide window → add 3, remove 1 → [5,1,3] → sum = 9
- Slide window → add 2, remove 5 → [1,3,2] → sum = 6
Output: 9
2. First Negative Number in Every Window
Input: [12,-1,-7,8,-15,30,16,28], k = 3
- Window [12,-1,-7] → first negative = -1
- Window [-1,-7,8] → first negative = -1
- Window [-7,8,-15] → first negative = -7
- Window [8,-15,30] → first negative = -15
- Window [-15,30,16] → first negative = -15
- Window [30,16,28] → no negative → 0
Output: -1 -1 -7 -15 -15 0
3. Count Distinct Elements in Every Window
Input: [1,2,1,3,4,2,3], k = 4
- [1,2,1,3] → distinct = 3
- [2,1,3,4] → distinct = 4
- [1,3,4,2] → distinct = 4
- [3,4,2,3] → distinct = 3
Output: 3 4 4 3
4. Average of Subarrays of Size K
Input: [1,3,2,6,-1,4,1,8,2], k = 5
- [1,3,2,6,-1] → avg = 2.2
- [3,2,6,-1,4] → avg = 2.8
- [2,6,-1,4,1] → avg = 2.4
- [6,-1,4,1,8] → avg = 3.6
- [-1,4,1,8,2] → avg = 2.8
Output: 2.2 2.8 2.4 3.6 2.8
5. Maximum of All Subarrays of Size K
Input: [1,3,-1,-3,5,3,6,7], k = 3
- [1,3,-1] → max = 3
- [3,-1,-3] → max = 3
- [-1,-3,5] → max = 5
- [-3,5,3] → max = 5
- [5,3,6] → max = 6
- [3,6,7] → max = 7
Output: 3 3 5 5 6 7
6. Longest Substring Without Repeating Characters
Input: "abcabcbb"
- "abc" → length 3
- Repeat 'a' → shrink window
- Continue maintaining unique window
Output: 3
7. Longest Substring with K Distinct Characters
Input: "aabacbebebe", k = 3
- Expand window until > k distinct characters
- Shrink window from left until condition is valid
- Track max length during valid windows
Output: 7
8. Smallest Subarray with Sum ≥ K
Input: [2,3,1,2,4,3], k = 7
- [2,3,1,2] → sum = 8 → shrink
- [4,3] → sum = 7 → length = 2
Output: 2
9. Minimum Window Substring
Input: s = "ADOBECODEBANC", t = "ABC"
- Expand window until all chars A, B, C included
- Shrink window to minimize length
- Smallest valid window = "BANC"
Output: BANC
Technique Used: Sliding Window (Fixed & Variable)
Sample Output
Max Sum Subarray: 9 First Negative: -1 -1 -7 -15 -15 0 Distinct Count: 3 4 4 3 Averages: 2.2 2.8 2.4 3.6 2.8 Max of Subarrays: 3 3 5 5 6 7 Longest Unique Substring: 3 Longest K Distinct: 7 Smallest Subarray >= 7: 2 Minimum Window Substring: BANC
Time & Space Complexity
| Type | Time | Space |
|---|---|---|
| Sliding Window | O(n) | O(k) |
Interview Tip
If the problem asks for a contiguous subarray or substring with constraints, Sliding Window should be your first optimization choice.
Practice More
- Maximum vowels in a substring of size k
- Longest subarray with at most k odd numbers
Category: Arrays, Strings
Difficulty: Easy → Medium
Techniques: Sliding Window, HashMap, Deque
No comments:
Post a Comment