DEV Community

Cover image for Sliding Windows Explained: Sunglasses Analogy with Ruby Code
Brian Kim
Brian Kim

Posted on

Sliding Windows Explained: Sunglasses Analogy with Ruby Code

#algorithms #beginners #ruby #tutorial

The Sunglasses Analogy πŸ˜ŽπŸŒ„

Imagine you are standing on a hill overlooking a long landscape. This landscape represents your array or string. You have a special pair of sunglasses that only let you see a fixed portion at a time β€” this is your sliding window.

  • Entering view: The new element coming into the right side of your window.
  • Exiting view: The element leaving from the left side of your window.
  • State tracking: You keep track of something interesting in your window, like the sum, max, or number of unique elements.

Instead of recalculating everything for each new position, you update incrementally:

  • Remove what leaves your view.
  • Add what enters your view.
  • Update your result.

Why this is useful

Without sliding windows:

For each window of size k, you recalculate everything from scratch. Slow!
Enter fullscreen mode Exit fullscreen mode

With sliding windows:

Update incrementally as the window moves. Fast and efficient!
Enter fullscreen mode Exit fullscreen mode

Ruby Code Example: Fixed-Size Window (Sum of Subarrays) 

# Landscape: array of trees
arr = [1, 2, 3, 4, 5]
k = 3

# Initial window sum
window_sum = arr[0...k].sum
max_sum = window_sum

# Slide the window
(1..arr.length - k).each do |i|
  window_sum = window_sum - arr[i - 1] + arr[i + k - 1]
  max_sum = [max_sum, window_sum].max
end

puts "Maximum sum of a window of size #{k}: #{max_sum}"
Enter fullscreen mode Exit fullscreen mode

Explanation:

  • arr[i - 1] leaves the window.
  • arr[i + k - 1] enters the window.
  • Update the window_sum incrementally.

Ruby Code Example: Variable-Size Window (Longest Substring with ≀ k Distinct Characters) 

s = "abcba"
k = 2
count = Hash.new(0)
left = 0
max_len = 0

(0...s.length).each do |right|
  count[s[right]] += 1

  # Shrink window from left if constraint is violated
  while count.size > k
    count[s[left]] -= 1
    count.delete(s[left]) if count[s[left]] == 0
    left += 1
  end

  max_len = [max_len, right - left + 1].max
end

puts "Length of longest substring with ≀ #{k} distinct characters: #{max_len}"
Enter fullscreen mode Exit fullscreen mode

Explanation:

  • Expand the window to the right.
  • Shrink from the left when there are too many unique characters.
  • Keep track of the state (count) inside the window.

Mental Takeaways

  1. Draw it out: Mark elements entering and leaving your window.
  2. Focus on incremental updates: Don’t recompute the entire window.
  3. Two pointers = sliding window: Usually left and right pointers track the window.
  4. Think in terms of the analogy: Sunglasses help visualize the moving window.

With this approach, sliding windows go from frustrating to intuitive. 😎

Tip: Start with small examples on paper using your sunglasses metaphor, then code them incrementally. It sticks in your brain and makes coding these problems much easier.

Top comments (0)