Skip to main content

Sliding Window Pattern

The Sliding Window pattern is used to solve array/string problems efficiently by maintaining a "window" that slides through the data.

What is Sliding Window?​

The Sliding Window pattern involves creating a window which can either be an array or number from one position to another. The window can either grow or shrink, and it helps us track a subset of data in an array/string.

When to Use?​

  • Problems involving arrays or strings where you need to find/calculate something among contiguous subarrays or substrings
  • When you need to maintain a set of elements that satisfy given constraints
  • When dealing with problems that require tracking a continuous sequence

Common Applications​

  • Finding longest/shortest substring with certain conditions
  • Finding max/min sum of k consecutive elements
  • Finding longest array with sum less than or equal to k
  • Calculating moving averages

Time Complexity​

Most sliding window solutions achieve O(n) time complexity, where n is the size of the input array/string.

Example Problems​

1. Maximum Sum Subarray of Size K​

Find the maximum sum of any contiguous subarray of size k.

Problem Description​

Given an array of integers and a number k, find the maximum sum of k consecutive elements in the array.

Example​

Input: [2, 1, 5, 1, 3, 2], k = 3
Output: 9
Explanation: Subarray with maximum sum is [5, 1, 3]

Solution​

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

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

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

	return maxSum;
}

Time Complexity​

  • Time: O(n) where n is the length of the array
  • Space: O(1)

2. Longest Substring Without Repeating Characters​

Find the length of the longest substring without repeating characters.

Problem Description​

Given a string, find the length of the longest substring that contains no repeating characters.

Example​

Input: "abcabcbb"
Output: 3
Explanation: The longest substring is "abc"

Input: "bbbbb"
Output: 1
Explanation: The longest substring is "b"

Solution​

function lengthOfLongestSubstring(str) {
	let windowStart = 0;
	let maxLength = 0;
	let charMap = new Map();

	for (let windowEnd = 0; windowEnd < str.length; windowEnd++) {
		const rightChar = str[windowEnd];

		// If character exists in current window
		if (charMap.has(rightChar)) {
			// Move window start to position after the last occurrence
			windowStart = Math.max(windowStart, charMap.get(rightChar) + 1);
		}

		// Add/update character position
		charMap.set(rightChar, windowEnd);

		// Update maximum length
		maxLength = Math.max(maxLength, windowEnd - windowStart + 1);
	}

	return maxLength;
}

Time Complexity​

  • Time: O(n) where n is the length of the string
  • Space: O(min(m, n)) where m is the size of the character set

Practice Problems​

To master the sliding window pattern, try solving these problems:

  1. Find all subarrays of size k with average greater than a given value
  2. Minimum size subarray sum
  3. Longest substring with k distinct characters
  4. Find all anagrams in a string
  5. Maximum fruits into baskets

Additional Resources​