Sliding Window Technique
The Sliding Window algorithm is a important fashion used in computer wisdom
and data wisdom to efficiently reuse sequences or arrays. It’s particularly
useful in scripts where we need to find a subarray, substring, or any
subsequence that satisfies a certain condition.
Before learning further about the sliding window algorithm let’s understand why we need a sliding window and what are the benefits of using it.
Problem Statement:-
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. Value of k equal to 3.
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.
Brute Force Approach:
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 sub entries to be considered.
Now we will see how this task can be achieved in much lower time, ca n’t believe
it? Look for yourself below.
Optimised Approach:
The fundamental concept is to define the window using two pointers, a left pointer, plus a right pointer.
originally, before we start the algorithm, the maximumSum variable is initialized to 0. Also, k is taken as 3
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.
Algorithm for above question:
- Initialize two pointers, left and right, to the start of the array.
2. Move the right pointer to form an initial window of size k.
3. Compute the sum of elements in the current window.
4. Slide the window by incrementing both left and right pointers.
5. Recalculate the sum for the new window.
6. Repeat steps 4 and 5 until the right pointer reaches the end of the array.
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 the previous window and adding the last element of the
// current window. This way our window moves forward.
// Also updating the maximum sum to the current window sum if the current window
// sum is greater than the 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;
}
}Hence the Time Complexity gets reduced to O(N), where N is the size of the input array because in this approach we run only one loop.
Here the Window Size is fixed i.e. value of K hence it is known as Fixed Size Sliding Window Algorithm.
Now if the size of the window changes during the algorithm’s execution based on certain conditions.
Let’s look at the Variable Size Sliding Window Algorithm with an example:
Problem Statement:-
Minimum Size Subarray Sum : find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn’t one, return 0 instead.
Brute Force Approach:
A simple solution is to use two nested loops. The outer loop picks a starting element, the inner loop considers all elements (on right side of current start) as ending element.
Whenever sum of elements between current start and end becomes more than the given number, update the result if current length is smaller than the smallest length so far.
Time Complexity: O(n^2).
Optimised Approach:
Algorithm for above question :
- Initialize two pointers left and right to the first element of the array.
2. Initialize a variable “sum” to be the sum of the first element, i.e., nums[0].
3. Initialize a variable “minlen” to a value larger than the size of the array, say n+1, as the length of the shortest subarray is less than or equal to the length of the array.
4. Loop through the array until the right pointer reaches the end of the array:
a. Add the value of nums[right] to sum.
b. If the sum becomes greater than or equal to the target sum i. Update the value of minlen to be the minimum of minlen and (right-left+1). ii. Keep moving the left pointer to the right until the sum becomes less than the target sum s.
c. Increment the right pointer.
5. Return minlen.
public int minSubArrayLen(int s, int[] nums) {
// Check for edge case
if (nums == null || nums.length == 0)
return 0;
// Initialize variables
int minLen = Integer.MAX_VALUE;
int sum = 0;
int left = 0;
// Loop through the array
for (int i = 0; i < nums.length; i++) {
// Update sum
sum += nums[i];
// While sum is greater than or equal to s, update minLen
while (sum >= s) {
minLen = Math.min(minLen, i - left + 1);
sum -= nums[left++];
}
}
// Return minLen
return minLen == Integer.MAX_VALUE ? 0 : minLen;
}The time complexity of this approach is O(N), where N is the size of the input array, as we loop through the array only once.
Hence, we can infer that the biggest advantage of the Sliding Window technique is for reducing time complexity and enhancing program performance.
Depending on the problem, it can solve ones with linear or logarithmic time complexity.
It is also a memory-efficient algorithm since it only needs a fixed amount of memory.
