What is Sliding Window
The sliding window pattern is a technique for efficiently processing sequential data, such as arrays and strings. It involves maintaining a dynamic window that slides across the data, allowing you to examine a fixed portion at a time. Instead of repeatedly scanning the entire dataset, this approach adjusts the window’s boundaries as needed to track relevant elements.
Depending on the problem, the sliding window can be of a fixed size or dynamic.
- The fixed-size window is used when the window size is given or constant. For example, find the largest sum of any three consecutive numbers.
- The dynamic window is used when the window size changes based on conditions. For example, find the smallest subarray whose sum exceeds a target.
- The sliding window technique uses two pointers representing the window’s boundaries. These pointers move through an array or a string to examine a portion of the data at a time. The window is then updated by adding new elements and removing old ones as the pointers move.
- In a fixed-size window, both pointers move together, keeping the window size constant.
Fixed Window Template
FUNCTION slidingWindow(arr, k, processWindow):
# Initialize the window result (sum, product, count, etc.)
windowResult = INITIAL_VALUE
# Compute the initial window’s result
FOR i FROM 0 TO k - 1:
UPDATE windowResult WITH arr[i]
# Process the first window
processWindow(windowResult)
# Slide the window across the array
FOR i FROM k TO length of arr - 1:
UPDATE windowResult BY ADDING arr[i] # Add a new element to the window
UPDATE windowResult BY REMOVING arr[i - k] # Remove outgoing element
processWindow(windowResult) # Operation on the updated window
Dynamic Window Template
FUNCTION slidingWindow(arr, condition, processWindow):
left = 0
windowState = INITIAL_VALUE
FOR right FROM 0 TO length of arr - 1:
UPDATE windowState WITH arr[right] # expand window
WHILE NOT condition(windowState): # shrink window if needed UPDATE windowState BY REMOVING arr[left] left = left + 1 processWindow(windowState, left, right)
Sliding WIndow Complexity
Avoids nested loops: Without a sliding window, many problems require checking all subarrays using two or more loops, leading to O(n2)O(n2) time complexity or more. The sliding window allows us to update the window by adjusting pointers, reducing the complexity of traversing and processing the entire array to linear, O(n)O(n).
Reuses computation: Instead of recalculating values for each window from scratch, the sliding window approach reuses previous calculations by adding new elements and removing old ones. In the example we discussed above, where we find the most chocolate chips in any 3 cookies, we only update the sum by adding the next cookie and removing the leftmost one.
Problems Matching pattern
- Contiguous data: The input data is stored in a contiguous manner, such as an array or string.
- Processing subsets of elements: The problem requires repeated computations on a contiguous subset of data elements (a subarray or a substring), such that the window moves across the input array from one end to the other. The size of the window may be fixed or variable, depending on the requirements of the problem.
- Efficient computation time complexity: The computations performed every time the window moves take constant or very small time.
- Sliding windows only work for contiguous subarrays and not subsequences
** Repeated DNA Sequences**
A DNA sequence consists of nucleotides represented by the letters ‘A’, ‘C’, ‘G’, and ‘T’ only. For example, “ACGAATTCCG” is a valid DNA sequence.
Given a string, s, that represents a DNA sequence, return all the 10-letter-long sequences (continuous substrings of exactly 10 characters) that appear more than once in s. You can return the output in any order.
Step 1: Encode characters into numbers
Step 2: Compute the first hash (rolling hash)
Step 3: Update the hash and use a set to track seen substrings
new hash == ((old hash×4old hash×4)) −− (leftmost digit×410)(leftmost digit×410)+ new digit+ new digit
public static List<String> findRepeatedDnaSequences(String s) {
Map<Character, Integer> toInt = new HashMap<Character, Integer>() {{ put('A', 0); put('C', 1); put('G', 2); put('T', 3); }};
List<Integer> encodedSequence = new ArrayList<>();
for (char c : s.toCharArray()) {
encodedSequence.add(toInt.get(c));
}</Integer></String>
int k = 10;
int n = s.length();
if (n <= k) return new ArrayList<>();
int a = 4;
int h = 0;
Set<Integer> seenHashes = new HashSet<>();
Set<String> output = new HashSet<>();
int a_k = 1;
for (int i = 0; i < k; i++) {
h = h * a + encodedSequence.get(i);
a_k *= a;
}
seenHashes.add(h);
for (int start = 1; start <= n - k; start++) {
h = h * a - encodedSequence.get(start - 1) * a_k + encodedSequence.get(start + k - 1);
if (seenHashes.contains(h)) {
output.add(s.substring(start, start + k));
} else {
seenHashes.add(h);
}
}
return new ArrayList<>(output);
}Sliding Window Maximum
You are given an array of integers nums and a sliding window of size w that moves from left to right across the array, shifting one position at a time.
Your task is to find the maximum value within the current window at each step and return it.
Our goal is to avoid recomputing the maximum value from scratch at every step. To do this, we maintain a list called currentWindow, which stores the indexes of useful elements. By useful, we mean elements that could still be the maximum in the current or any upcoming window. The list is kept in decreasing order of values in nums, i.e., the first index will always point to the largest element in the current window.
https://www.educative.io/courses/grokking-coding-interview/solution-sliding-window-maximum
Each of these steps makes sure that currentWindow always holds exactly the right elements:
- Older elements that can no longer be maximum are removed.
- Smaller elements that will be “dominated” by newer, larger elements are removed.
- The largest element’s index always remains at the front, so getting the max at each step is constant-time.
// function to clean up the window
public static Deque<Integer> cleanUp(int i, Deque<Integer> currentWindow, int[] nums) {
while (currentWindow.size() != 0 && nums[i] >= nums[currentWindow.getLast()]) {
currentWindow.removeLast();
}
return currentWindow;
}
// function to find the maximum in all possible windows
public static int[] findMaxSlidingWindow(int[] nums, int w) {
if (nums.length == 1) {
return nums;
}
int [] output = new int[nums.length - w + 1];
Deque<Integer> currentWindow = new ArrayDeque<>();
for (int i = 0; i < w; i++) {
currentWindow = SlidingWindowMaximum.cleanUp(i, currentWindow, nums);
currentWindow.add(i);
}
output[0] = nums[currentWindow.getFirst()];
for (int i = w; i < nums.length; i++) {
cleanUp(i, currentWindow, nums);
if (!currentWindow.isEmpty() && currentWindow.getFirst() <= (i - w)) {
currentWindow.removeFirst();
}
currentWindow.add(i);
output[i - w + 1] = nums[currentWindow.getFirst()];
}
return output;
}Longest Repeating Character Replacement
Given a string, s, and an integer, k, find the length of the longest substring in s, where all characters are identical, after replacing, at most, k characters with any other uppercase English character.
We iterate over the input string using two pointers.
In each iteration:
If the new character is not present in the hash map, we add it. Otherwise, we increment its frequency by 1.
We slide the window one step forward if the number of replacements required in the current window has exceeded our limit.
If the current window is the longest so far, then we update the length of the longest substring that has the same character.
Finally, we return the length of the longest substring with the same character after replacements. public static int longestRepeatingCharacterReplacement(String s, int k) {
// initialize variables
int stringLength = s.length();
int lengthOfMaxSubstring = 0;
int start = 0;
Map<Character, Integer> charFreq = new HashMap<>();
int mostFreqChar = 0;
// iterate over the input string
for (int end = 0; end < stringLength; ++end) {
char currentChar = s.charAt(end);
// if the new character is not in the hash map, add it, else increment its frequency
charFreq.put(currentChar, charFreq.getOrDefault(currentChar, 0) + 1);
// update the most frequent char
mostFreqChar = Math.max(mostFreqChar, charFreq.get(currentChar));
// if the number of replacements in the current window have exceeded the limit, slide the window
if (end - start + 1 - mostFreqChar > k) {
charFreq.put(s.charAt(start), charFreq.get(s.charAt(start)) - 1);
start += 1;
}
// if this window is the longest so far, update the length of max substring
lengthOfMaxSubstring = Math.max(lengthOfMaxSubstring, end - start + 1);
}
// return the length of the max substring with same characters after replacement(s)
return lengthOfMaxSubstring;
}Minimum Window Substring
Given two strings, s and t, find the minimum window substring in s, which has the following properties:
It is the shortest substring of s that includes all of the characters present in t. It must contain at least the same frequency of each character as in t. The order of the characters does not matter here.
// Function to find the minimum window in s that contains all characters of t
public static String minWindow(String s, String t) {
// If t is empty, return an empty string as no window is possible
if (t.isEmpty()) {
return “”;
}
// Maps to store the required character counts and the current window's character counts
Map<Character, Integer> reqCount = new HashMap<>();
Map<Character, Integer> window = new HashMap<>();
// Populate `reqCount` with the character frequencies of `t`
for (char c : t.toCharArray()) {
reqCount.put(c, reqCount.getOrDefault(c, 0) + 1);
}
// Variables to track the number of characters that match the required frequencies
int current = 0; // Count of characters in the current window that meet the required frequency
int required = reqCount.size(); // Total number of unique characters in `t`
// Result variables to track the best window
int[] res = {-1, -1}; // Stores the start and end indices of the minimum window
int resLen = Integer.MAX_VALUE; // Length of the minimum window
// Sliding window pointers
int left = 0; // Left pointer of the window
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
// If `c` is in `t`, update the window count
if (reqCount.containsKey(c)) {
window.put(c, window.getOrDefault(c, 0) + 1);
// If the frequency of `c` in the window matches the required frequency, update `current`
if (window.get(c).equals(reqCount.get(c))) {
current++;
}
}
// Try to contract the window while all required characters are present
while (current == required) {
// Update the result if the current window is smaller than the previous best
if ((right - left + 1) < resLen) {
res[0] = left;
res[1] = right;
resLen = (right - left + 1);
}
// Shrink the window from the left
char leftChar = s.charAt(left);
if (reqCount.containsKey(leftChar)) {
// Decrement the count of `leftChar` in the window
window.put(leftChar, window.get(leftChar) - 1);
// If the frequency of `leftChar` in the window is less than required, update `current`
if (window.get(leftChar) < reqCount.get(leftChar)) {
current--;
}
}
left++; // Move the left pointer to shrink the window
}
}
// Return the minimum window if found, otherwise return an empty string
return res[0] == -1 ? "" : s.substring(res[0], res[1] + 1);
}Longest Substring without Repeating Characters
Given a string, str, return the length of the longest substring without repeating characters.
Constraints:
11 ≤≤ str.length ≤≤ 105105 str consists of English letters, digits, symbols, and spaces.
Use a Map to store character indexes and jum to last seen + 1
Solution summary
To recap, the solution to this problem can be divided into the following parts:
* Traverse the input string
* Use a hash map to store elements along with their respective indexes.
* If the current element is present in the hash map, check whether it’s already present in the current window. If it is, we have found the end of the current window and the start of the next. We check if it’s longer than the longest window seen so far and update it accordingly.
* Store the current element in the hash map with the key as the element and the value as the current index.
* At the end of the traversal, we have the length of the longest substring with all distinct characters.
public static int findLongestSubstring(String str) {
// Check the length of input str
if (str.length() == 0) {
return 0;
}
int n = str.length();
int windowStart = 0, longest = 0, windowLength = 0, i = 0;
Hashtable <Character, Integer> lastSeenAt = new Hashtable <Character, Integer> ();
// Traverse input str to find the longest substring
// without repeating characters.
for (i = 0; i < n; i++) {
// If the current element is not present in the hash map,
// then store it in the hash map with the current index as the value.
if (!lastSeenAt.containsKey(str.charAt(i))) {
lastSeenAt.put(str.charAt(i), i);
} else {
// If the current element is present in the hash map,
// it means that this element may have appeared before.
// Check if the current element occurs before or after `windowStart`.
if (lastSeenAt.get(str.charAt(i)) >= windowStart) {
windowLength = i - windowStart;
if (longest < windowLength) {
longest = windowLength;
}
windowStart = lastSeenAt.get(str.charAt(i)) + 1;
}
// Update the last occurence of
// the element in the hash table
lastSeenAt.replace(str.charAt(i), i);
}
}
// Update the longest substring's
// length and starting index.
if (longest < i - windowStart) {
longest = i - windowStart;
}
return longest;
}Minimum Size Subarray Sum
Given an array of positive integers, nums, and a positive integer, target, find the minimum length of a contiguous subarray whose sum is greater than or equal to the target. If no such subarray is found, return 0.
public static int minSubArrayLen(int target, int[] nums) {
int windowSize = Integer.MAX_VALUE;
int currSubArrSize = 0;
int start = 0;
int sum = 0;
for (int end = 0; end < nums.length; end++) {
sum += nums[end];
while (sum >= target) {
currSubArrSize = (end + 1) - start;
windowSize = Math.min(windowSize, currSubArrSize);
sum -= nums[start];
start += 1;
}
}
if (windowSize != Integer.MAX_VALUE) {
return windowSize;
}
return 0;
}
Maximum Average Subarray I
Given an array of integers nums, and an integer k, return the maximum average of a contiguous subarray of length k.
// Method to find maximum average of subarray of length k
public static double findMaxAverage(int[] nums, int k) {
int currentSum = 0;
for (int i = 0; i < k; i++) {
currentSum += nums[i];
}
int maxSum = currentSum;
for (int i = k; i < nums.length; i++) {
currentSum += nums[i] - nums[i - k];
maxSum = Math.max(maxSum, currentSum);
}
return (double) maxSum / k;
}
Diet Plan Performance
A dieter consumes calories[i] calories on the i-th day.
Given an integer k, the dieter reviews their calorie intake over every sequence of k consecutive days (from calories[i] to calories[i+k-1] for all 0 <= i <= n-k). For each sequence, they calculate T, the total calories consumed over those k days:
If T is less than lower, the dieter performs poorly and loses 1 point. If T is greater than upper, the dieter performs better and gains 1 point. If T is between lower and upper (inclusive), the dieter’s performance is normal, and their points remain the same.
The dieter starts with zero points. Return the total points after the dieter follows this routine for all calories.length days. The total points can be negative.
// Function to calculate diet plan performance
public static int dietPlanPerformance(List<Integer> calories, int k, int lower, int upper) {
int points = 0;</Integer>
int currentSum = 0;
for (int i = 0; i < k; i++) {
currentSum += calories.get(i);
}
if (currentSum < lower) {
points -= 1;
} else if (currentSum > upper) {
points += 1;
}
for (int i = k; i < calories.size(); i++) {
currentSum = currentSum - calories.get(i - k) + calories.get(i);
if (currentSum < lower) {
points -= 1;
} else if (currentSum > upper) {
points += 1;
}
}
return points;
}Fruit Into Baskets
While visiting a farm of fruits, you have been given a row of fruits represented by an integer array, fruits, where fruits[i] is the type of fruit the ithith tree produces. You have to collect fruits, but there are some rules that you must follow while collecting fruits:
You are given only two baskets, each capable of holding an unlimited quantity of a single type of fruit. You can start collecting from any tree but must collect exactly one fruit from each tree (including the starting tree) while moving to the right. You must stop while encountering a tree with a fruit type that cannot fit into any of your baskets.
Return the maximum number of fruits you can collect following the above rules for the given array of fruits.
public static int totalFruit(int[] fruits) {
// Map to count the frequency of fruit types in the current window
Map<Integer, Integer> baskets = new HashMap<>();
// Maximum number of fruits collected so far
int collected = 0;
// Left boundary of the sliding window
int left = 0;
// Iterate over each tree (right boundary of the sliding window)
for (int right = 0; right < fruits.length; right++) {
// Add the current fruit to the baskets and increment its count
baskets.put(fruits[right], baskets.getOrDefault(fruits[right], 0) + 1);
// If there are more than two types of fruits in the baskets
while (baskets.size() > 2) {
// Decrease the count of the fruit at the left boundary
baskets.put(fruits[left], baskets.get(fruits[left]) - 1);
// Remove the fruit type from the baskets if its count becomes zero
if (baskets.get(fruits[left]) == 0) {
baskets.remove(fruits[left]);
}
// Move the left boundary to the right
left++;
}
// Update the maximum number of fruits collected
collected = Math.max(collected, right - left + 1);
}
// Return the maximum number of fruits that can be collected
return collected;
}Contains Duplicate II
You are given an integer array, nums, and an integer k. Determine whether two distinct indices, i and j, are in the array, such that nums[i] == nums[j] and the absolute difference between i and j is at most k. Return TRUE if such indices exist; otherwise, return FALSE.
The core intuition of solving this problem is maintaining a sliding window of size k to track elements within a limited range using a set. As we iterate through the array, we check if the current element already exists in the set, indicating a duplicate within the range. If it exists, we return TRUE. Otherwise, the element is added to the set. If the set size exceeds k, we remove the oldest element to ensure that the set only contains elements within the valid range at any time.
public static boolean containsNearbyDuplicate(int[] nums, int k) {
Set<Integer> seen = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
if (seen.contains(nums[i]))
return true;
seen.add(nums[i]);
if (seen.size() > k)
seen.remove(nums[i - k]);
}
return false;
}Frequency of the Most Frequent Element
You are given an integer array, nums, and an integer k, representing the maximum number of operations you can perform. In each operation, you may select any index in nums and increment its value by 1.
Your task is to determine the maximum possible frequency of a single element in the final array after performing at most k operations. You can choose to increase any elements in a way that results in one particular element appearing as often as possible (within k operations). For example, if nums = [2, 2, 3] and k = 4, you can increment the first and the second element, 2, once to match the third element, 3, achieving a maximum frequency of 3.
Return the highest frequency that can be achieved for any element in nums after at most k operations.
public static int maxFrequency(int[] nums, int k) {
Arrays.sort(nums);
int left = 0, maxFreq = 0;
long windowSum = 0;
for (int right = 0; right < nums.length; right++) {
long target = nums[right];
windowSum += target;
while ((right - left + 1) * target > windowSum + k) {
windowSum -= nums[left];
left++;
}
maxFreq = Math.max(maxFreq, right - left + 1);
}
return maxFreq;
}Subarrays with K Different Integers
You are given an integer array nums and an integer k. Your task is to return the number of good subarrays of nums.
A good subarray is a contiguous subarray that contains exactly k distinct integers. For example, in the array [1,2,3,1,2][1,2,3,1,2], the subarray [1,2,3][1,2,3]contains 33 distinct integers: 11, 22, and 33.
Number of subarrays with exactly k distinct integers=atMost(k)−atMost(k−1)
public class Solution {
// Main method to compute subarrays with exactly K distinct integers
public static int subarraysWithKDistinct(int[] nums, int k) {
return atMostK(nums, k) - atMostK(nums, k - 1);
}
// Helper function to count subarrays with at most K distinct integers
private static int atMostK(int[] nums, int k) {
int count = 0; // Total valid subarrays
int left = 0; // Left pointer of the sliding window
Map<Integer, Integer> freq = new HashMap<>(); // Frequency map for window
for (int right = 0; right < nums.length; right++) {
// If current element is new in the window, decrement k
freq.put(nums[right], freq.getOrDefault(nums[right], 0) + 1);
if (freq.get(nums[right]) == 1) {
k--;
}
// Shrink window from the left if distinct count exceeds k
while (k < 0) {
freq.put(nums[left], freq.get(nums[left]) - 1);
if (freq.get(nums[left]) == 0) {
k++; // One distinct element removed completely
}
left++; // Move left pointer forward
}
// All subarrays ending at 'right' and starting from 'left' are valid
count += right - left + 1;
}
return count;
}Count Subarrays With Score Less Than K
An array score is defined as the sum of the array elements multiplied by its length. For example, if the array is [2,1,5][2,1,5], then its score is (2+1+5)×3(2+1+5)×3 = 2424.
Given an array of positive integers, nums, and a positive integer k, count and return the number of non-empty subarrays of nums whose score is strictly less than k.
public long countSubarrays(int[] nums, long k) {
long result = 0; // Store the runningSum count of valid subarrays
long runningSum = 0; // Keeps the running sum of the current window
int left = 0; // Left boundary of the sliding window
// Expand the window by moving the right boundary one step at a time
for (int right = 0; right < nums.length; right++) {
runningSum += nums[right]; // Add the current element to the runningSum
// Calculate score for the current window
long score = runningSum * (right - left + 1);
// Shrink the window from the left until the score is less than k
// Score = runningSum sum * number of elements in the current window
while (left <= right && score >= k) {
runningSum -= nums[left]; // Subtract the leftmost element
left++; // Move the left boundary to the right
score = runningSum * (right - left + 1);
}
// All subarrays ending at 'right' and starting from 'left' to 'right' are valid
// Their count is (right - left + 1)
result += right - left + 1;
}
return result; // Return the runningSum count of valid subarrays
}
Count Substrings With K-Frequency Characters II
Given a string s and an integer k, return the total number of substrings of s where at least one character appears at least k times.
public long numberOfSubstrings(String s, int k) {
int n = s.length();
int[] freq = new int[26];
int charsWithK = 0;
long total = 0L;
int left = 0;
for (int right = 0; right < n; right++) {
int charFreqIdx = s.charAt(right) - 'a';
freq[charFreqIdx]++;
if (freq[charFreqIdx] == k) {
charsWithK++;
}
while (charsWithK > 0) {
total += (long) n - right;
int leftCharFreqIdx = s.charAt(left) - 'a';
if (freq[leftCharFreqIdx] == k) {
charsWithK--;
}
freq[leftCharFreqIdx]--;
left++;
}
}
return total;
}Substring with Concatenation of All Words
You are given a string, s, and an array of strings, words. All strings in words are of the same length.
A concatenated string is a string that contains all the words in words exactly once, in any order, concatenated together without any intervening characters.
Formally, a concatenated string is a permutation of all words joined together. For example, if words = [“ab”, “cd”, “ef”], then the following are all valid concatenated strings: “abcdef”, “abefcd”, “cdabef”, “cdefab”, “efabcd”, “efcdab”. However, “acdbef” is not valid because it is not formed by concatenating all the words in any order.
Your task is to return all starting indices of substrings in s that are concatenated strings.
You may return the indices in any order.
public static List<Integer> findSubstring(String s, String[] words) {
// Each word has the same length
int wordLen = words[0].length();
// Total number of words
int numWords = words.length;
// Total length of a valid substring (all words concatenated)
int totalLen = wordLen * numWords;</Integer>
// Frequency count of all words in the list
Map<String, Integer> wordCount = new HashMap<>();
for (String w : words) {
wordCount.put(w, wordCount.getOrDefault(w, 0) + 1);
}
// List to store all valid starting indices
List<Integer> result = new ArrayList<>();
// Check all possible starting offsets within word length range
for (int i = 0; i < wordLen; i++) {
int left = i; // Left pointer for sliding window
int right = i; // Right pointer for sliding window
Map<String, Integer> seen = new HashMap<>(); // Tracks words seen in the current window
// Slide the window across the string
while (right + wordLen <= s.length()) {
// Extract a word-sized substring
String word = s.substring(right, right + wordLen);
right += wordLen;
// If the word exists in the target list
if (wordCount.containsKey(word)) {
seen.put(word, seen.getOrDefault(word, 0) + 1); // Count it in the current window
// If we’ve seen a word too many times, shrink the window from the left
while (seen.get(word) > wordCount.get(word)) {
String leftWord = s.substring(left, left + wordLen);
seen.put(leftWord, seen.get(leftWord) - 1);
left += wordLen;
}
// If the total window matches the length of all words, record index
if (right - left == totalLen) {
result.add(left);
}
} else {
// Invalid word — reset the window
seen.clear();
left = right;
}
}
}Binary Subarrays With Sum
Let’s solve the Binary Subarrays With Sum problem using the Sliding Window pattern.
Statement
You are given a binary array, nums, and an integer, goal. Your task is to return the number of non-empty subarrays with a sum that meets the goal.
Constraints:
1≤1≤ nums.length ≤3×104≤3×104 nums[i] is either 00 or 11. 0≤0≤ goal ≤≤ nums.length
public int numSubarraysWithSum(int[] nums, int goal) {
int start = 0;
int prefixZeros = 0;
int currentSum = 0;
int totalCount = 0;
for (int end = 0; end < nums.length; end++) {
currentSum += nums[end];
// 1. Shrink window: If sum exceeds goal, contract from left
while (start <= end && currentSum > goal) {
currentSum -= nums[start];
start++;
prefixZeros = 0; // Reset count since we moved past the relevant segment
}
// 2. Count prefix zeros: If sum matches goal, count leading zeros
// These zeros allow for multiple valid subarrays ending at 'end'
while (start < end && nums[start] == 0 && currentSum == goal) {
prefixZeros++;
currentSum -= nums[start]; // Removing 0 doesn't change sum
start++;
}
// 3. Accumulate count if window is valid
if (start <= end && currentSum == goal) {
totalCount += 1 + prefixZeros;
}
}
return totalCount;
}
