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

• Binary Search Algorithm
• The Big O Notation
• Bucket Sort Algorithm
• Insertion Sort Algorithm
• Merge Sort Algorithm

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