Hi. Welcome,
If you’re like me and you’re not a scholar but you have a burning desire to become a great within the software field, let’s learn together. We demystify leetcode exercises by understanding a base concept and work our way up to the more challenging problems surrounding the concept. In this post, we look specifically at the Sliding Window Approach.
The sliding window involves traversing a collection of structures iteratively using a fixed-size window that moves from left to right. Most commonly, it is employed to address issues involving linear data structures, such as arrays and strings. Where sliding window becomes helpful is where you can reduce repetitive computation.
Let’s imagine we are asked to find the three repeating number in an array. We are informed that the three repeating integers in this array are an oddity in the dataset. The brute force method requires that we traverse the array and then determine whether the subsequent two elements are identical. When N is the number of elements in the array and M is the number of repeated elements to be found, the result is a time complexity of O(N*M). Let’s look at an example [11,4,3,3,3].
The illustration above demonstrates how we check to see if the following two elements in the loop are identical to the current element. We eventually discovered that the number 3 occurs three times in a row.
The Sliding Window Logic
Sliding window helps reduce the time complexity to O(N) by allowing all computation to be done within 1 traversal of the loop instead of having a nested traversal. The nested traversal simply means that with each element we check, we have to traverse the array again before moving the pointer forward.
Just to ensure we understand why we need a better approach.
Array[0] holds the value of 11. We then create a second pointer to do a nested array traversal. While traversing we find out that array[1] which holds the value of 4 is not the same as array[2] which holds a value of 3. All three values are not the same. So we increment the index by 1.
Array[1] holds a value of 4. We then create a second pointer to do a nested array traversal. While traversing we find out that array[2] which holds the value of 3 is the same as array[3] which holds a value of 3 but all three values are not the same. So we increment the index by 1.
BUT! If you noticed, in the first loop we are checked array[0], array[1] and array[2]. In the next loop we are checking array[1], array[2], and array[3] so we are checking array[1] and array[2] twice. In essence, we are doing “double the work!”. The sliding window pattern utilizes the fact that we already have an answer to a previous compute that can assist in providing the answer to the entire problem. It is much easier to understand window sliding approach with an example and visual representation.
Let’s look at an example where we have an array [1,3,4,10,1] and we’re are trying to find the first three successive numbers that are greater than 15.
In the brute force approach we do the following
- we traverse each element on the array
- while traversing, we create a temporary variable that hold the value of the current index
- we traverse the length of 3 for each element in the array using the temporary variable
- then we increment the index by 1 and start again
In the sliding window approach below
- we traverse the array until we find the length we require to compute
- In this case we go until we reach the third element. array[2] which holds a value of 4
- we compute the tally of the first 3 element then we change the tally by shifting the window
- the logic of shifting the window includes removing the first element and adding the next. When this is done, the window size remains fixed without having to recalculate previous compute.
No matter how complex a question becomes, the basic application remains valid. Due to the ubiquity of this method, the majority of sliding window problems require some additional logic to resolve. more so at the more challenging questions. I advise gaining as much practice as you can and learning from others. Eventually, it will get easier, and your broad knowledge will enable you to put together an answer with confidence. Don’t give up
We search by category and filter by acceptance. The questions tend to become more difficult as the acceptance rate decreases. We’ll tackle one problem from each difficulty level.
- 1 Question below 50% acceptance in easy, medium and hard
- Pop Question. I’ll leave it up to you to reason why my solution it works
……………… Leetcode 643. MAXIMUM AVERAGE SUBARRAY I……………..
https://leetcode.com/problems/maximum-average-subarray-i
Acceptance criteria BELOW 50% & EASY | Acceptance at post time 43%.
In this question we are told to find the maximum average of k element. K is 4 therefore we are looking for the window of 4 elements that have the highest average. Let’s see how the sliding pattern attempts to solve this question.
As seen above, the highest average of a window of length k is 12.75
var findMaxAverage = function(nums, k) {
if(nums.length == 1) return nums[0]
let tot = 0
,maxn = -Infinity
for(let i=0; i<nums.length; i++){
if(i >= k){
maxn = Math.max(maxn, tot/k)
tot -= nums[i-k]
}
tot += nums[i]
}
return Math.max(maxn, tot/k).toFixed(5)
}…………………… Leetcode 904. FRUIT INTO BASKETS …………………..
https://leetcode.com/problems/fruit-into-baskets
Acceptance criteria BELOW 50% & MEDIUM| Acceptance at post time 43%.
The problem can be solved using the sliding window pattern because it involves a consecutive set of numbers to find the solution. If we look at example 2. We have an array [0,1,2,2] and we need to find the maximum window length which includes only 2 unique numbers. In this case the answer would be [1,2,2] which is 3 because it is the longest “window” with 2 unique numbers. Just to reinforce, [0,1,2] cannot be a correct answer because it has 3 unique numbers and [2,2] cannot be a correct answer because it only includes 1 unique number.
This question would require an object/dictionary to hold each number in the window. We will add each number to the object/dictionary and keep a track of the frequency of each number. Remember! we can have duplicate but there must be only 2 unique numbers. For instance, [2,1,1,1,1,1,1,1,1,1] is an answer even though it has many 1’s it still only has 2 unique numbers. Anytime the object/dictionary’s length is greater than 2, we will delete the first number and add the next! i.e. Sliding window!
If it’s a bit unclear, the diagrams should help
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1. add current number array[0] which holds value of 0 to the object
2. is the length of the object greater than 2? No.
3. increment index by 1
1. add current number array[1] which holds value of 1 to the object
2. is the length of the object greater than 2? No.
3. increment index by 1
1. add current number array[2] which holds value of 2 to the object
2. Is the length of the object greater than 2? Yes
3. Because it is greater than 2, we want to reduce the window length. To do this we remove the first element in the array, array[0] which holds the value of 0. This means that the object has to remove that element as well.
After moving the sliding window we end up with an array [1,2]
which fits the requirements. Now we can check again. Is the
window length greater than 2? No! So we increment index by 1
- add current number array[3] which holds value of 2 to the object. Since the value 2 exist in the object, we increase the frequency by 1. This means that the length of the object remains the same.
- Is the length of the object greater than 2? No!
- So we increment index by 1.
- Now the traversal is complete as we have reached the
end of the array. Leaving us with an array [1,2,2] which has a length
of 3.
var totalFruit = function(fruits) {
let s = 0
,l = 0
,store = {}
for(let i=0 ; i< fruits.length; i++){
store[fruits[i]] = (store[fruits[i]] || 0) + 1
while(Object.keys(store).length > 2){
if(--store[fruits[s]] == 0) delete store[fruits[s]]
s++
}
l = Math.max(l, -~i - s)
}
return l
}……………… Leetcode 480.SLIDING WINDOW MEDIAN ………………
https://leetcode.com/problems/sliding-window-median/
Acceptance criteria BELOW 50% & HARD| Acceptance at post time 43%.
We are instructed to find the median within the window in this question. In the same manner as question 1, we were keeping a window of length k, performing some calculations, and adjusting the window by removing the first element and adding the next. The difference with this question is that each window must be sorted to obtain the median, but that’s all there is to it! It’s that simple, although you may need to find a way to keep the sorted order of the window. At most, we can end up with a window of 100,000 values and sorting a window of 100,000 numbers is an expensive operation.
In our case, we are using the binary search to find the position of the next element to add to the window instead of sorting on each shift of the window.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Example — [3,10,2,4] k=3 answer = [3,4]
The first window of length k is [3,10,2] — sorted => [2,3,10] therefore the median is 3.
We know the next digit to add is 4. but instead of shifting the window to get [10,2,4] and sorting again, we can reuse the sorted window [2,3,10] removing the first digit from the array which is 3. This leaves us with a sorted window [2,10] then we add the next number 4. This number is added using binary search to find its position in O(log N) time complexity.
var medianSlidingWindow = function (nums, k) {
let med = []
, window = nums.slice(0, k).sort((a, b) => a - b)
, leftIndex = Math.floor((k - 1) / 2)
, rightIndex = Math.ceil((k - 1) / 2)
for (let i = k-1; i < nums.length; i++) {
med.push((window[leftIndex] + window[rightIndex]) / 2)
window = updateWindow(window, nums[i+1-k], nums[i+1])
}
return med
}
function updateWindow(window, numToRemove, numToInsert) {
const removeIndex = window.indexOf(numToRemove)
window.splice(removeIndex, 1)
let left = 0
, right = window.length - 1
while (left <= right) {
let mid = left + right >>> 1
if (window[mid] == numToInsert) {
left = mid
break
} else if (window[mid] < numToInsert) {
left = mid + 1
} else {
right = mid - 1
}
}
window.splice(left, 0, numToInsert)
return window
}You can see that the underlying use of sliding windows remains the same, despite the implementation becoming a little more difficult. To primarily reduce the number of operations from O(N²) and higher to O(N), we use a set structure. In contrast to sliding windows, which should only have 100 operations at most, an array of 100 numbers can result in a set of 100*100 or 10,000 operations when using a quadratic time complexity.
Also, I’m quite sure there are better solutions out there or maybe you can come up with one that improves upon mine.
………………….. POP QUESTION …………………..
https://leetcode.com/problems/longest-subarray-of-1s-after-deleting-one-element
Try it ! before revealing my attempt.
.
.
.
.
.
var longestSubarray = function(nums) {
let start = maxn = ones = 0
for (let i = 0; i < nums.length; i++) {
nums[i] === 1 && ++ones
if ((i - start + 1 - ones) > 1) {
nums[start] === 1 && --ones
++start
}
maxn = Math.max(maxn, i - start);
}
return maxn
}Persistence and Passion Pays. ❤ Thanks for reading
