[DSA] Sliding Window Algorithm

The Sliding Window Algorithm is a powerful technique used to reduce the time complexity of problems involving arrays or strings—specifically those that require finding a sub-segment that meets certain criteria.
Instead of using nested loops O(n^2), the sliding window maintains a dynamic range that "slides" across the data, usually bringing the complexity down to O(n).

Problem:Find the maximum sum of a contiguous subarray of size `k`.

public class SlidingWindow {

public static int findMaxSum(int[] arr, int k) {

int n = arr.length;

if (n < k) return -1;
int windowSum = 0; // 1. Compute sum of the first window for (int i = 0; i < k; i++) {

windowSum += arr[i];

}
int maxSum = windowSum;

// 2. Slide the window from index k to n-1

for (int i = k; i < n; i++) {

// Add the next element, remove the first element of the previous window

windowSum += arr[i] - arr[i - k];

maxSum = Math.max(maxSum, windowSum);

}

return maxSum;

}

}