Sliding Window Algorithm

The sliding window algorithm is an efficient tool for providing solutions to problems involving the selection and comparison of subsets within arrays and strings.

Examples of such problems include finding the maximum sum subarray of a given size, finding the length of the longest substring without repeating characters, and finding the minimum window substring containing all characters of a given string. After understanding how the window sliding algorithm works, one could feasibly complete this Medium LeetCode problem: https://leetcode.com/problems/maximum-sum-of-distinct-subarrays-with-length-k/

In this post, we will be tackling a simpler modification of the above problem. We'll detail how you can find the maximum sum subarray of a given array, with a subarray size of K.

Maximum Sum Subarray of size K

Problem statement:

Given an array of integers and an integer k, find the maximum sum of any contiguous subarray of size k.

Input:

• An array nums containing n integers, where 1 <= n <= 10^5

• An integer k, where 1 <= k <= n

Output:

• Return the maximum sum of any contiguous subarray of size k

Input: nums = [2, 1, 5, 1, 3, 2], k = 3
Output: 9

And a potential solution in ruby:

def max_sum_subarray(nums, k)
  max_sum = 0
  window_sum = 0
  window_start = 0

  nums.each_with_index do |num, window_end|
    window_sum += num # Add the next element to the window sum

    if window_end >= k - 1 # If the window size is >= k
      max_sum = [max_sum, window_sum].max # Update the max_sum if needed
      window_sum -= nums[window_start] # Remove the element going out of the window
      window_start += 1 # Slide the window
    end
  end

  max_sum
end

nums = [2, 1, 5, 1, 3, 2]
k = 3
puts max_sum_subarray(nums, k) # Output: 9

In this implementation, we initialize a window_sum. This represents the sum of elements within the sliding window.

We iterate through the array, adding elements to the window_sum.

When the window size is greater than or equal to k, we update the max_sum and remove the element that is no longer in the window.

I've included a diagram below, to help demonstrate how this works:

Final thoughts

Hopefully, the sliding window algorithm is a bit clearer now. Like most, these problems start simple but then require additional considerations as the problems get more complicated.

If you're interested in advancing your algorithm skills with the sliding window, here are two Medium LeetCode problems that can be solved using a similar technique:

• https://leetcode.com/problems/maximum-sum-of-distinct-subarrays-with-length-k/

• https://leetcode.com/problems/maximum-subarray-sum-with-one-deletion/

Thanks for reading!