Topic Overview
Sliding Window Technique
Master the sliding window technique: efficiently solve subarray/substring problems by maintaining a window that slides through the array.
The sliding window technique is an efficient method for solving problems involving subarrays or substrings by maintaining a window that slides through the array, avoiding redundant calculations.
Why This Matters in Interviews
Sliding window is essential because:
- Efficiency: Reduces O(n²) or O(n³) to O(n)
- Common pattern: Many array/string problems use this technique
- Two pointers: Tests understanding of pointer manipulation
- Optimization: Demonstrates ability to optimize solutions
Interviewers use sliding window to assess your problem-solving skills, your ability to recognize patterns, and your optimization thinking.
Core Concepts
- Fixed window: Window size is constant
- Variable window: Window size changes based on condition
- Two pointers: Left and right pointers define window
- Window maintenance: Add/remove elements as window moves
- Optimization: Avoid recalculating window properties
- Expanding/contracting: Grow or shrink window based on condition
Detailed Explanation
Fixed Window Size
function maxSumSubarray(arr: number[], k: number): number {
if (arr.length < k) return 0;
// Calculate sum of first window
let windowSum = 0;
for (let i = 0; i < k; i++) {
windowSum += arr[i];
}
let maxSum = windowSum;
// Slide window
for (let i = k; i < arr.length; i++) {
// Remove leftmost, add rightmost
windowSum = windowSum - arr[i - k] + arr[i];
maxSum = Math.max(maxSum, windowSum);
}
return maxSum;
}
// Time: O(n)
// Space: O(1)
Variable Window Size
function longestSubstringWithoutRepeating(s: string): number {
const charIndex = new Map<string, number>();
let maxLength = 0;
let left = 0;
for (let right = 0; right < s.length; right++) {
const char = s[right];
// If character seen and within window, move left
if (charIndex.has(char) && charIndex.get(char)! >= left) {
left = charIndex.get(char)! + 1;
}
charIndex.set(char, right);
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}
// Time: O(n)
// Space: O(min(n, m)) where m is character set size
Minimum Window Substring
function minWindow(s: string, t: string): string {
const need = new Map<string, number>();
const window = new Map<string, number>();
// Count characters needed
for (const char of t) {
need.set(char, (need.get(char) || 0) + 1);
}
let left = 0;
let right = 0;
let valid = 0; // Number of characters with correct count
let start = 0;
let len = Infinity;
while (right < s.length) {
const c = s[right];
right++;
// Update window
if (need.has(c)) {
window.set(c, (window.get(c) || 0) + 1);
if (window.get(c) === need.get(c)) {
valid++;
}
}
// Try to shrink window
while (valid === need.size) {
// Update result
if (right - left < len) {
start = left;
len = right - left;
}
const d = s[left];
left++;
// Update window
if (need.has(d)) {
if (window.get(d) === need.get(d)) {
valid--;
}
window.set(d, (window.get(d) || 1) - 1);
}
}
}
return len === Infinity ? "" : s.substring(start, start + len);
}
// Time: O(|s| + |t|)
// Space: O(|s| + |t|)
Examples
Maximum Average Subarray
function findMaxAverage(nums: number[], k: number): number {
let sum = 0;
// Sum of first window
for (let i = 0; i < k; i++) {
sum += nums[i];
}
let maxSum = sum;
// Slide window
for (let i = k; i < nums.length; i++) {
sum = sum - nums[i - k] + nums[i];
maxSum = Math.max(maxSum, sum);
}
return maxSum / k;
}
Longest Repeating Character Replacement
function characterReplacement(s: string, k: number): number {
const count = new Map<string, number>();
let maxCount = 0;
let maxLength = 0;
let left = 0;
for (let right = 0; right < s.length; right++) {
const char = s[right];
count.set(char, (count.get(char) || 0) + 1);
maxCount = Math.max(maxCount, count.get(char)!);
// If window needs more than k replacements, shrink
if (right - left + 1 - maxCount > k) {
count.set(s[left], count.get(s[left])! - 1);
left++;
}
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}
// Time: O(n)
// Space: O(1) - limited character set
Subarray with Given Sum
function subarraySum(nums: number[], target: number): number[] {
let left = 0;
let sum = 0;
for (let right = 0; right < nums.length; right++) {
sum += nums[right];
// Shrink window if sum exceeds target
while (sum > target && left <= right) {
sum -= nums[left];
left++;
}
if (sum === target) {
return [left, right];
}
}
return [];
}
// For negative numbers, use prefix sum + hash map
function subarraySumNegative(nums: number[], target: number): number {
const prefixSum = new Map<number, number>();
prefixSum.set(0, 1);
let sum = 0;
let count = 0;
for (const num of nums) {
sum += num;
const needed = sum - target;
if (prefixSum.has(needed)) {
count += prefixSum.get(needed)!;
}
prefixSum.set(sum, (prefixSum.get(sum) || 0) + 1);
}
return count;
}
Common Pitfalls
- Off-by-one errors: Window boundaries incorrect. Fix: Be careful with inclusive/exclusive
- Not updating window state: Forgetting to update counts/maps. Fix: Always update when adding/removing
- Wrong shrinking condition: Shrinking too much or too little. Fix: Understand problem requirements
- Not handling empty window: Edge cases. Fix: Check window size before processing
- Inefficient updates: Recalculating entire window. Fix: Update incrementally
Interview Questions
Beginner
Q: What is the sliding window technique and when would you use it?
A:
Sliding Window Technique efficiently solves subarray/substring problems by maintaining a window that slides through the array.
When to use:
- Subarray/substring problems: Finding subarrays or substrings
- Fixed size: Window of fixed size (e.g., max sum of k elements)
- Variable size: Window that grows/shrinks (e.g., longest substring)
- Optimization: Need to optimize O(n²) to O(n)
Types:
1. Fixed Window:
// Window size is constant
function fixedWindow(arr, k) {
// Calculate first window
// Slide and update
}
2. Variable Window:
// Window size changes
function variableWindow(arr, condition) {
// Expand until condition met
// Shrink until condition not met
}
Example:
Array: [1, 4, 2, 10, 23, 3, 1, 0, 20]
Window size: 4
Window 1: [1, 4, 2, 10] → sum = 17
Window 2: [4, 2, 10, 23] → sum = 39
Window 3: [2, 10, 23, 3] → sum = 38
...
Benefits:
- Efficiency: O(n) instead of O(n²)
- Simple: Easy to implement
- Space efficient: O(1) or O(k) space
Intermediate
Q: Implement a sliding window solution for finding the longest substring with at most k distinct characters.
A:
function longestSubstringKDistinct(s: string, k: number): number {
if (k === 0 || s.length === 0) return 0;
const charCount = new Map<string, number>();
let left = 0;
let maxLength = 0;
for (let right = 0; right < s.length; right++) {
const char = s[right];
charCount.set(char, (charCount.get(char) || 0) + 1);
// Shrink window if more than k distinct characters
while (charCount.size > k) {
const leftChar = s[left];
const count = charCount.get(leftChar)!;
if (count === 1) {
charCount.delete(leftChar);
} else {
charCount.set(leftChar, count - 1);
}
left++;
}
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}
// Time: O(n) - each character visited at most twice
// Space: O(k) - at most k characters in map
// Alternative: Return the actual substring
function longestSubstringKDistinctString(s: string, k: number): string {
const charCount = new Map<string, number>();
let left = 0;
let maxLength = 0;
let start = 0;
for (let right = 0; right < s.length; right++) {
const char = s[right];
charCount.set(char, (charCount.get(char) || 0) + 1);
while (charCount.size > k) {
const leftChar = s[left];
const count = charCount.get(leftChar)!;
if (count === 1) {
charCount.delete(leftChar);
} else {
charCount.set(leftChar, count - 1);
}
left++;
}
if (right - left + 1 > maxLength) {
maxLength = right - left + 1;
start = left;
}
}
return s.substring(start, start + maxLength);
}
Key points:
- Expand: Add characters to window
- Shrink: Remove characters when condition violated
- Track distinct: Use map to count distinct characters
- Update result: Track maximum length
Senior
Q: Design a rate limiter using sliding window technique that tracks requests per time window. Handle millions of requests per second and ensure accurate rate limiting.
A:
class SlidingWindowRateLimiter {
private requests: Map<string, number[]>; // user -> timestamps
private maxRequests: number;
private windowSize: number; // in milliseconds
constructor(maxRequests: number, windowSizeMs: number) {
this.requests = new Map();
this.maxRequests = maxRequests;
this.windowSize = windowSizeMs;
}
isAllowed(userId: string, timestamp: number = Date.now()): boolean {
const userRequests = this.requests.get(userId) || [];
const windowStart = timestamp - this.windowSize;
// Remove requests outside window (sliding)
const validRequests = userRequests.filter(ts => ts > windowStart);
if (validRequests.length >= this.maxRequests) {
return false;
}
// Add current request
validRequests.push(timestamp);
this.requests.set(userId, validRequests);
return true;
}
// Optimized with circular buffer
isAllowedOptimized(userId: string, timestamp: number = Date.now()): boolean {
if (!this.requests.has(userId)) {
this.requests.set(userId, []);
}
const userRequests = this.requests.get(userId)!;
const windowStart = timestamp - this.windowSize;
// Binary search for window start (if sorted)
let startIdx = 0;
for (let i = 0; i < userRequests.length; i++) {
if (userRequests[i] > windowStart) {
startIdx = i;
break;
}
}
// Sliding window: keep only valid requests
const validRequests = userRequests.slice(startIdx);
if (validRequests.length >= this.maxRequests) {
return false;
}
validRequests.push(timestamp);
this.requests.set(userId, validRequests);
return true;
}
// Distributed version with approximate counting
class DistributedRateLimiter {
private redis: RedisClient;
private maxRequests: number;
private windowSize: number;
async isAllowed(userId: string): Promise<boolean> {
const key = `ratelimit:${userId}`;
const now = Date.now();
const windowStart = now - this.windowSize;
// Use sorted set in Redis
// Remove old entries
await this.redis.zremrangebyscore(key, 0, windowStart);
// Count current requests
const count = await this.redis.zcard(key);
if (count >= this.maxRequests) {
return false;
}
// Add current request
await this.redis.zadd(key, now, `${now}-${Math.random()}`);
await this.redis.expire(key, Math.ceil(this.windowSize / 1000));
return true;
}
}
// Sliding log algorithm
class SlidingLogRateLimiter {
private logs: Map<string, number[]>;
async isAllowed(userId: string, maxRequests: number, windowMs: number): Promise<boolean> {
const now = Date.now();
const userLogs = this.logs.get(userId) || [];
// Remove logs outside window
const validLogs = userLogs.filter(ts => ts > now - windowMs);
if (validLogs.length >= maxRequests) {
return false;
}
validLogs.push(now);
this.logs.set(userId, validLogs);
// Cleanup old entries periodically
if (Math.random() < 0.01) { // 1% chance
this.cleanup();
}
return true;
}
private cleanup(): void {
const now = Date.now();
for (const [userId, logs] of this.logs.entries()) {
const valid = logs.filter(ts => ts > now - 3600000); // 1 hour
if (valid.length === 0) {
this.logs.delete(userId);
} else {
this.logs.set(userId, valid);
}
}
}
}
}
Features:
- Sliding window: Remove old requests as window slides
- Efficient storage: Only store timestamps in window
- Distributed: Use Redis for distributed systems
- Cleanup: Periodic cleanup of old data
- Scalability: Handle millions of requests
Key Takeaways
- Sliding window: Efficient technique for subarray/substring problems
- Fixed window: Constant size, O(n) time
- Variable window: Size changes, expand/contract based on condition
- Two pointers: Left and right define window boundaries
- Time complexity: O(n) - each element visited at most twice
- Space complexity: O(1) or O(k) depending on tracking needs
- Applications: Rate limiting, substring problems, subarray problems