Quick Overview
Recomputing each subarray from scratch is `O(N^2)`. A sliding window adds the entering element and subtracts the leaving one, so each step is `O(1)` and the whole scan finishes in `O(N)`.
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")
K elements at every step keeps the complexity at O(N × K). Only add the incoming item and subtract the outgoing item in O(1)!Use sliding windows on contiguous subarrays and substrings. Next, let's explore Singly and Doubly Linked Lists!
Big O describes how work grows, not how long it takes. An `O(N^2)` algorithm on 1,000 items does a million steps; the same work at `O(N log N)` does about 10,000.
A dynamic array doubles rather than growing by one, so the expensive copy lands on the 1st, 2nd, 4th and 8th push. Averaged across every push, that is `O(1)` amortised.
A nested loop tests every pair in `O(N^2)`. On sorted data, moving two pointers inward from both ends rules out half the remaining candidates at each step and settles it in one `O(N)` pass.
Average 5.0 by 1 learner