Sliding Window

Array Sweeps

Signal

Longest/shortest/max/min contiguous subarray or substring

Template

Grow right, shrink left while the window is invalid.

Worked examples (2)

Sliding Window (fixed size)

Sliding Window (fixed)

Given an integer array and a number k, find the contiguous subarray of length k with the maximum average, and return that average.

function findMaxAverage(nums: number[], k: number): number {
  let windowSum = 0;
  for (let i = 0; i < k; i++) windowSum += nums[i];
  let best = windowSum;
  for (let i = k; i < nums.length; i++) {
    windowSum += nums[i] - nums[i - k]; // add entering, drop leaving
    best = Math.max(best, windowSum);
  }
  return best / k;
}

def find_max_average(nums, k)
  window_sum = nums.first(k).sum
  best = window_sum
  (k...nums.length).each do |i|
    window_sum += nums[i] - nums[i - k] # add entering, drop leaving
    best = [best, window_sum].max
  end
  best.to_f / k
end

Sliding Window (variable size)

Sliding Window (variable)

Given a string, return the length of the longest substring containing no repeated characters.

function lengthOfLongestSubstring(s: string): number {
  const lastSeen = new Map<string, number>();
  let left = 0, best = 0;
  for (let right = 0; right < s.length; right++) {
    const c = s[right];
    const prev = lastSeen.get(c);
    if (prev !== undefined && prev >= left) left = prev + 1; // shrink past the dup
    lastSeen.set(c, right);
    best = Math.max(best, right - left + 1);
  }
  return best;
}

def length_of_longest_substring(s)
  last_seen = {}
  left = 0
  best = 0
  s.each_char.with_index do |c, right|
    prev = last_seen[c]
    left = prev + 1 if prev && prev >= left # shrink past the dup
    last_seen[c] = right
    best = [best, right - left + 1].max
  end
  best
end