Sliding Window in Java: The Trick That Replaces Nested Loops

#devops #code #datastructures #datascience

Many beginners write nested loops for subarray problems.

That leads to O(n²) time complexity.

But what if you could solve the same problem in O(n)?

That’s where Sliding Window comes in.

What is Sliding Window?

Imagine a window covering part of the array.

Instead of recalculating everything:

You remove one element
You add one element

Reuse previous computation

Fixed-Size Sliding Window

Problem:

Find maximum sum of subarray of size k

public static int maxSumFixedWindow(int[] arr, int k) {
int windowSum = 0;

for (int i = 0; i < k; i++) windowSum += arr[i];

int maxSum = windowSum;

for (int i = k; i < arr.length; i++) {
    windowSum = windowSum - arr[i - k] + arr[i];
    maxSum = Math.max(maxSum, windowSum);
}

return maxSum;

}

Complexity:

Time → O(n)
Space → O(1)

Fixed-Size Sliding Window
💡 Problem:

Find maximum sum of subarray of size k

public static int maxSumFixedWindow(int[] arr, int k) {
int windowSum = 0;

for (int i = 0; i < k; i++) windowSum += arr[i];

int maxSum = windowSum;

for (int i = k; i < arr.length; i++) {
    windowSum = windowSum - arr[i - k] + arr[i];
    maxSum = Math.max(maxSum, windowSum);
}

return maxSum;

}
⏱️ Complexity:
Time → O(n)
Space → O(1)

Variable-Size Sliding Window

Problem:

Find longest subarray with sum ≤ target

public static int longestSubarraySumAtMost(int[] arr, int target) {
int left = 0, sum = 0, maxLen = 0;

for (int right = 0; right < arr.length; right++) {
    sum += arr[right];

    while (sum > target) {
        sum -= arr[left];
        left++;
    }

    maxLen = Math.max(maxLen, right - left + 1);
}

return maxLen;

}

Complexity: