The sliding window is a powerful algorithmic technique commonly used to solve problems that involve linear data structures like arrays or strings. It helps in reducing the time complexity of problems that require checking all possible subarrays or substrings.
Concept of the Sliding Window Technique
The sliding window technique involves creating a window that can slide over data to process elements in chunks. This window can be of a fixed size or can dynamically resize based on certain conditions. By moving this window across the data structure, we can perform operations on a subset of elements without repeatedly iterating over them.
- Window Size:
- Fixed-Size Window: The window remains the same size throughout processing.
- Dynamic-Size Window: The window size changes according to problem constraints.
When to Use the Sliding Window Technique
- Dealing with contiguous data sequences (subarrays or substrings).
- Optimizing problems where the goal is to find maximum, minimum, or specific conditions within a subarray or substring.
- Problems where a brute-force approach would be inefficient due to high time complexity.
Types of Sliding Window Techniques
- Fixed-Size Sliding Window
- Dynamic-Size Sliding Window
Let's dive into both types with examples written in JavaScript.
Examples in JavaScript
1. Fixed-Size Sliding Window
Problem: Find the maximum sum of any subarray of size k in an array.
Solution:
function maxSubarraySum(arr, k) {
const n = arr.length;
if (n < k) {
console.log("Invalid input: The array length is less than k.");
return null;
}
// Compute the sum of the first window of size k
let windowSum = 0;
for (let i = 0; i < k; i++) {
windowSum += arr[i];
}
let maxSum = windowSum;
// Slide the window from start to end
for (let i = k; i < n; i++) {
// Subtract the element going out and add the new element
windowSum += arr[i] - arr[i - k];
maxSum = Math.max(maxSum, windowSum);
}
return maxSum;
}
// Example usage:
const arr = [2, 5, 1, 8, 2, 9, 1];
const k = 3;
console.log(
"Maximum sum of a subarray of size",
k,
"is",
maxSubarraySum(arr, k)
);Explanation:
- Initialization: Calculate the sum of the first k elements as the initial window sum.
- Window Sliding:
- Iterate from index k to the end of the array.
- At each step, remove the element that's no longer in the window (arr[i — k]) and add the new element (arr[i]).
- Update maxSum if the current windowSum is greater than the previous maxSum.
Time Complexity:
- O(n), where n is the number of elements in the array.
2. Dynamic-Size Sliding Window
Problem: Find the length of the smallest subarray whose sum is greater than or equal to a given number S.
Solution:
function smallestSubarrayWithGivenSum(S, arr) {
let windowSum = 0,
minLength = Infinity,
windowStart = 0;
for (let windowEnd = 0; windowEnd < arr.length; windowEnd++) {
windowSum += arr[windowEnd]; // Add the next element
// Shrink the window as small as possible while the window's sum is larger than or equal to 'S'
while (windowSum >= S) {
minLength = Math.min(minLength, windowEnd - windowStart + 1);
windowSum -= arr[windowStart]; // Subtract the element going out
windowStart++; // Slide the window ahead
}
}
return minLength === Infinity ? 0 : minLength;
}
// Example usage:
const arr = [4, 2, 2, 7, 8, 1, 2, 8, 10];
const S = 8;
console.log(
"Length of the smallest subarray:",
smallestSubarrayWithGivenSum(S, arr)
);Explanation:
- Expand the Window: Move windowEnd forward, adding elements to windowSum until windowSum >= S.
- Shrink the Window: When windowSum >= S, move windowStart forward, subtracting elements from windowSum, to minimize the window size while still satisfying the condition.
- Update minLength: Keep track of the minimum window size that satisfies the condition.
Time Complexity:
- O(n), since each element is visited at most twice (once when windowEnd increases and once when windowStart increases).
3. Longest Substring Without Repeating Characters
Problem: Given a string, find the length of the longest substring without repeating characters.
Solution:
function lengthOfLongestSubstring(s) {
const charIndexMap = {};
let maxLength = 0,
windowStart = 0;
for (let windowEnd = 0; windowEnd < s.length; windowEnd++) {
const rightChar = s[windowEnd];
// If the character is already in the map and is in the current window
if (
charIndexMap[rightChar] !== undefined &&
charIndexMap[rightChar] >= windowStart
) {
// Move the window start next to the last occurrence of the current character
windowStart = charIndexMap[rightChar] + 1;
}
charIndexMap[rightChar] = windowEnd; // Update the last seen index
maxLength = Math.max(maxLength, windowEnd - windowStart + 1); // Update maxLength
}
return maxLength;
}
// Example usage:
const str = "pwwkew";
console.log(
"Length of the longest substring without repeating characters:",
lengthOfLongestSubstring(str)
);Explanation:
- Character Map: Use a hashmap (charIndexMap) to store the latest index of characters.
- Check for Repeats: If the character is found in the map and is within the current window, move windowStart to the right of the previous occurrence to avoid repeating characters.
- Update Max Length: Calculate the length of the current window and update maxLength if it's the longest so far.
Time Complexity:
- O(n), where n is the length of the string.
Benefits of the Sliding Window Technique
- Efficiency: Reduces the time complexity from O(n²) (in brute-force solutions) to O(n).
- Optimization: Offers a systematic method to handle a subset of data and optimize the code.
- Simplicity: Helps in writing cleaner and more understandable code.
Common Problems Suitable for Sliding Window
- Maximum Sum Subarray of Size K
- Longest Substring with K Distinct Characters
- Permutation in a String
- Longest Repeating Character Replacement
- Longest Subarray with Ones after Replacement
Tips for Implementing Sliding Window
- Initialize Pointers: Typically, windowStart and windowEnd.
- Condition Checks: Determine when to expand or shrink the window based on problem-specific conditions.
- Data Structures: Use auxiliary data structures like hash maps or sets when necessary to keep track of elements within the window.
- Edge Cases: Always consider empty inputs, invalid values, or cases where no solution exists.
Practice Problems
To master the sliding window technique, practice the following problems: