Sliding Window Technique - Complete Guide

The sliding window technique is a powerful algorithmic pattern used to solve array and string problems efficiently. It reduces time complexity from O(n²) or O(n³) to O(n) in many cases.

What is the Sliding Window Technique? #

The sliding window technique involves creating a “window” that slides over the data structure (usually an array or string) to examine subsets of elements. Instead of recalculating from scratch for each position, we efficiently update the window by adding new elements and removing old ones.

When to Use Sliding Window #

Use sliding window when:

Problem involves contiguous subarrays or substrings
You need to find maximum, minimum, or target sum/length
Problem asks about all subarrays of size k
Looking for longest/shortest substring with conditions

Types of Sliding Window #

1. Fixed Size Window #

The window size remains constant as it slides.

2. Dynamic Size Window #

The window size changes based on conditions.

Fixed Size Window Problems #

Maximum Sum of Subarray of Size K #

Problem: Find maximum sum of any contiguous subarray of size k.

Brute Force (O(n×k)):

function maxSumBruteForce(arr, k) {
  let maxSum = -Infinity;

  for (let i = 0; i <= arr.length - k; i++) {
    let sum = 0;
    for (let j = i; j < i + k; j++) {
      sum += arr[j];
    }
    maxSum = Math.max(maxSum, sum);
  }

  return maxSum;
}

Sliding Window (O(n)):

function maxSum(arr, k) {
  if (arr.length < k) return null;

  // Calculate sum of first window
  let windowSum = 0;
  for (let i = 0; i < k; i++) {
    windowSum += arr[i];
  }

  let maxSum = windowSum;

  // Slide the window
  for (let i = k; i < arr.length; i++) {
    windowSum = windowSum - arr[i - k] + arr[i];
    maxSum = Math.max(maxSum, windowSum);
  }

  return maxSum;
}

console.log(maxSum([2, 1, 5, 1, 3, 2], 3));  // 9 (5+1+3)
console.log(maxSum([2, 3, 4, 1, 5], 2));  // 7 (3+4)

Average of Subarrays of Size K #

function findAverages(arr, k) {
  const result = [];
  let windowSum = 0;

  for (let i = 0; i < arr.length; i++) {
    windowSum += arr[i];

    if (i >= k - 1) {
      result.push(windowSum / k);
      windowSum -= arr[i - k + 1];
    }
  }

  return result;
}

console.log(findAverages([1, 3, 2, 6, -1, 4, 1, 8, 2], 5));
// [2.2, 2.8, 2.4, 3.6, 2.8]

Maximum of All Subarrays of Size K #

function maxOfSubarrays(arr, k) {
  const result = [];
  const deque = [];  // Store indices

  for (let i = 0; i < arr.length; i++) {
    // Remove elements outside window
    while (deque.length > 0 && deque[0] <= i - k) {
      deque.shift();
    }

    // Remove smaller elements from back
    while (deque.length > 0 && arr[deque[deque.length - 1]] < arr[i]) {
      deque.pop();
    }

    deque.push(i);

    // Add to result when window is complete
    if (i >= k - 1) {
      result.push(arr[deque[0]]);
    }
  }

  return result;
}

console.log(maxOfSubarrays([1, 3, -1, -3, 5, 3, 6, 7], 3));
// [3, 3, 5, 5, 6, 7]

Dynamic Size Window Problems #

Longest Substring with K Distinct Characters #

function longestSubstringKDistinct(s, k) {
  const map = new Map();
  let left = 0;
  let maxLen = 0;

  for (let right = 0; right < s.length; right++) {
    const char = s[right];
    map.set(char, (map.get(char) || 0) + 1);

    // Shrink window if more than k distinct
    while (map.size > k) {
      const leftChar = s[left];
      map.set(leftChar, map.get(leftChar) - 1);
      if (map.get(leftChar) === 0) {
        map.delete(leftChar);
      }
      left++;
    }

    maxLen = Math.max(maxLen, right - left + 1);
  }

  return maxLen;
}

console.log(longestSubstringKDistinct("araaci", 2));  // 4 ("araa")
console.log(longestSubstringKDistinct("cbbebi", 3));  // 5 ("cbbeb")

Minimum Window Substring #

Problem: Find the smallest substring containing all characters of a target string.

function minWindow(s, t) {
  const need = new Map();
  const window = new Map();

  for (const char of t) {
    need.set(char, (need.get(char) || 0) + 1);
  }

  let left = 0;
  let right = 0;
  let valid = 0;
  let start = 0;
  let minLen = Infinity;

  while (right < s.length) {
    const char = s[right];
    right++;

    if (need.has(char)) {
      window.set(char, (window.get(char) || 0) + 1);
      if (window.get(char) === need.get(char)) {
        valid++;
      }
    }

    while (valid === need.size) {
      if (right - left < minLen) {
        start = left;
        minLen = right - left;
      }

      const leftChar = s[left];
      left++;

      if (need.has(leftChar)) {
        if (window.get(leftChar) === need.get(leftChar)) {
          valid--;
        }
        window.set(leftChar, window.get(leftChar) - 1);
      }
    }
  }

  return minLen === Infinity ? "" : s.substring(start, start + minLen);
}

console.log(minWindow("ADOBECODEBANC", "ABC"));  // "BANC"

Longest Substring Without Repeating Characters #

function lengthOfLongestSubstring(s) {
  const set = new Set();
  let left = 0;
  let maxLen = 0;

  for (let right = 0; right < s.length; right++) {
    while (set.has(s[right])) {
      set.delete(s[left]);
      left++;
    }

    set.add(s[right]);
    maxLen = Math.max(maxLen, right - left + 1);
  }

  return maxLen;
}

console.log(lengthOfLongestSubstring("abcabcbb"));  // 3 ("abc")
console.log(lengthOfLongestSubstring("pwwkew"));  // 3 ("wke")

Smallest Subarray with Sum >= Target #

function minSubArrayLen(target, nums) {
  let left = 0;
  let sum = 0;
  let 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];
      left++;
    }
  }

  return minLen === Infinity ? 0 : minLen;
}

console.log(minSubArrayLen(7, [2, 3, 1, 2, 4, 3]));  // 2 ([4,3])
console.log(minSubArrayLen(11, [1, 2, 3, 4, 5]));  // 3 ([3,4,5])

Maximum Consecutive Ones III #

Problem: Find longest subarray with at most k zeros flipped to ones.

function longestOnes(nums, k) {
  let left = 0;
  let zeros = 0;
  let 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;
}

console.log(longestOnes([1,1,1,0,0,0,1,1,1,1,0], 2));  // 6
console.log(longestOnes([0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], 3));  // 10

Sliding Window with Two Pointers Pattern #

Fruits Into Baskets #

Problem: Pick maximum fruits with at most 2 types.

function totalFruit(fruits) {
  const basket = new Map();
  let left = 0;
  let maxFruits = 0;

  for (let right = 0; right < fruits.length; right++) {
    basket.set(fruits[right], (basket.get(fruits[right]) || 0) + 1);

    while (basket.size > 2) {
      basket.set(fruits[left], basket.get(fruits[left]) - 1);
      if (basket.get(fruits[left]) === 0) {
        basket.delete(fruits[left]);
      }
      left++;
    }

    maxFruits = Math.max(maxFruits, right - left + 1);
  }

  return maxFruits;
}

console.log(totalFruit([1,2,1]));  // 3
console.log(totalFruit([0,1,2,2]));  // 3
console.log(totalFruit([1,2,3,2,2]));  // 4

Permutation in String #

Problem: Check if s2 contains permutation of s1.

function checkInclusion(s1, s2) {
  if (s1.length > s2.length) return false;

  const need = new Map();
  const window = new Map();

  for (const char of s1) {
    need.set(char, (need.get(char) || 0) + 1);
  }

  let left = 0;
  let right = 0;
  let valid = 0;

  while (right < s2.length) {
    const char = s2[right];
    right++;

    if (need.has(char)) {
      window.set(char, (window.get(char) || 0) + 1);
      if (window.get(char) === need.get(char)) {
        valid++;
      }
    }

    while (right - left >= s1.length) {
      if (valid === need.size) {
        return true;
      }

      const leftChar = s2[left];
      left++;

      if (need.has(leftChar)) {
        if (window.get(leftChar) === need.get(leftChar)) {
          valid--;
        }
        window.set(leftChar, window.get(leftChar) - 1);
      }
    }
  }

  return false;
}

console.log(checkInclusion("ab", "eidbaooo"));  // true
console.log(checkInclusion("ab", "eidboaoo"));  // false

Sliding Window Template #

Template for Most Problems #

function slidingWindow(s) {
  const window = new Map();
  let left = 0;
  let right = 0;

  while (right < s.length) {
    // Expand window
    const char = s[right];
    right++;
    // Update window data
    window.set(char, (window.get(char) || 0) + 1);

    // Check if we need to shrink
    while (needToShrink()) {
      // Shrink window
      const leftChar = s[left];
      left++;
      // Update window data
      window.set(leftChar, window.get(leftChar) - 1);
    }

    // Update result
  }

  return result;
}

Time and Space Complexity #

Approach	Time Complexity	Space Complexity
Brute Force	O(n²) or O(n³)	O(1)
Sliding Window	O(n)	O(k) or O(1)

Where k is the window size or distinct characters.

Tips for Solving Sliding Window Problems #

Identify the pattern - Look for subarray/substring keywords
Choose window type - Fixed or dynamic size
Define window state - What data to track (sum, count, map)
Expand window - Add elements to the right
Shrink window - Remove elements from the left when needed
Update result - Track maximum, minimum, or count

Common Mistakes to Avoid #

Not checking edge cases (empty array, k > length)
Forgetting to update window state when shrinking
Using wrong loop conditions
Not handling duplicate elements properly
Confusing left/right pointer movements

The sliding window technique is essential for technical interviews and appears frequently on platforms like LeetCode. Master this pattern to solve array and string problems efficiently.