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.
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.
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:
- 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.
- 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.
- Update the maximum if the currentSum is greater than the maximumSum, and repeat step 2.
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
C++ Code for Sliding Window Algorithm
Java Code for Sliding Window Algorithm
The time complexity of the above code is O(N), as in this approach we run only one loop to compute the maximum sum.
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.