Siding window is a method for iterating over a linear collection by maintaining a window range indices (a group of consecutive elements) to satisfy the problem constraints

Sliding window is an improvement over brute force iteration to reduce the time complexity

Problem

  • Given an array A and a number k

  • Write an algorithm to find the maximum sum of k consecutive elements in A

Example

  • Input: [5, 7, 2, 9, 4] and 2

  • Expected output: 13

  • Explanation: 9 and 4 are 2 consecutive elements have maximum sum

Approach 1: Brute force

  • Iterating over a one by one element to find max sum
public class SubarrayMaxSumBruteforce {  
    public static int maxSumBruteforce(int[] A, int k) {
        int maxSum = Integer.MIN_VALUE;

        for (int i = 0; i < A.length - k + 1; i++) {
            int currentSum = 0;

            for (int j = 0; j < k; j++) {
                currentSum += A[i+j];
            }

            if (currentSum > maxSum) maxSum = currentSum;
        }

        return maxSum;
    }

    public static void main(String[] args) {
        System.out.println(maxSumBruteforce(new int[]{5, 7, 2, 9, 4}, 2));
    }
}
  • Output
13

  • Time complexity: O(n*k)

  • Space complexity: O(1)

Approach 2: Sliding window

  • Iterating over a window by window to find max sum
public class SubarrayMaxSumWindowSliding {  
    public static int maxSumWindowSliding(int[] A, int k) {
        int windowsSum = 0, maxSum = Integer.MIN_VALUE;

        for (int i = 0; i < k; i++) {
            windowsSum += A[i];
        }

        for (int i = k; i < A.length; i++) {
            windowsSum += A[i] - A[i-k];
            if (windowsSum > maxSum) maxSum = windowsSum;
        }

        return maxSum;
    }

    public static void main(String[] args) {
        System.out.println(maxSumWindowSliding(new int[]{-5, -7, -2, -9, -4}, 2));
    }
}
  • Output
-9

  • Time complexity: O(n)

  • Space complexity: O(1)

Algorithm