Introduction to Sliding Window

A sliding window is one of the very important categories and can come in handy while solving some Array or Linked List-based problems. Let’s try to understand the concept of the sliding window with some examples.

Example 1:

Input: arr: [2, 6, 9, -2, -1, 5, 4], k: 3
Output: [17, 13, 6, 2, 8]

Let’s try to observe the above example:

1. The size of the output array will be (n - k + 1).
2. Solution :
   1. 0th Index (sum of subarray from index 0-2): 2 + 6 + 9 = 17 
   2. 1st Index (sum of subarray from index 1-3): 6 + 9 + (-2) = 13
   3. 2nd Index (sum of subarray from index 2-4): 9 + (-2) + (-1) = 6
   4. 3rd Index (sum of subarray from index 3-5): (-2) + (-1) + 5 = 2
   5. 4th Index (sum of subarray from index 4-6): (-1) + 5 + 4 = 8

So, the brute force approach will be to calculate the sum of every “k” element and then store it in the list.

Brute Force:

import java.io.*;
 
class Innoskrit {
    public static int[] subarraySumKSize(int arr[], int k) {
        int n = arr.length;
        int ans[] = new int[n - k + 1];
        for(int i = 0; i < n - k + 1; i++) {
            int sum = 0;
            for(int j = i; j < i + k; j++) {
                sum += arr[j];
            }
            ans[i] = sum;
        }
        return ans;
    }
    public static void main (String[] args) {
        int arr[] = {2, 6, 9, -2, -1, 5, 4};
        int k = 3;
        int ans[] = subarraySumKSize(arr, k);
        for(int a : ans) {
            System.out.print(a + " ");
        }
    }
}

def subarraySumKSize(arr, k):
    ans = []
 
    for i in range(len(arr) - k + 1):
        sum = 0
        for j in range(i, i + k):
            sum += arr[j]
        ans.append(sum)
    return ans
             
if __name__ == '__main__':
    ans = subarraySumKSize([2, 6, 9, -2, -1, 5, 4], 3)
    for a in ans:
        print(a, end = " ")

#include <iostream>
#include <vector>
using namespace std;
 
class Innoskrit {
    public:
        static vector<int> subarraySumKSize(const vector<int>& arr, int k) {
            int n = arr.size();
            vector<int> ans(n - k + 1);
            for(int i = 0; i < n - k + 1; i++) {
                int sum = 0;
                for(int j = i; j < i + k; j++) {
                    sum += arr[j];
                }
                ans[i] = sum;
            }
            return ans;
        }
};
 
int main(int argc, char * argv[]) {
    vector<int> ans = Innoskrit::subarraySumKSize(vector<int>{2, 6, 9, -2, -1, 5, 4}, 3);
    for (int a : ans) {
        cout << a << " ";
    }
    cout << endl;
}

Time Complexity for the above brute force approach will be O(n * k). This is because for every element in the input array we are calculating the sum of every next k element. Can we reduce this time? Can you go up and try to find out the part which is causing inefficiency?

If you will see the above approach carefully you will find out that there is some part that we are repeating in every iteration.

In the first iteration, we took the sum of (2, 6, 9) and in the second iteration sum of (6, 9, -2). But if we see, we already have the sum of 6 and 9 from our previous iteration and we are repeating this unnecessarily in the next iteration. Now, our task is to identify how we can utilize this sum.

Now let’s try to visualize it.

Step 1: Sum of 3 consecutive elements.

Step 2: We have a Sum of (2,6,9) and we want the sum of (6,9,-2). So, remove 2 and add (-2).

Step 3:

Step 4:

Step 5:

We can visualize each subarray as a sliding window of ‘3’ elements. This means when we will move to the next element we will simply slide the window by one element and we will subtract the element going out of the window and add the one which is now newly included in the window.

Let’s code this.

Code:

import java.io.*;
class Innoskrit {
    public static int[] subarraySumKSize(int arr[], int k) {
        int n = arr.length;
        int[] ans = new int[n - k + 1];
        int windowSum = 0;
        int windowStart = 0;
        for (int windowEnd = 0; windowEnd < n; windowEnd++) {
            windowSum += arr[windowEnd];
            if(windowEnd >= k - 1) {
                ans[windowStart] = windowSum;
                windowSum -= arr[windowStart];
                windowStart++;
            }
       }
       return ans;
   }
  
    public static void main (String[] args) {
        int ans[] = subarraySumKSize(new int[] {2, 6, 9, -2, -1, 5, 4}, 3);
        for(int a : ans) {
            System.out.print(a + " ");
        }
    }
}

def subarraySumKSize(arr, k):
    ans = []
    windowSum = 0
    windowStart = 0
 
    for windowEnd in range(len(arr)):
        windowSum += arr[windowEnd]
        if windowEnd >= k - 1:
            ans.append(windowSum)
            windowSum -= arr[windowStart]
            windowStart += 1
 
    return ans
 
if __name__ == '__main__':
    ans = subarraySumKSize([2, 6, 9, -2, -1, 5, 4], 3)
    for a in ans:
        print(a, end = " ")

#include <iostream>
#include <vector>
using namespace std;
 
class Innoskrit {
    public:
        static vector<int> subarraySumKSize(const vector<int>& arr, int k) {
                        int n = arr.size();
            vector<int> ans(n - k + 1);
            int windowSum = 0;
            int windowStart = 0;
            for(int windowEnd = 0; windowEnd < n; windowEnd++) {
                windowSum += arr[windowEnd];
                if(windowEnd >= k - 1) {
                    ans[windowStart] = windowSum;
                    windowSum -= arr[windowStart];
                    windowStart++;
                }
            }
            return ans;
        }
};
 
int main(int argc, char * argv[]) {
    vector<int> ans = Innoskrit::subarraySumKSize(vector<int>{2, 6, 9, -2, -1, 5, 4}, 3);
    for (int a : ans) {
        cout << a << " ";
    }
    cout << endl;
}

Output:

17 13 6 2 8

Time Complexity:

The Sliding window refrains us from traversing the complete subarray of size k to find the sum. In the efficient approach, we are traversing every element only once. Hence, Time Complexity will be O(n).

In this chapter of Sliding Window, we will learn to apply the sliding window approach to solve some problems.
The sliding window can come in handy in the problems where we are dealing with continuous subarrays. But there might be some cases in which the size of the sliding window is not fixed. In such scenarios, we will expand or shrink our window size according to our needs.
Now, Let’s move to our first problem.