Educative Answers Team

Free System Design Interview Course

Get Educative's definitive System Design Interview Handbook for free.

The **sliding window algorithm** can be used to solve problems that involve linear sequences, such as arrays. A window is a contiguous sequence which is part of an array. As the name suggests, the window is * slid* over the array. Some operations are performed on elements within this window, and then the window is slid further.

Letâ€™s look at an example problem to make things clearer.

We are given an array of size $N$; we need to calculate the maximum sum of $K$ consecutive elements.

The most obvious solution would be to find all possible blocks of $K$ elements, and pick the one with the largest sum.

The optimal solution, however, uses the sliding window algorithm. Here is how it works:

- Add the first $K$ elements together, and store the sum in the variable
`currentSum`

. Since this is the first sum, it is also the current maximum, so store it in variable`maximumSum`

as well. - Since the window size is $K$, we
the window one place to the right, and compute the sum of the elements in the window.**slide** - If the
`currentSum`

is larger than the`maximumSum`

, then update the maximum and repeat step 2. This is illustrated below:

We're given this array of size 6, and need to find 3 consecutive elements which give the maximum sum.

This is how it is implemented in C++:

int maxSum(int arr[], int k, int n, int &start, int &end){if (k > n){return -1;}int maximumSum = 0;int currentSum = 0;// Compute the initial sum of first K elements.for (int i=0;i<k;i++){currentSum += arr[i];}maximumSum = currentSum;start = 0;end = k - 1;// Sliding the window and updating maximumSumfor (int i=k;i<n;i++){// Add the rightmost element to the window and// discard the leftmost element from the windowcurrentSum += arr[i] - arr[i-k];if (currentSum > maximumSum){maximumSum = currentSum;start = i - k + 1; // the window starts one ahead of the element that was removed from the leftend = i; // the window goes upto the position of the newly added element from the right}}return maximumSum;}// driver codeint main(){int start = 0;int end = 0;int arr[] = {6, 2, -1, 9, 1, -2};int k = 3;int n = (sizeof(arr)/sizeof(*arr));int maxsum = maxSum(arr, k, n, start, end);cout << "The maximum sum is " << maxsum;cout << " from position " << start << " till " << end << endl;return 0;}

The function `maxSum()`

is called with the following parameters:

`arr[]`

, which is the array of $N$ integers.`k`

, which is the window size, and`n`

, which is the size of array`arr`

.`start`

and`end`

will store the starting and ending indexes of the window with the maximum sum. These are initially passed as 0.

- In
**lines 10-16**, the first`k`

elements are added together, the sum of this is also the maximum sum yet. The starting and ending positions are also updated. **Lines 18-29**contain the window sliding algorithm, but**line 22**is the most important line of code. Here the previous sum, stored in`currentSum`

, is used to calculate the new current sum. This new current sum is found by adding the windowâ€™s new element and removing the old one.**Lines 25-27**are in charge of updating the`maximumSum`

, if it is smaller than the`currentSum`

, as well as the starting and ending positions of the window where the maximum was found.

RELATED TAGS

Copyright Â©2023 Educative, Inc. All rights reserved

Keep Exploring

Related Courses