A collection of TypeScript sliding window algorithm implementations for common array and string processing tasks, optimized for O(n) time complexity.
/**
* Sliding Window Algorithm Utilities
* Time-efficient solutions for subarray and substring problems
*/
type SlidingWindowResult<T> = {
value: T;
startIndex: number;
endIndex: number;
};
/**
* Finds the maximum sum of any contiguous subarray of size k
* Time Complexity: O(n) - single pass through array
* Space Complexity: O(1) - constant extra space
*
* @param arr - Array of numbers
* @param k - Window size (must be positive and <= arr.length)
* @returns Object containing max sum and window indices, or null if invalid input
*/
function maxSumSubarray(
arr: number[],
k: number
): SlidingWindowResult<number> | null {
if (k <= 0 || k > arr.length || arr.length === 0) {
return null;
}
let windowSum = 0;
for (let i = 0; i < k; i++) {
windowSum += arr[i];
}
let maxSum = windowSum;
let maxStartIndex = 0;
for (let i = k; i < arr.length; i++) {
windowSum = windowSum - arr[i - k] + arr[i];
if (windowSum > maxSum) {
maxSum = windowSum;
maxStartIndex = i - k + 1;
}
}
return {
value: maxSum,
startIndex: maxStartIndex,
endIndex: maxStartIndex + k - 1
};
}
/**
* Finds the longest substring without repeating characters
* Time Complexity: O(n) - each character visited at most twice
* Space Complexity: O(min(m, n)) where m is charset size
*
* @param s - Input string
* @returns Object containing substring length and indices, or null if empty
*/
function longestSubstringWithoutRepeat(
s: string
): SlidingWindowResult<number> | null {
if (s.length === 0) {
return null;
}
const charIndexMap = new Map<string, number>();
let maxLength = 0;
let maxStartIndex = 0;
let windowStart = 0;
for (let windowEnd = 0; windowEnd < s.length; windowEnd++) {
const currentChar = s[windowEnd];
if (charIndexMap.has(currentChar) && charIndexMap.get(currentChar)! >= windowStart) {
windowStart = charIndexMap.get(currentChar)! + 1;
}
charIndexMap.set(currentChar, windowEnd);
const currentLength = windowEnd - windowStart + 1;
if (currentLength > maxLength) {
maxLength = currentLength;
maxStartIndex = windowStart;
}
}
return {
value: maxLength,
startIndex: maxStartIndex,
endIndex: maxStartIndex + maxLength - 1
};
}
/**
* Calculates the moving average for each window position
* Time Complexity: O(n) - single pass through array
* Space Complexity: O(n - windowSize + 1) for result array
*
* @param arr - Array of numbers
* @param windowSize - Size of the moving window
* @returns Array of averages for each window position
*/
function movingAverage(
arr: number[],
windowSize: number
): number[] {
if (windowSize <= 0 || windowSize > arr.length || arr.length === 0) {
return [];
}
const averages: number[] = [];
let windowSum = 0;
for (let i = 0; i < windowSize; i++) {
windowSum += arr[i];
}
averages.push(windowSum / windowSize);
for (let i = windowSize; i < arr.length; i++) {
windowSum = windowSum - arr[i - windowSize] + arr[i];
averages.push(windowSum / windowSize);
}
return averages;
}
/**
* Generic sliding window processor for custom operations
* Time Complexity: O(n * processingTime) where processingTime depends on callbacks
* Space Complexity: O(windowSize) for window storage + callback requirements
*/
function slidingWindowProcess<T, R>(
arr: T[],
windowSize: number,
processor: (window: T[], index: number) => R
): R[] {
if (windowSize <= 0 || windowSize > arr.length || arr.length === 0) {
return [];
}
const results: R[] = [];
for (let i = 0; i <= arr.length - windowSize; i++) {
const window = arr.slice(i, i + windowSize);
results.push(processor(window, i));
}
return results;
}
const numbers = [2, 1, 5, 1, 3, 2, 8, 4, 6];
console.log("Array:", numbers);
const maxSum = maxSumSubarray(numbers, 3);
console.log("\nMax Sum Subarray (k=3):", maxSum);
const testString = "abcabcdefbb";
console.log("\nString:", testString);
const longestSub = longestSubstringWithoutRepeat(testString);
console.log("Longest Substring Without Repeat:", longestSub);
if (longestSub) {
console.log("Substring:", testString.slice(longestSub.startIndex, longestSub.endIndex + 1));
}
const prices = [10, 20, 30, 40, 50, 60, 70];
console.log("\nPrices:", prices);
const movingAvg = movingAverage(prices, 3);
console.log("Moving Average (window=3):", movingAvg);
const minValues = slidingWindowProcess(numbers, 3, (window) => Math.min(...window));
console.log("\nMin values per window (size=3):", minValues);
console.log("\n--- Edge Cases ---");
console.log("Empty array:", maxSumSubarray([], 3));
console.log("Window > array:", maxSumSubarray([1, 2], 5));
console.log("Single char string:", longestSubstringWithoutRepeat("a"));
console.log("All same chars:", longestSubstringWithoutRepeat("aaaa"));The sliding window technique is a powerful algorithmic pattern that transforms naive O(n*k) solutions into O(n) by maintaining a 'window' of elements and updating it incrementally as we traverse the data structure. Instead of recalculating everything for each window position, we simply remove the element leaving the window and add the element entering it.
The maxSumSubarray function demonstrates a fixed-size window approach. We first calculate the sum of the initial window, then slide it across the array by subtracting the leftmost element and adding the next element on the right. This avoids recalculating the entire sum for each position, reducing time complexity from O(n*k) to O(n). The function returns not just the maximum sum but also the window boundaries, making it useful for practical applications like finding peak trading periods.
The longestSubstringWithoutRepeat function uses a dynamic-size window that expands and contracts based on character uniqueness. A Map tracks the last seen index of each character. When we encounter a repeat, we shrink the window by moving the start pointer past the previous occurrence of that character. The key insight is using charIndexMap.get(currentChar)! >= windowStart to handle cases where a character's stored index is from before our current window started.
The movingAverage function is particularly useful in time-series analysis, financial calculations, and signal processing. It maintains a running sum and divides by window size, producing smooth trend lines from noisy data. The precision of floating-point arithmetic should be considered for financial applications where exact decimal precision matters.
The generic slidingWindowProcess function provides flexibility for custom window operations at the cost of creating new arrays for each window (O(k) per iteration). Use the optimized specific functions when performance is critical, but this generic version is valuable for complex processing where maintaining incremental state would be error-prone. Common real-world applications include network packet analysis, sensor data smoothing, and detecting patterns in streaming data.