Sliding window algorithm

Say, we have an array 'arr' of size 'n'. We will use a window of a certain size that slides through the entire array, giving us all the possible sub-outputs or sub-array.

Thereby, giving us the final answer we need in the best complexity.

Example:-

Implementation:-

package Arrays;

import java.util.Scanner;

public class LargestSumContinuousSubArray {
    // Sliding window algorithm -> O(n)
    static int largestSum_OptimizedV2(int[] arr, int size, int window_size) {
        int curr_sum = 0;
        int max_sum = Integer.MIN_VALUE;

        for (int i = 0; i < size; i++) {
            curr_sum = curr_sum + arr[i];

            // window condition
            if (i >= window_size - 1) {
                // updating maximum sum value
                max_sum = Math.max(curr_sum, max_sum);
                    // deleting the left most element in order to maintain the window size when it iterates
                    curr_sum = curr_sum - arr[i - (window_size - 1)];
                }
            }

        return max_sum;
    }

    // Brute force approach - O(n^2)
    static int largestSum(int[] arr, int size) {
        int max_sum = -999;
        int sum = 0;

        for (int i = 0; i < size; i++) {
            sum = arr[i];
            for (int j = i + 1; j < size; j++) {
                sum = sum + arr[j];

                if (sum > max_sum)
                    max_sum = sum;
            }
        }
        return  max_sum;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int size = sc.nextInt();

        int[] arr = new int[size];
        for (int i = 0; i < size; i++)
            arr[i] = sc.nextInt();

        int window_size = sc.nextInt();

        System.out.println(largestSum(arr, size));
        System.out.println(largestSum_OptimizedV2(arr, size, window_size));
    }
}

Dynamic size sliding window:-

Similar to the sliding window, except that the window can shrink and expand upon iteration.

Example:-

• In the 3rd iteration, we got a subarray with sum = 8 and size = 3. Thus, we got the final output.

• In the 5th iteration, we do get a subarray with sum = 8. However, the size remains the same. Thus, we neglect it and move forward by shrinking it.

• In the 6th iteration, we get a subarray with sum = 8 and size = 2. Thus, it became our new output.

• In the 8th iteration, we do get a subarray with sum = 8. However, the size remains the same. Thus, we neglect it and move forward by shrinking it.

• In the 9th iteration, we get a subarray with sum = 8 and size = 1 which is our base case by default. Therefore, we stop the iteration.

Implementation:-

package Arrays;

import java.util.Scanner;

public class SmallestSubArrayWithGivenSum {

    /*
    Given an array 'arr' of size 'n'. Find the smallest sub-array size with the given target sum.
    Dynamic sliding window - O(n)
    */
    static int smallestSubArray(int[] arr, int size, int target_sum) {
        int minSumArraySize = Integer.MAX_VALUE;
        int curr_sum = 0;
        int window_start, window_end = window_start = 0;

        while (window_end < size) {
            curr_sum = curr_sum + arr[window_end];

            while (curr_sum >= target_sum) {
                // getting the size of the sub-array with minimum size
                minSumArraySize = Math.min(minSumArraySize, window_end - window_start + 1);
                // eliminating the first index element from sub-array
                curr_sum = curr_sum - arr[window_start];
                window_start++;
            }

            window_end++;
        }

        return minSumArraySize;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int size = sc.nextInt();

        int[] arr = new int[size];
        for (int i = 0; i < size; i++)
            arr[i] = sc.nextInt();

        int target_sum = sc.nextInt();

        System.out.println(smallestSubArray(arr, size, target_sum));
    }
}