Sliding Window

Overview

Sliding window provides an efficient approach for solving problems that involve sequential data where answers depend on contiguous subarrays or substrings. The technique reduces time complexity by avoiding redundant computations as the window moves through the data structure.

The core concept involves maintaining two pointers that define a range of elements. As these pointers move, they create a "window" that slides across the data. Operations performed on elements entering or leaving the window enable incremental computation of aggregate values without recalculating from scratch.

Problems suited for sliding window share common characteristics: they involve arrays or strings, require processing contiguous elements, and ask for optimization (maximum, minimum, or specific conditions) over all possible windows. Examples include finding the longest substring without repeating characters, maximum sum subarray of fixed size, or smallest subarray with sum greater than a target value.

The technique appears in string processing, time series analysis, network packet processing, and anywhere sequential data requires efficient range-based computation.

# Basic fixed-size window: maximum sum of k consecutive elements
def max_sum_fixed_window(arr, k)
  return nil if arr.length < k
  
  # Calculate initial window sum
  window_sum = arr[0...k].sum
  max_sum = window_sum
  
  # Slide window: remove leftmost, add new rightmost
  (k...arr.length).each do |i|
    window_sum = window_sum - arr[i - k] + arr[i]
    max_sum = [max_sum, window_sum].max
  end
  
  max_sum
end

max_sum_fixed_window([2, 1, 5, 1, 3, 2], 3)
# => 9 (subarray [5, 1, 3])

Key Principles

The sliding window technique operates on the principle of incremental computation. Instead of recalculating values for each possible subarray, the algorithm maintains state as the window moves. When the window shifts by one position, only two operations occur: remove the element leaving the window and add the element entering the window.

Window Boundaries

Two indices define the window boundaries. The left pointer marks the start, the right pointer marks the end. The window size equals right - left + 1 for inclusive boundaries or right - left for exclusive right boundaries. The choice between inclusive and exclusive boundaries affects loop conditions and index calculations.

State Maintenance

The window maintains aggregate state that updates incrementally. For sum-based problems, the state holds the current sum. For substring problems, the state might track character frequencies using a hash. For maximum/minimum problems, the state could use a deque to maintain elements in sorted order.

Window Movement Patterns

Fixed-size windows move both pointers together, maintaining constant size. The right pointer advances, a new element enters, the left pointer advances, an old element exits. Variable-size windows expand and contract based on conditions. The right pointer extends the window when conditions allow, the left pointer contracts when constraints violated.

Termination Conditions

Fixed-size windows terminate when the right pointer reaches the end. Variable-size windows terminate when no valid expansion remains possible. Some problems require processing after the main loop to handle edge cases where the optimal window exists at the end.

Time Complexity Foundation

Naive approaches checking all subarrays run in O(n²) or O(n³) time. Sliding window reduces this to O(n) because each element enters and exits the window exactly once. The work per element remains constant, leading to linear time complexity.

# Variable-size window: longest substring without repeating characters
def longest_unique_substring(s)
  char_index = {}
  left = 0
  max_length = 0
  
  s.each_char.with_index do |char, right|
    # If character seen and within current window
    if char_index[char] && char_index[char] >= left
      left = char_index[char] + 1
    end
    
    char_index[char] = right
    max_length = [max_length, right - left + 1].max
  end
  
  max_length
end

longest_unique_substring("abcabcbb")
# => 3 (substring "abc")

Ruby Implementation

Ruby's enumerable methods and hash capabilities make sliding window implementations concise. The language provides multiple approaches depending on problem requirements and readability preferences.

Fixed Window with Array Slicing

Array slicing creates readable fixed-window code but generates intermediate arrays. This approach works well for small windows or when clarity outweighs performance.

def average_of_subarrays(arr, k)
  return [] if arr.length < k
  
  (0..arr.length - k).map do |i|
    arr[i, k].sum / k.to_f
  end
end

average_of_subarrays([1, 3, 2, 6, -1, 4, 1, 8, 2], 5)
# => [2.2, 2.8, 2.4, 3.6, 2.8]

Fixed Window with Manual State

Manual state management avoids intermediate arrays and provides better performance. The pattern maintains window state and updates incrementally.

def max_sum_subarray(arr, k)
  return nil if arr.empty? || k > arr.length || k <= 0
  
  current_sum = arr[0...k].sum
  max_sum = current_sum
  
  (k...arr.length).each do |i|
    current_sum += arr[i] - arr[i - k]
    max_sum = current_sum if current_sum > max_sum
  end
  
  max_sum
end

Variable Window with Hash State

Variable windows often require hash maps to track element frequencies, positions, or counts within the window.

def min_window_substring(s, t)
  return "" if s.empty? || t.empty?
  
  target_freq = t.each_char.tally
  window_freq = Hash.new(0)
  
  left = 0
  min_len = Float::INFINITY
  min_start = 0
  matched = 0
  
  s.each_char.with_index do |char, right|
    window_freq[char] += 1
    matched += 1 if target_freq[char] && window_freq[char] == target_freq[char]
    
    while matched == target_freq.size
      if right - left + 1 < min_len
        min_len = right - left + 1
        min_start = left
      end
      
      left_char = s[left]
      window_freq[left_char] -= 1
      matched -= 1 if target_freq[left_char] && window_freq[left_char] < target_freq[left_char]
      left += 1
    end
  end
  
  min_len == Float::INFINITY ? "" : s[min_start, min_len]
end

min_window_substring("ADOBECODEBANC", "ABC")
# => "BANC"

Deque for Maximum/Minimum in Window

When the window must track maximum or minimum values, a deque maintains elements in sorted order. Ruby lacks a built-in deque, but arrays provide the necessary operations.

def max_sliding_window(arr, k)
  return [] if arr.empty? || k <= 0
  
  result = []
  deque = [] # Stores indices
  
  arr.each_with_index do |num, i|
    # Remove elements outside window
    deque.shift while !deque.empty? && deque.first < i - k + 1
    
    # Remove elements smaller than current (they can't be max)
    deque.pop while !deque.empty? && arr[deque.last] < num
    
    deque.push(i)
    result.push(arr[deque.first]) if i >= k - 1
  end
  
  result
end

max_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3)
# => [3, 3, 5, 5, 6, 7]

Using Enumerator for Complex Iterations

Enumerators enable custom iteration patterns for complex sliding window scenarios.

def each_window(arr, size)
  return enum_for(:each_window, arr, size) unless block_given?
  
  return if arr.length < size
  
  (0..arr.length - size).each do |i|
    yield arr[i, size], i
  end
end

# Usage
sums = []
each_window([1, 2, 3, 4, 5], 3) do |window, index|
  sums << window.sum
end
# sums => [6, 9, 12]

Common Patterns

Several sliding window patterns recur across different problem types. Recognition of these patterns accelerates problem-solving and implementation.

Fixed-Size Window with Aggregate

This pattern computes an aggregate value (sum, average, product) over all windows of size k. The window moves one element at a time, updating the aggregate incrementally.

def max_average_subarray(nums, k)
  window_sum = nums[0...k].sum
  max_sum = window_sum
  
  (k...nums.length).each do |i|
    window_sum += nums[i] - nums[i - k]
    max_sum = [max_sum, window_sum].max
  end
  
  max_sum / k.to_f
end

Expanding Window with Constraint

The window expands by moving the right pointer until a constraint breaks. When violated, the left pointer advances to restore validity. This pattern handles problems like "longest substring with at most k distinct characters."

def length_of_longest_substring_k_distinct(s, k)
  return 0 if s.empty? || k == 0
  
  char_count = Hash.new(0)
  left = 0
  max_length = 0
  
  s.each_char.with_index do |char, right|
    char_count[char] += 1
    
    while char_count.size > k
      left_char = s[left]
      char_count[left_char] -= 1
      char_count.delete(left_char) if char_count[left_char] == 0
      left += 1
    end
    
    max_length = [max_length, right - left + 1].max
  end
  
  max_length
end

length_of_longest_substring_k_distinct("eceba", 2)
# => 3 ("ece")

Shrinking Window with Target

The window expands until meeting a target, then shrinks to find the minimum size that still satisfies the target. This handles "smallest subarray with sum >= target."

def min_subarray_sum(target, nums)
  return 0 if nums.empty?
  
  left = 0
  current_sum = 0
  min_length = Float::INFINITY
  
  nums.each_with_index do |num, right|
    current_sum += num
    
    while current_sum >= target
      min_length = [min_length, right - left + 1].min
      current_sum -= nums[left]
      left += 1
    end
  end
  
  min_length == Float::INFINITY ? 0 : min_length
end

min_subarray_sum(7, [2, 3, 1, 2, 4, 3])
# => 2 (subarray [4, 3])

Two-Pointer with Frequency Map

Maintains character or element frequencies within the window using a hash. Common for anagram, permutation, or pattern-matching problems.

def find_anagrams(s, p)
  result = []
  return result if s.length < p.length
  
  p_count = p.each_char.tally
  window_count = Hash.new(0)
  
  # Initialize first window
  s[0...p.length].each_char { |c| window_count[c] += 1 }
  result << 0 if window_count == p_count
  
  # Slide window
  (p.length...s.length).each do |i|
    # Add new character
    window_count[s[i]] += 1
    
    # Remove old character
    left_char = s[i - p.length]
    window_count[left_char] -= 1
    window_count.delete(left_char) if window_count[left_char] == 0
    
    result << i - p.length + 1 if window_count == p_count
  end
  
  result
end

find_anagrams("cbaebabacd", "abc")
# => [0, 6] (anagrams at indices 0 and 6)

Maximum/Minimum in Sliding Window

Maintains the maximum or minimum element as the window slides. Uses a deque to track potential candidates in sorted order.

def min_sliding_window(nums, k)
  result = []
  deque = []
  
  nums.each_with_index do |num, i|
    deque.shift if !deque.empty? && deque.first < i - k + 1
    deque.pop while !deque.empty? && nums[deque.last] > num
    deque.push(i)
    result.push(nums[deque.first]) if i >= k - 1
  end
  
  result
end

Distinct Count Window

Tracks the number of distinct elements in the window, often requiring a hash to maintain counts.

def count_distinct_windows(arr, k)
  return [] if arr.length < k
  
  freq = Hash.new(0)
  result = []
  
  # First window
  arr[0...k].each { |num| freq[num] += 1 }
  result << freq.size
  
  # Slide window
  (k...arr.length).each do |i|
    # Add new element
    freq[arr[i]] += 1
    
    # Remove old element
    old = arr[i - k]
    freq[old] -= 1
    freq.delete(old) if freq[old] == 0
    
    result << freq.size
  end
  
  result
end

count_distinct_windows([1, 2, 1, 3, 4, 2, 3], 4)
# => [3, 4, 4, 3]

Practical Examples

Problem: Maximum Points from Cards

Given an array of card values, select exactly k cards from either end to maximize points. This requires a sliding window approach where the window represents cards NOT selected.

def max_score(card_points, k)
  n = card_points.length
  window_size = n - k
  
  # If selecting all cards
  return card_points.sum if window_size == 0
  
  total = card_points.sum
  window_sum = card_points[0...window_size].sum
  min_window = window_sum
  
  # Find minimum window (cards not selected)
  (window_size...n).each do |i|
    window_sum += card_points[i] - card_points[i - window_size]
    min_window = [min_window, window_sum].min
  end
  
  total - min_window
end

max_score([1, 2, 3, 4, 5, 6, 1], 3)
# => 12 (take [6, 1] from right and [1] from left)

Problem: Longest Repeating Character Replacement

Find the longest substring where at most k characters can be replaced to make all characters the same.

def character_replacement(s, k)
  char_count = Hash.new(0)
  left = 0
  max_count = 0
  max_length = 0
  
  s.each_char.with_index do |char, right|
    char_count[char] += 1
    max_count = [max_count, char_count[char]].max
    
    # Window size - most frequent character count = replacements needed
    while right - left + 1 - max_count > k
      char_count[s[left]] -= 1
      left += 1
    end
    
    max_length = [max_length, right - left + 1].max
  end
  
  max_length
end

character_replacement("AABABBA", 1)
# => 4 (replace one B in "AABA" to get "AAAA")

Problem: Fruits into Baskets

Collect maximum fruits from trees where each basket holds one fruit type, and baskets hold only two types total. This reduces to longest subarray with at most two distinct elements.

def total_fruit(fruits)
  basket = Hash.new(0)
  left = 0
  max_fruits = 0
  
  fruits.each_with_index do |fruit, right|
    basket[fruit] += 1
    
    while basket.size > 2
      basket[fruits[left]] -= 1
      basket.delete(fruits[left]) if basket[fruits[left]] == 0
      left += 1
    end
    
    max_fruits = [max_fruits, right - left + 1].max
  end
  
  max_fruits
end

total_fruit([1, 2, 1, 2, 3, 1, 1])
# => 5 (collect [2, 3, 1, 1, 1] or [1, 1, 2, 1, 2])

Problem: Permutation in String

Check if one string contains a permutation of another string as a substring.

def check_inclusion(s1, s2)
  return false if s1.length > s2.length
  
  s1_count = s1.each_char.tally
  window_count = Hash.new(0)
  
  # Initialize window
  s2[0...s1.length].each_char { |c| window_count[c] += 1 }
  return true if window_count == s1_count
  
  # Slide window
  (s1.length...s2.length).each do |i|
    window_count[s2[i]] += 1
    
    left_char = s2[i - s1.length]
    window_count[left_char] -= 1
    window_count.delete(left_char) if window_count[left_char] == 0
    
    return true if window_count == s1_count
  end
  
  false
end

check_inclusion("ab", "eidbaooo")
# => true (contains "ba")

Problem: Minimum Size Subarray Sum

Find the minimal length of a contiguous subarray where sum >= target.

def min_sub_array_len(target, nums)
  left = 0
  sum = 0
  min_len = Float::INFINITY
  
  nums.each_with_index do |num, right|
    sum += num
    
    while sum >= target
      min_len = [min_len, right - left + 1].min
      sum -= nums[left]
      left += 1
    end
  end
  
  min_len == Float::INFINITY ? 0 : min_len
end

min_sub_array_len(7, [2, 3, 1, 2, 4, 3])
# => 2 ([4, 3])

Performance Considerations

Sliding window transforms problems from O(n²) or worse to O(n) time complexity by eliminating redundant computation. Understanding when this optimization applies and its implementation costs guides effective usage.

Time Complexity Analysis

Fixed-size window algorithms run in O(n) time where n is the array length. Each element enters and exits the window exactly once. Operations per element remain constant: hash lookup, arithmetic update, comparison. Variable-size windows also achieve O(n) despite the nested while loop. The left pointer moves at most n times across the entire algorithm, not per iteration.

The deque-based maximum/minimum window runs in O(n) amortized time. Each element enters and exits the deque at most once. Individual operations might take O(k) where k is the deque size, but total operations across all elements remain O(n).

Space Complexity Patterns

Fixed-size windows with simple aggregates (sum, count) use O(1) space. The state consists of a few variables regardless of input size. Windows tracking frequencies or unique elements use O(k) space where k is the window size or number of distinct elements. Hash maps grow with distinct elements in the window.

Deque-based approaches use O(k) space in the worst case where k is the window size. The deque size never exceeds the window size because elements outside the window get removed.

Ruby-Specific Performance

Array slicing creates new array objects. For performance-critical code processing large arrays, avoid slicing inside loops. Manual index tracking with state variables outperforms slicing by eliminating object allocation.

# Slower: creates k new arrays
def slow_window_sum(arr, k)
  (0..arr.length - k).map { |i| arr[i, k].sum }
end

# Faster: maintains single sum variable
def fast_window_sum(arr, k)
  result = []
  sum = arr[0...k].sum
  result << sum
  
  (k...arr.length).each do |i|
    sum += arr[i] - arr[i - k]
    result << sum
  end
  
  result
end

Hash operations in Ruby run in O(1) average time. However, hash creation and manipulation add constant overhead. For windows tracking only presence/absence, consider alternative data structures. For frequency counting, hashes remain the idiomatic choice.

Optimization Techniques

Early Termination: Some problems allow stopping before processing all elements. If finding any valid window suffices, return immediately upon discovery.

def contains_duplicate_within_k(nums, k)
  seen = {}
  
  nums.each_with_index do |num, i|
    return true if seen[num] && i - seen[num] <= k
    seen[num] = i
  end
  
  false
end

Batch Processing: When the window operation is expensive, batch multiple operations. Instead of checking conditions on every iteration, check periodically or only when state changes significantly.

State Representation: Choose state representation based on query requirements. Tracking sum requires one integer. Tracking maximum requires a deque. Tracking median requires two heaps. Match state complexity to problem needs.

Memory Locality: Fixed-size windows with sequential access exhibit good cache performance. Variable-size windows with hash lookups may incur cache misses. For performance-critical applications processing large datasets, consider cache effects.

Benchmarking Example

require 'benchmark'

arr = (1..100_000).to_a
k = 1000

Benchmark.bm do |x|
  x.report("slicing:") do
    (0..arr.length - k).each { |i| arr[i, k].sum }
  end
  
  x.report("sliding:") do
    sum = arr[0...k].sum
    (k...arr.length).each { |i| sum += arr[i] - arr[i - k] }
  end
end

# Results show sliding window significantly faster

Common Pitfalls

Off-by-One Errors in Window Bounds

Incorrect boundary calculations cause elements to be processed multiple times or skipped. The window size calculation right - left + 1 assumes both indices are inclusive. Exclusive right boundaries use right - left.

# Incorrect: double-counts elements
def wrong_window(arr, k)
  left = 0
  arr.each_with_index do |_, right|
    window_size = right - left  # Wrong for inclusive bounds
    left += 1 if window_size > k
  end
end

# Correct
def correct_window(arr, k)
  left = 0
  arr.each_with_index do |_, right|
    window_size = right - left + 1  # Correct for inclusive bounds
    left += 1 if window_size > k
  end
end

Forgetting to Update State on Window Shrink

When the left pointer moves, the element exiting the window must update the state. Forgetting this creates incorrect results.

# Incorrect: doesn't remove exiting element from hash
def wrong_distinct_count(arr, k)
  freq = Hash.new(0)
  
  arr.each_with_index do |num, right|
    freq[num] += 1
    
    if right >= k
      # Missing: freq[arr[right - k]] -= 1
    end
  end
end

# Correct
def correct_distinct_count(arr, k)
  freq = Hash.new(0)
  
  arr.each_with_index do |num, right|
    freq[num] += 1
    
    if right >= k
      old = arr[right - k]
      freq[old] -= 1
      freq.delete(old) if freq[old] == 0
    end
  end
end

Not Handling Empty Hash Values

Ruby hashes return nil for missing keys unless a default value is set. When decrementing counts, removing zero-count entries prevents the hash from growing unbounded.

# Problematic: hash grows with zero values
def bad_frequency_tracking(s, k)
  freq = {}
  
  s.each_char.with_index do |c, i|
    freq[c] = (freq[c] || 0) + 1
    
    if i >= k
      old = s[i - k]
      freq[old] -= 1  # Leaves zero values
    end
  end
end

# Better: removes zero counts
def good_frequency_tracking(s, k)
  freq = Hash.new(0)
  
  s.each_char.with_index do |c, i|
    freq[c] += 1
    
    if i >= k
      old = s[i - k]
      freq[old] -= 1
      freq.delete(old) if freq[old] == 0
    end
  end
end

Incorrect Maximum Count Tracking

When tracking the most frequent element in a variable window, the maximum count may not decrease when the window shrinks. This optimization requires careful handling.

# Bug: max_count never decreases
def buggy_replacement(s, k)
  freq = Hash.new(0)
  left = 0
  max_count = 0
  
  s.each_char.with_index do |c, right|
    freq[c] += 1
    max_count = [max_count, freq[c]].max
    
    # max_count doesn't update when window shrinks
    while right - left + 1 - max_count > k
      freq[s[left]] -= 1
      left += 1
    end
  end
end

# Correct approach: recalculate or use different strategy
def correct_replacement(s, k)
  freq = Hash.new(0)
  left = 0
  result = 0
  
  s.each_char.with_index do |c, right|
    freq[c] += 1
    
    while right - left + 1 - freq.values.max > k
      freq[s[left]] -= 1
      left += 1
    end
    
    result = [result, right - left + 1].max
  end
  
  result
end

Initial Window Setup Errors

Setting up the first window before entering the main loop requires careful index handling. Missing or incorrect initialization causes wrong results for the first window.

# Wrong: doesn't process first k elements correctly
def wrong_init(arr, k)
  sum = 0
  
  arr.each_with_index do |num, i|
    sum += num
    sum -= arr[i - k] if i >= k  # First window incomplete
  end
end

# Correct: initializes first window separately
def correct_init(arr, k)
  sum = arr[0...k].sum
  max_sum = sum
  
  (k...arr.length).each do |i|
    sum += arr[i] - arr[i - k]
    max_sum = [max_sum, sum].max
  end
  
  max_sum
end

Comparing Hashes for Equality

Ruby hash equality requires both keys and values to match. When comparing frequency maps, zero-count entries must be removed or the comparison fails.

# Fails when hashes have different zero-count keys
target = { 'a' => 2, 'b' => 1 }
window = { 'a' => 2, 'b' => 1, 'c' => 0 }

target == window  # => false, even though counts match for target keys

# Solution: remove zero counts
window.delete('c')
target == window  # => true

Infinite Loops in While Conditions

Variable windows use while loops to shrink. If the shrinking condition never becomes false, the loop runs infinitely. Verify that the left pointer advancement always makes progress toward satisfying the loop exit condition.

# Potential infinite loop if condition poorly designed
def risky_window(arr, k)
  left = 0
  
  arr.each_with_index do |num, right|
    while some_condition  # Verify this eventually becomes false
      left += 1
    end
  end
end

Reference

Sliding Window Types

Common Problem Categories

Time Complexity Summary

Space Complexity Patterns

Ruby Methods for Sliding Window

Decision Matrix

Edge Cases Checklist