A sliding window is one of the very important categories and can come in handy while solving some Array or Linked List-based problems.
A sliding window is one of the very important categories and can come in handy while solving some Array or Linked List-based problems.
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.
Given an array of size “n” we are supposed to find the sum of all subarrays of size “k” in it.
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:
(n - k + 1)
.So, the brute force approach will be to calculate the sum of every “k” element and then store it in the list.
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.
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;
}
17 13 6 2 8
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.
© 2022 - All Rights Reserved.