Mastery Points
0
Sliding Window Pattern in dsa
Context & Logic
Sliding Window technique is used to solve problems that involve arrays or strings by maintaining a 'window' (range of elements) that slides over the data structure.
Example
// Example: Max sum of window size k
function maxWindowSum(arr, k) {
let maxSum = 0, currentSum = 0;
for (let i = 0; i < k; i++) currentSum += arr[i];
maxSum = currentSum;
for (let i = k; i < arr.length; i++) {
currentSum += arr[i] - arr[i-k];
maxSum = Math.max(maxSum, currentSum);
}
return maxSum;
}Step-by-Step Logic
1
Define the window size (fixed or variable).
2
Calculate the value for the first window.
3
Slide the window by adding the next element and removing the first element of the previous window.
4
Keep track of the optimal value (max, min, etc.) found during the process.
Complexity Metrics
Time Efficiency
O(n)
Memory Footprint
O(1) usually