An Introduction to Algorithmic Thinking With Sliding Window
In this article, I will explain the basics ideas on solving coding questions that use the sliding window technique. As a prerequisite, one should feel comfortable working with arrays, arraylists, and fundamental concepts such as looping and if-else statements. I covered the latter concept in my previous article regarding the basics of Java, and I will soon publish my article on arrays and arraylists in Java!
Let’s hop straight into an example, where we will go through the logic and code for a sliding window problem.
“Tell me and I forget, teach me and I may remember, involve me and I learn.” — Benjamin Franklin
Laying Out the Question
Suppose we are given an array of integers of size n. Each integer array[i], where 0 ≤ i < array.length can be positive or negative. We are also given an integer m, which represents the size of a subarray within the original array, and 1 ≤ m ≤ n. We want to find the subarray of length m which has the highest average out of all subarrays of length m in the array, and then return the value of that average as a double.
For somebody who is not familiar with the sliding window technique, this question might be difficult to grasp. So, let’s break this problem down.
We essentially want to check every subarray of length m and keep track of the maximum subarray average, but we want to get rid of some of the redundant work like calculating the average. The fundamental idea of solving a problem like this involves utilizing two pointers that act as the left and right boundaries of the current subarray. Whenever the length of our “window” matches the constraints, we shift our window to the right and continue solving from there (hence the name sliding window). The trick comes in when we need to calculate our average. The naive approach would be to calculate a sum starting from the left boundary, clear the sum when our window…