Variable window

2 snippets in Interview Prep

DSAInterview Prep

Sliding Window

syntax

Maintain a window [left..right] and expand/shrink to satisfy a condition.
Fixed-size window: move both pointers together.
Variable-size window: expand right, shrink left when constraint violated.

example

// JavaScript — Max sum subarray of size k
function maxSumWindow(arr, k) {
  let windowSum = 0, maxSum = -Infinity;
  for (let i = 0; i < arr.length; i++) {
    windowSum += arr[i];
    if (i >= k) windowSum -= arr[i - k];
    if (i >= k - 1) maxSum = Math.max(maxSum, windowSum);
  }
  return maxSum;
}

# Python — Max sum subarray of size k
def max_sum_window(arr, k):
    window_sum = 0
    max_sum = float('-inf')
    for i in range(len(arr)):
        window_sum += arr[i]
        if i >= k:
            window_sum -= arr[i - k]
        if i >= k - 1:
            max_sum = max(max_sum, window_sum)
    return max_sum

output

max_sum_window([2,1,5,1,3,2], 3) → 9 (subarray [5,1,3])

Note Time O(n), Space O(1). Sliding window converts O(n*k) brute force to O(n). For variable-size windows (e.g., longest substring without repeats), use a hash set to track window contents. Always clarify: is the window fixed or variable size?

Pattern: Sliding Window (Summary)

DSA · Common Patterns Summary

syntax

When to use:
- Subarray/substring with constraint (max sum, min length, distinct chars)
- Fixed-size window statistics
- Longest/shortest substring matching a condition

Template:
- Expand right pointer
- When window invalid, shrink left pointer
- Update answer at each valid state

example

// JavaScript — Longest substring without repeating characters
function lengthOfLongestSubstring(s) {
  const charIdx = new Map();
  let maxLen = 0, left = 0;
  for (let right = 0; right < s.length; right++) {
    if (charIdx.has(s[right]) && charIdx.get(s[right]) >= left) {
      left = charIdx.get(s[right]) + 1;
    }
    charIdx.set(s[right], right);
    maxLen = Math.max(maxLen, right - left + 1);
  }
  return maxLen;
}

# Python
def length_of_longest_substring(s):
    char_idx = {}
    max_len = left = 0
    for right, ch in enumerate(s):
        if ch in char_idx and char_idx[ch] >= left:
            left = char_idx[ch] + 1
        char_idx[ch] = right
        max_len = max(max_len, right - left + 1)
    return max_len

output

length_of_longest_substring('abcabcbb') → 3 ('abc')

Note O(n) time, O(k) space where k = alphabet/window contents. The trick: store the last index of each character so you can jump the left pointer forward without shrinking one step at a time. This is one of the most frequently asked medium problems.