Sliding Window Algorithm - The Coding Shala

Last Updated: 27-Jan-2021
Home >> Algorithms >> Sliding Window Algorithm

 In this post, we will learn what is Sliding Window Algorithm and how to implement it in Java.

Sliding Window Algorithm

What do you mean by Sliding Window? A window of fixed length can be slide over the input. The sliding window algorithm is used to reduce the time complexity by converting the nested for loops into a single for loop.

Let's take an example and understand the sliding window problem. we have given an array of integers of size n and need to find the maximum sum of k consecutive elements in the array.

Input array:  { 100, 200, 300, 400}
k = 2
Output: 700

So how we solve this problem we start outer loop from index 0 and inner loop runs till i+k size every time and compare the maximum sum.

The following is the code for this brute force approach.

Java Program: 

static int maxSum(int arr[], int n, int k) 
    { 
        // Initialize result 
        int max_sum = Integer.MIN_VALUE; 
  
        // Consider all blocks starting with i. 
        for (int i = 0; i < n - k + 1; i++) { 
            int current_sum = 0; 
            for (int j = 0; j < k; j++) 
                current_sum = current_sum + arr[i + j]; 
  
            // Update result if required. 
            max_sum = Math.max(current_sum, max_sum); 
        } 
  
        return max_sum; 
    } 

Now how do we solve this problem using a sliding window? We will take a window of size k and then move that window to find the maximum sum.

 Array:  {100, 200, 300, 400}         window size:  2
                ----------
                  300
        ---------
      500
               ----------
    700
 max output it 700.

So using Sliding Window Algorithm we can solve this problem using a single loop.

Java Program: 
//sliding window algorithm
//thecodingshala.com

class Main{
	
	public static int sliding_window(int[] input, int k) {
		int len = input.length;
		int max_sum = 0;
		//compute first window
		for(int i=0; i<k; i++) {
			max_sum += input[i];
		}
		
		int window_sum = max_sum;
		//compute window sum every time and check with max_sum
		for(int i=k; i<len; i++) {
			window_sum += input[i]-input[i-k];
			max_sum = Math.max(max_sum, window_sum);
		}
		
		return max_sum;
	}
	
	public static void main(String[] args) {
		int[] input = {100, 200, 300, 400};
		int k = 2;
		System.out.println("Max sum is: "+ sliding_window(input, k));
	}
}


Other Posts You May Like
Please leave a comment below if you like this post or found some errors, it will help me to improve my content.

Comments

Popular Posts from this Blog

Shell Script to find sum, product and average of given numbers - The Coding Shala

Shell Script to Create a Simple Calculator - The Coding Shala

Add two numbers in Scala - The Coding Shala

New Year Chaos Solution - The Coding Shala

Richest Customer Wealth LeetCode Solution - The Coding Shala