Sliding Window Technique

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

1function maxSumSubarray(arr: number[], k: number): number {
2  if (arr.length < k) return 0;
3  
4  // Calculate sum of first window
5  let windowSum = 0;
6  for (let i = 0; i < k; i++) {
7    windowSum += arr[i];
8  }
9  
10  let maxSum = windowSum;
11  
12  // Slide window
13  for (let i = k; i < arr.length i

Variable Window Size

1function longestSubstringWithoutRepeating(s: string): number {
2  const charIndex = new Map<string, number>();
3  let maxLength = 0;
4  let left = 0;
5  
6  for (let right = 0; right < s.length; right++) {
7    const char = s[right];
8    
9    // If character seen and within window, move left
10    if (charIndex.has(char) && charIndex.getchar  left

Minimum Window Substring

1function minWindow(s: string, t: string): string {
2  const need = new Map<string, number>();
3  const window = new Map<string, number>();
4  
5  // Count characters needed
6  for (const char of t) {
7    need.set(char, (need.get(char) || 0) + 1);
8  }

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:

1. Sliding window: Remove old requests as window slides
2. Efficient storage: Only store timestamps in window
3. Distributed: Use Redis for distributed systems
4. Cleanup: Periodic cleanup of old data
5. Scalability: Handle millions of requests

• 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