Overview🧐

Sliding Window Algorithm is an approach or technique for reducing the complexity of algorithms. It is used such that the need for reusing the loops gets lessened and hence the program gets optimized. In this method, we reuse the result of the previous step to compute the result of the next step.

• In this blog, we will walk through the Sliding window algorithm. show how to use it, and when to use it.

• This blog also includes steps to solve Sliding window problems.

• This blog contains a Maximum Sum Of K Size Subarray example of the Sliding window technique.

Sliding window 🔥

The sliding window pattern is a technique for solving problems on sequences or arrays. It works by maintaining a window of fixed size over the sequence, and repeatedly updating the window as we move through the sequence. The goal is to find the optimal solution within the window, such as the maximum sum, minimum sum, or longest substring.

How to use Sliding Window Technique? 🤔🧠

The general steps to use the sliding window technique are:

1. Find the size of the window required

2. Compute the result for the first window, i.e. from the start of the data structure

3. Then use a loop to slide the window by one, and keep computing the result window by window.

When to use it? ⌛

The sliding window technique can be used when:

• The size of the window for computation is fixed throughout the problem

• The problem requires finding a maximum or minimum value that occurs in a range or “window” over the given sequence

Tip⚡:

Identify if the problem can be solved using the sliding window technique by looking for keywords such as array, string, subarray, substring, largest sum, maximum sum, minimum sum, etc.

Basic Steps to Solve Sliding Window Problems🪜:

Let's describe the basic steps involved in solving problems using the Sliding Window pattern:

1. Initialize variables, such as window start, window end, and other relevant variables specific to the problem.

2. Iterate through the data structure, moving the window one element at a time.

3. Perform the necessary calculations or operations within the window to obtain the desired result.

4. Update the solution or store the relevant information.

5. Adjust the window's boundaries based on the problem's requirements and constraints.

6. Continue iterating until the end of the data structure is reached.

7. Return the final result.

Example of sliding window

Maximum Sum Of K Size Subarray (Sliding Window)

Problem: Maximum Sum Of K Size Subarray (Sliding Window)

Array: [2, 6, -9, 7, -1, 5, 4]

K: 3 (Size of the subarray)

Approach🤯🧩

We can use the sliding window technique to solve this problem. We will maintain a window of size k and slide it over the array from left to right. At each step, we will add the new element at the end of the window and subtract the first element from the previous window. This way, we will keep track of the current sum of k elements in constant time. We will also keep track of the maximum sum so far and update it whenever we find a larger sum.

for a better understanding, take a look below at my drawings✏️😁

Intuition:

Array:

Visualization:

In this table, each row represents an iteration of the sliding window. The columns show the values for arr (the current array element), k, WindowStart, WindowEnd, sum (the sum of elements within the window), and max (the maximum sum encountered so far).

Note:📝

The last row with 4 in the arr the column is left blank for the remaining columns since it doesn't contribute to the sliding window anymore.

import java.util.Scanner; // import Scanner class for input

public class Solution {
    public int maxSum(int[] arr, int k) {
        // edge case: if array is null or empty or k is invalid
        if (arr == null || arr.length == 0 || k <=0 || k > arr.length) {
            return -1; // return some invalid value
        }
        // initialize variables
        int WindowStart = 0; // start index of window
        int WindowEnd = 0; // end index of window
        int sum = 0; // current sum of k elements in window
        int max = Integer.MIN_VALUE; // maximum sum so far

        // loop over array from start to end
        while (WindowEnd < arr.length) {
            // expand window by adding new element at end
            sum += arr[WindowEnd];
            // check if window size is equal to k
            if (WindowEnd - WindowStart + 1 == k) {
                // update max if needed
                max = Math.max(max, sum);
                // shrink window by removing first element from start
                sum -= arr[WindowStart];
                // increment start index
                WindowStart++;
            }
            // increment end index
            WindowEnd++;
        }
        // return max
        return max;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in); // create Scanner object for input
        System.out.println("Enter the size of the array: ");
        int n = sc.nextInt(); // read the size of the array from input
        System.out.println("Enter the elements of the array: ");
        int[] arr = new int[n]; // create an array of size n
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt(); // read the elements of the array from input
        }
        System.out.println("Enter the size of the subarray: ");
        int k = sc.nextInt(); // read the size of the subarray from input
        Solution sol = new Solution(); // create a Solution object
        int result = sol.maxSum(arr, k); // call the maxSum method with the array and subarray size as arguments
        System.out.println("The maximum sum of " + k + " size subarray is: " + result); // print the result
    }
}

Time⌚ and space 💾 complexity:

The time complexity of this algorithm is O(n), where n is the length of the array. This is because we are iterating over the array only once and doing constant work at each step.

The space complexity of this algorithm is O(1), as we are not using any extra space apart from a few variables.