# Sliding Window Algorithm (With Java, C++ and Python Code)

If you study Computer Science, you are bound to come across various algorithms. One such algorithm is the sliding window algorithm, which has its use in cases across fields like computer networks and data communication. It is used in the TCP (Transmission Control Protocol) for flow control. Apart from this, several competitive problems can be formed on this algorithm; therefore, you must understand this algorithm to ace the interview of your dream company. In this article, we discuss what is the sliding window Algorithm and its implementation in three different programming languages.

## Problem Statement

Let us first understand the problem before going further with its approach. The problem statement is as follows, find the largest sum of K consecutive entries, given an array of size N. Not sure if you get it? Don’t worry we will understand this by taking an example.

Suppose that the following array is given to us and we are required to find 3 consecutive numbers in this array that give us the largest sum. So, k is equal to 3 in this case.

arr = [16, 12, 9, 19, 11, 8]

Blocks containing three consecutive entries in the given array are: [16, 12, 9], [12, 9, 19], [9, 19, 11], [19, 11, 8]. Now we calculate the sum of each block, the sum of each corresponding block is as follows: 37, 40, 39, 38. Out of all these calculated sums, the maximum sum is 40. Therefore, our output is 40.

### Naive approach

There exists an inefficient but simple approach to solve this problem. You may be wondering why are we discussing this approach when it is not efficient enough? Well, one must know the importance of a good approach, right? Also, understanding this approach allows us to build upon the knowledge to allows us to develop a more efficient algorithm called the sliding window algorithm.

In this approach, we begin with the first index and add up until the kth element is reached. For all possible consecutive blocks or groups of k elements, we repeat the process. This approach uses a nested for loop; the outer for loop begins with the first element of the k-element block, and the inner or nested loop continues until the kth element is reached.

As this approach contains two nested loops therefore the complexity of this approach is O(N*K). Where n is the size of the array given to us and k is the number of consecutive subentries to be considered. Now what we tell you that this task can be achieved in much less time, can’t believe it? Look for yourself below.

### Sliding Window Approach

To understand this approach let us take the help of an analogy. Consider a window of length n and a pane that is fixed in it, of length k. Now, that the pane is originally at the far left, or 0 units from the left. Co-relate the window with the n-element array arr[] and the pane with the k-element current sum. If we apply force to the window so that it will move a unit distance forward. The following k components will be covered by the pane.

The current sum at each step is calculated by adding the last element of the current block and subtracting the first element of the previous block. That’s it! This is the whole sliding window algorithm. Easy right? Let us now look at the algorithm of this approach.

## Sliding Window Algorithm

Here are the steps for applying the sliding window algorithm:

1. Add the first K components together and save the result in the currentSum variable. Because this is the first sum, it is also the current maximum; thus, save it in the variable maximumSum.
2. As the window size is K, we move the window one place to the right and compute the sum of the items in the window.
3. Update the maximum if the currentSum is greater than the maximumSum, and repeat step 2.

### Example

Let us now take an example to understand the algorithm better. Initially, before we start the algorithm, the maximumSum variable is initialized to 0. Also, k is taken as 3 in this example. We begin with finding the sum of the first 3 consecutive numbers, i.e., from index 0 to 2. The sum of this initial window comes out to be 37 and is stored in the currentSum variable. Now since the currentSum is greater than maximumSum, therefore, The value of the maximumSum variable is updated to store 37. The window is slid by a unit distance, to cover the next 3 consecutive numbers. The sum of the new current window is evaluated by subtracting 16 from the currentSum and adding 19 to it. The currentSum is now equal to 40. The latest currentSum value is now compared with the maximumSum since it is greater, therefore, the maximumSum variable will be made to store 40. The window is again shifted to cover the next 3 consecutive numbers. To get the sum of this window, 12 is deducted from the currentSum and 11 is added which results in 39. As this value is lesser than maximumSum, therefore the value of maximumSum remains unchanged. The window now shifts to cover the last 3 consecutive numbers. The sum at this step is evaluated to be equal to 38. As this value is also less than the value of maximumSum (40), its value remains unaffected. All the possible combinations of three consecutive numbers have now been identified and their sums have been evaluated. In the end, the maximumSum, which is identified as 40, is returned.

### Python Code for Sliding Window Algorithm

```def maxSum(arr, k):
# length of the array
n = len(arr)

# length of array must be greater
# window size
if n < k:
print("Invalid")
return -1

# sum of first k elements
window_sum = sum(arr[:k])
max_sum = window_sum

# remove the  first element of previous
# window and add the last element of
# the current window to calculate the
# the sums of remaining windows by
for i in range(n - k):
window_sum = window_sum - arr[i] + arr[i + k]
max_sum = max(window_sum, max_sum)

return max_sum

arr = [16, 12, 9, 19, 11, 8]
k = 3
print(maxSum(arr, k))```

### C++ Code for Sliding Window Algorithm

```#include
using namespace std;

// Returns maximum sum in a subarray of size k.
int maxSum(int arr[], int n, int k) {
// n must be greater
if (n < k) {
cout << "Invalid";
return -1;
}

//sum of first window of size k
int window_sum = 0;
for (int i = 0; i < k; i++)
window_sum += arr[i];

// Compute sums of remaining windows by
// removing first element of previous
// window and adding last element of
// current window.
int max_sum = window_sum;
for (int i = k; i < n; i++) {
window_sum += (arr[i] - arr[i - k]);
max_sum = max(max_sum, window_sum);
}
return max_sum;
}

int main(){
int n = 5 , k = 3;;
int arr[] = { 16,12,9,19,11,8};
cout << maxSum(arr, n, k);
return 0;
}
```

### Java Code for Sliding Window Algorithm

```public class slidingwindow {

static int maxSum(int[] arr,int k){
//length of the array
int n=arr.length;

//length of array(n) must be greater than window size(k)
if(n<k){
System.out.println("Invalid");
return -1;
}

//sum of first k(window size) elements
int window_sum=0;
for(int i=0;i<k;i++) window_sum+=arr[i];

int max_sum=window_sum;

//Calculating sums of remaining windows by
//removing first element of previous window
//and adding last element of current window
//this way our window moves forward.

//Also updating the maximum sum to current window sum
// if the current window sum is greater
// than existing maximum sum.
for(int i=k;i<n;i++){
window_sum+=(arr[i]-arr[i-k]);
max_sum=Math.max(window_sum,max_sum);
}

return max_sum;
}

public static void main(String[] args) {
//window size
int k=3;
int[] arr={16, 12, 9, 19, 11, 8};
System.out.println(maxSum(arr,k));
}

}```

Output:

`40`

### Time complexity

The time complexity of the above code is O(N), as in this approach we run only one loop to compute the maximum sum.

## Conclusion

The Sliding window Algorithm is a crucial topic for competitive coding. A lot of problems can be solved using this algorithm by doing some small tweaks in it. In this article, we first understood the problem statement, and we then saw the naïve approach. We, at last, learned a more efficient approach along with its code in C++, Java, and python. Our experts are available 24/7 to help you with any coding issues you may have.

### FavTutor - 24x7 Live Coding Help from Expert Tutors! 