Master the sliding window technique to optimize subarray and substring problems from O(N^2) quadratic to O(N) linear time.
Learn how dynamic arrays achieve O(1) amortized insertion, contiguous memory layout, and geometric doubling strategies.
The Sliding Window Pattern maintains a contiguous sub-range (window) over an array or string. As the window moves, elements enter from the right and leave from the left.
Find the maximum sum of any contiguous subarray of fixed size k:
function maxSubarraySum(arr, k) {
if (arr.length < k) return null;
let maxSum = 0;
let windowSum = 0;
// Step 1: Calculate sum of the very first window of size k
for (let i = 0; i < k; i++) {
windowSum += arr[i];
}
maxSum = windowSum;
// Step 2: Slide the window across the rest of the array
for (let i = k; i < arr.length; i++) {
// Add incoming right element, subtract outgoing left element
windowSum += arr[i] - arr[i - k];
maxSum = Math.max(maxSum, windowSum);
}
return maxSum;
}
// Example: k = 3
console.log(maxSubarraySum([2, 1, 5, 1, 3, 2], 3)); // Output: 9 (subarray [5, 1, 3])
Initial Window [k=3]: [ 2 , 1 , 5 ] , 1 , 3 , 2 Sum = 8
Slide Window: 2 , [ 1 , 5 , 1 ] , 3 , 2 Sum = 8 - 2 + 1 = 7
Slide Window: 2 , 1 , [ 5 , 1 , 3 ] , 2 Sum = 7 - 1 + 3 = 9 (MAX!)
For dynamic windows, expand right to grow the window, and contract left when the window constraint is violated:
function lengthOfLongestSubstring(s) {
const seen = new Set();
let left = 0;
let maxLength = 0;
for (let right = 0; right < s.length; right++) {
while (seen.has(s[right])) {
seen.delete(s[left]);
left++; // Contract window from the left until duplicate is removed
}
seen.add(s[right]);
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}
console.log(lengthOfLongestSubstring("abcabcbb")); // Output: 3 ("abc")
Use sliding windows on contiguous subarrays and substrings. Next, let's explore Singly and Doubly Linked Lists!