Sliding Window

Use a variable-size sliding window: expand the right boundary to increase the sum, and shrink the left boundary when the sum meets the target.

function minSubarrayLen(target, nums) {
    let left = 0, sum = 0, minLen = Infinity;
    for (let right = 0; right < nums.length; right++) {
        sum += nums[right];
        while (sum >= target) {
            minLen = Math.min(minLen, right - left + 1);
            sum -= nums[left++];
        }
    }
    return minLen === Infinity ? 0 : minLen;
}
// minSubarrayLen(7, [2,3,1,2,4,3]) => 2 (subarray [4,3])

Time: O(n)  |  Space: O(1)

Use a sliding window with a Set to track characters. Expand right, and if a duplicate is found, shrink from the left until no duplicates remain.

function lengthOfLongestSubstring(s) {
    const set = new Set();
    let left = 0, maxLen = 0;
    for (let right = 0; right < s.length; right++) {
        while (set.has(s[right])) {
            set.delete(s[left++]);
        }
        set.add(s[right]);
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}
// lengthOfLongestSubstring("abcabcbb") => 3 ("abc")

Time: O(n)  |  Space: O(min(n, alphabet))

Sliding window: expand right, count zeros. When zeros exceed k, shrink from the left until zeros ≤ k again.

function longestOnes(nums, k) {
    let left = 0, zeros = 0, maxLen = 0;
    for (let right = 0; right < nums.length; right++) {
        if (nums[right] === 0) zeros++;
        while (zeros > k) {
            if (nums[left] === 0) zeros--;
            left++;
        }
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}
// longestOnes([1,1,0,0,1,1,1,0,1], 2) => 6

Time: O(n)  |  Space: O(1)

Find the longest subarray with at most 2 distinct elements (fruit types). Use a sliding window with a frequency map.

function totalFruit(fruits) {
    const map = new Map();
    let left = 0, maxLen = 0;
    for (let right = 0; right < fruits.length; right++) {
        map.set(fruits[right], (map.get(fruits[right]) || 0) + 1);
        while (map.size > 2) {
            const f = fruits[left];
            map.set(f, map.get(f) - 1);
            if (map.get(f) === 0) map.delete(f);
            left++;
        }
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}
// totalFruit([1,2,3,2,2]) => 4

Time: O(n)  |  Space: O(1) (at most 3 keys in map)

Use a fixed window of size s1.length on s2. Track character frequencies and compare with s1 frequencies.

function checkInclusion(s1, s2) {
    if (s1.length > s2.length) return false;
    const count = new Array(26).fill(0);
    for (let i = 0; i < s1.length; i++) {
        count[s1.charCodeAt(i) - 97]++;
        count[s2.charCodeAt(i) - 97]--;
    }
    if (count.every(c => c === 0)) return true;
    for (let i = s1.length; i < s2.length; i++) {
        count[s2.charCodeAt(i) - 97]--;
        count[s2.charCodeAt(i - s1.length) - 97]++;
        if (count.every(c => c === 0)) return true;
    }
    return false;
}
// checkInclusion("ab", "eidbaooo") => true

Time: O(n)  |  Space: O(1)

Use a variable sliding window with a frequency map. Expand right to include characters, shrink left to find the minimum valid window.

function minWindow(s, t) {
    const need = new Map();
    for (const c of t) need.set(c, (need.get(c) || 0) + 1);
    let left = 0, have = 0, required = need.size;
    let minLen = Infinity, result = "";
    const window = new Map();
    for (let right = 0; right < s.length; right++) {
        const c = s[right];
        window.set(c, (window.get(c) || 0) + 1);
        if (need.has(c) && window.get(c) === need.get(c)) have++;
        while (have === required) {
            if (right - left + 1 < minLen) {
                minLen = right - left + 1;
                result = s.slice(left, right + 1);
            }
            const d = s[left++];
            window.set(d, window.get(d) - 1);
            if (need.has(d) && window.get(d) < need.get(d)) have--;
        }
    }
    return result;
}

Time: O(m + n)  |  Space: O(m + n)

Find the longest substring where you can replace at most k characters to make all characters the same. Track the count of the most frequent character in the window.

function characterReplacement(s, k) {
    const count = new Array(26).fill(0);
    let left = 0, maxFreq = 0, maxLen = 0;
    for (let right = 0; right < s.length; right++) {
        count[s.charCodeAt(right) - 65]++;
        maxFreq = Math.max(maxFreq, count[s.charCodeAt(right) - 65]);
        while ((right - left + 1) - maxFreq > k) {
            count[s.charCodeAt(left) - 65]--;
            left++;
        }
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}
// characterReplacement("AABABBA", 1) => 4

Time: O(n)  |  Space: O(1)

Use the trick: exactly(k) = atMost(k) - atMost(k-1). Implement atMost(k) with a sliding window.

function subarraysWithKDistinct(nums, k) {
    return atMost(nums, k) - atMost(nums, k - 1);
}
function atMost(nums, k) {
    const map = new Map();
    let left = 0, count = 0;
    for (let right = 0; right < nums.length; right++) {
        map.set(nums[right], (map.get(nums[right]) || 0) + 1);
        while (map.size > k) {
            const v = nums[left];
            map.set(v, map.get(v) - 1);
            if (map.get(v) === 0) map.delete(v);
            left++;
        }
        count += right - left + 1;
    }
    return count;
}
// subarraysWithKDistinct([1,2,1,2,3], 2) => 7

Time: O(n)  |  Space: O(k)

Find the maximum in each window of size k. Use a deque (monotonic decreasing) to track the index of potential maximums efficiently.

function maxSlidingWindow(nums, k) {
    const deque = [], result = [];
    for (let i = 0; i < nums.length; i++) {
        // Remove indices outside the window
        if (deque.length && deque[0] < i - k + 1) deque.shift();
        // Remove smaller elements from back
        while (deque.length && nums[deque[deque.length-1]] < nums[i])
            deque.pop();
        deque.push(i);
        if (i >= k - 1) result.push(nums[deque[0]]);
    }
    return result;
}
// maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3)
// => [3,3,5,5,6,7]

Time: O(n)  |  Space: O(k)

Expand the window. Track the most frequent character count in the window. If (window size - max freq) > k, shrink from left.

function characterReplacement(s, k) {
    const freq = {};
    let left = 0, maxFreq = 0, best = 0;
    for (let right = 0; right < s.length; right++) {
        freq[s[right]] = (freq[s[right]] || 0) + 1;
        maxFreq = Math.max(maxFreq, freq[s[right]]);
        // If replacements needed exceed k, shrink window
        if (right - left + 1 - maxFreq > k) {
            freq[s[left]]--;
            left++;
        }
        best = Math.max(best, right - left + 1);
    }
    return best;
}
// Input: s="AABABBA", k=1  => Output: 4  ("AABA" or "ABBA")
// Input: s="ABAB", k=2     => Output: 4  (replace both B's or A's)

Time: O(n)  |  Space: O(26) = O(1)

Use a sliding window of size k with a frequency map. Track distinct characters. Count windows where distinct ≤ j.

function countSubstringsAtMostK(s, k, j) {
    const freq = new Map();
    let left = 0, count = 0;
    for (let right = 0; right < s.length; right++) {
        freq.set(s[right], (freq.get(s[right]) || 0) + 1);
        while (freq.size > j) {
            const lc = s[left];
            freq.set(lc, freq.get(lc) - 1);
            if (freq.get(lc) === 0) freq.delete(lc);
            left++;
        }
        // All subarrays ending at right with distinct <= j
        count += right - left + 1;
    }
    return count;
}
// subarrays with exactly k distinct: atMostK(k) - atMostK(k-1)
function subarraysWithExactlyK(s, k) {
    return countSubstringsAtMostK(s, s.length, k)
         - countSubstringsAtMostK(s, s.length, k - 1);
}
// Input: s="araaci", k=2  => Output: 4 windows with exactly 2 distinct chars

Time: O(n)  |  Space: O(k)

Convert 0s to -1. Now the problem becomes: find the longest subarray with sum 0. Use a prefix sum + hash map approach — variable-size sliding window.

function findMaxLength(nums) {
    const map = new Map([[0, -1]]); // prefixSum -> first index
    let sum = 0, maxLen = 0;
    for (let i = 0; i < nums.length; i++) {
        sum += nums[i] === 1 ? 1 : -1; // convert 0 to -1
        if (map.has(sum)) {
            maxLen = Math.max(maxLen, i - map.get(sum));
        } else {
            map.set(sum, i); // only record first occurrence
        }
    }
    return maxLen;
}
// Input: [0,1]           => Output: 2
// Input: [0,1,0]         => Output: 2
// Input: [0,0,1,0,0,0,1,1] => Output: 6

Time: O(n)  |  Space: O(n)

Use a variable sliding window. Expand right, multiply. When product >= k, shrink left by dividing. Count windows: each right pointer gives (right - left + 1) valid subarrays.

function numSubarrayProductLessThanK(nums, k) {
    if (k <= 1) return 0;
    let product = 1, left = 0, count = 0;
    for (let right = 0; right < nums.length; right++) {
        product *= nums[right];
        while (product >= k) product /= nums[left++];
        count += right - left + 1;
    }
    return count;
}
// Input: nums=[10,5,2,6], k=100   => Output: 8
//   Subarrays: [10],[5],[2],[6],[10,5],[5,2],[2,6],[5,2,6]
// Input: nums=[1,2,3], k=0        => Output: 0

Time: O(n)  |  Space: O(1)

Use a deque to efficiently find the minimum subarray of length ≥ some size with sum ≥ target using prefix sums.

function shortestSubarray(nums, k) {
    const n = nums.length;
    const prefix = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];
    let result = Infinity;
    const deque = []; // stores indices of prefix sum in increasing order
    for (let i = 0; i <= n; i++) {
        // Delete front while subarray sum >= k
        while (deque.length && prefix[i] - prefix[deque[0]] >= k) {
            result = Math.min(result, i - deque.shift());
        }
        // Maintain increasing deque
        while (deque.length && prefix[deque[deque.length-1]] >= prefix[i]) {
            deque.pop();
        }
        deque.push(i);
    }
    return result === Infinity ? -1 : result;
}
// Input: nums=[2,-1,2], k=3   => Output: 3  (whole array)
// Input: nums=[1,2], k=4      => Output: -1

Time: O(n)  |  Space: O(n)

Use a fixed-size sliding window with a frequency map. Maintain a counter of duplicates. A window is valid when duplicates = 0.

function countKLengthNoDup(arr, k) {
    const freq = new Map();
    let dupCount = 0, result = 0;
    for (let i = 0; i < arr.length; i++) {
        // Add right element
        freq.set(arr[i], (freq.get(arr[i]) || 0) + 1);
        if (freq.get(arr[i]) === 2) dupCount++; // new duplicate
        // Shrink from left when window exceeds k
        if (i >= k) {
            if (freq.get(arr[i - k]) === 2) dupCount--;
            freq.set(arr[i - k], freq.get(arr[i - k]) - 1);
        }
        if (i >= k - 1 && dupCount === 0) result++;
    }
    return result;
}
// Input: arr=[1,2,3,1,2,3], k=3  => Output: 2  ([1,2,3] at index 0 and 3)
// Input: arr=[2,2,2,2], k=2      => Output: 0  (all windows have dups)

Time: O(n)  |  Space: O(k)

Use a fixed sliding window. Count vowels in the first k characters, then slide: add the new character's vowel contribution, subtract the removed character's.

function maxVowels(s, k) {
    const vowels = new Set(['a','e','i','o','u']);
    let count = 0;
    for (let i = 0; i < k; i++) if (vowels.has(s[i])) count++;
    let maxCount = count;
    for (let i = k; i < s.length; i++) {
        if (vowels.has(s[i]))   count++;
        if (vowels.has(s[i-k])) count--;
        maxCount = Math.max(maxCount, count);
    }
    return maxCount;
}
// Input: s="abciiidef", k=3   => Output: 3  (window "iii")
// Input: s="aeiou", k=2       => Output: 2
// Input: s="leetcode", k=3    => Output: 2  ("lee" or "eet")

Time: O(n)  |  Space: O(1)

Take k cards total from either end. The optimal strategy leaves a window of (n-k) cards in the middle untouched. Minimize the middle window sum = maximize remaining sum.

function maxScore(cardPoints, k) {
    const n = cardPoints.length;
    const totalSum = cardPoints.reduce((a, b) => a + b, 0);
    // Find minimum sum of window of size (n-k)
    let windowSum = 0, minWindowSum = Infinity;
    for (let i = 0; i < n - k; i++) windowSum += cardPoints[i];
    minWindowSum = windowSum;
    for (let i = n - k; i < n; i++) {
        windowSum += cardPoints[i] - cardPoints[i - (n - k)];
        minWindowSum = Math.min(minWindowSum, windowSum);
    }
    return totalSum - minWindowSum;
}
// Input: cardPoints=[1,2,3,4,5,6,1], k=3   => Output: 12  (6+5+1 from ends)
// Input: cardPoints=[2,2,2], k=2            => Output: 4

Time: O(n)  |  Space: O(1)

Variable sliding window: expand right to grow sum, shrink left to minimize length while maintaining sum >= target.

function minSubArrayLen(target, nums) {
    let left = 0, sum = 0, minLen = Infinity;
    for (let right = 0; right < nums.length; right++) {
        sum += nums[right];
        while (sum >= target) {
            minLen = Math.min(minLen, right - left + 1);
            sum -= nums[left++]; // shrink from left
        }
    }
    return minLen === Infinity ? 0 : minLen;
}
// Input: target=7, nums=[2,3,1,2,4,3]   => Output: 2  ([4,3])
// Input: target=4, nums=[1,4,4]          => Output: 1  ([4])
// Input: target=11, nums=[1,1,1,1,1,1]  => Output: 0  (impossible)

Time: O(n)  |  Space: O(1)

Variable sliding window: expand right adding elements, shrink from left when sum exceeds k. Track the maximum window length where sum ≤ k.

function longestSubarrayAtMostK(nums, k) {
    let left = 0, sum = 0, maxLen = 0;
    for (let right = 0; right < nums.length; right++) {
        sum += nums[right];
        while (sum > k && left <= right) {
            sum -= nums[left++];
        }
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}
// Input: nums=[3,1,2,1,1], k=5   => Output: 4  ([1,2,1,1])
// Input: nums=[4,1,1,2], k=4     => Output: 3  ([1,1,2])
// Input: nums=[5,5], k=3         => Output: 0  (no subarray works)

Time: O(n)  |  Space: O(1)

Count total 1s (= window size). Find the minimum 0s in any window of that size — each 0 is a swap needed to bring a 1 in.

function minSwaps(nums) {
    const ones = nums.reduce((a, b) => a + b, 0);
    if (ones === 0) return 0;
    // Count 0s in first window of size 'ones'
    let zeros = 0;
    for (let i = 0; i < ones; i++) if (nums[i] === 0) zeros++;
    let minZeros = zeros;
    // Slide window on circular array (duplicate for circular)
    const n = nums.length;
    for (let i = ones; i < n + ones; i++) {
        if (nums[i % n] === 0) zeros++;
        if (nums[(i - ones) % n] === 0) zeros--;
        minZeros = Math.min(minZeros, zeros);
    }
    return minZeros;
}
// Input: [0,1,0,1,1,0,0]  => Output: 1  (swap one 0 into the window of 3 ones)
// Input: [1,0,1,0,1]      => Output: 1

Time: O(n)  |  Space: O(1)

Use a fixed-size sliding window of length p. Compare sorted (or frequency map) of window with sorted pattern. Record start index when they match.

function findPermutationIndices(s, p) {
    const result = [];
    if (p.length > s.length) return result;
    const pSorted = p.split('').sort().join('');
    for (let i = 0; i <= s.length - p.length; i++) {
        if (s.slice(i, i + p.length).split('').sort().join('') === pSorted) {
            result.push(i);
        }
    }
    return result;
}
// Optimized O(n) using frequency array (same as findAnagrams):
// Input: s="eidbaooo", p="ab"  => Output: [3]  ("ba" at index 3)
// Input: s="cbaebabacd", p="abc" => Output: [0,6]

Time: O(n × k log k) naive, O(n) optimized  |  Space: O(k)