Sliding Window Technique in Ruby

As I continue studying for future technical interviews, I'd also like to keep sharing different implementations of many common data structures and algorithms in Ruby. Today I thought I'd share an algorithm model, a pattern known as the sliding window technique. For all of your fellow Rubyists out there, I hope this can be helpful.

It is a technique that could come in handy for certain algorithm problems that may pop up as an interview question. It is usually implemented on strings, arrays or linked lists. This pattern can be useful for questions that include the words "smallest, largest, minimum, maximum, subarray, subsequent" or anything that alludes to the fact that we are looking for a sequential set of numbers or letters.

It is called the sliding window technique because essentially we are looking for a subarray which is what we call our window, and we are only concerned with what values are inside of the subarray or window in a contiguous order. So I will often refer to the subarray as a window.

There are two types of implementations for the sliding window technique, based upon the window size. If the window length is known and can be fixed, the solution is a bit more simple as opposed to a variable window size. I'll go over both implementations, but first I'll begin with the solution for a fixed window size.

Fixed Window

For the fixed window length example, this solution is based off of the problem maximum or minimum sum subarray of size 'k'. For this implementation we will focus on the maximum sum.

We will be given an array and want to find the maximum total within the subarray size of k. First we will declare two variables, maxValue to hold the largest value we find, and then currentWindowSum to keep track of the current sum of the window.

We will iterate through the array and add each value onto our currentWindowSum until the window size is either greater or equal to our defined window size of k.

When we hit this conditional, we will compare the maxValue with our currentWindowSum to find the larger of the two and make this our new maxValue. We will also subtract the leftmost value before we continue iterating through our array and adding the next value.

We then return our maxValue as it will be the maximum sum of the continuous subarray of size k.

def max_sum_subarray(array, k)
  maxValue = 0
  currentWindowSum = 0

  i = 0
  while i < array.length do
    currentWindowSum += array[i]

    if i >= k-1
      maxValue = [maxValue, currentWindowSum].max
      currentWindowSum -= array[i - (k-1)]
    end

    i += 1
  end

  return maxValue
end

Variable Window

For the variable window length example, this solution is based off of the problem minimum size subarray sum. For this implementation we will be looking for the smallest subarray that totals to the target value.

The execution of a variable window size problem is a bit more tricky and will require more variables to keep track of where our window begins and ends. First we'll declare four variables:

We will iterate through our array, adding each consecutive value as we go along, also known as the value at the index of windowEnd, to our currentWindowSum. This continues until the currentWindowSum is either greater than or equal to the target value.

At this point we will compare the value of the current minWindowSize and the size of the window we have just discovered (the index of the beginning of our window, windowStart, plus 1 for indexing errors, subtracted from the index of the end of our window, windowEnd). Whichever is smaller becomes the new value for minWindowSize, and the value of the beginning of our window is subtracted from the currentWindowSum and the windowStart value is incremented as we continue iterating through the array.

This continues until we reach the end of our array, and the minimum window size is returned.

def smallest_subarray(array, target)

  minWindowSize = 100
  currentWindowSum = 0
  windowStart = 0

  windowEnd = 0
  while windowEnd < array.length do
    currentWindowSum += array[windowEnd]

    while currentWindowSum >= target do
      minWindowSize = [minWindowSize, (windowEnd - windowStart + 1)].min
      currentWindowSum -= arr[windowStart]
      windowStart += 1
    end

    windowEnd += 1
  end

  return minWindowSize

end

Helpful Video Tutorial

• Sliding Window Technique by The Simple Engineer

I hope this could be helpful for anyone interested in Ruby or using it in interviews as well. As always, please feel free to leave comments that could help improve my implementations or any information I may be missing. Otherwise, have an awesome weekend!