Understanding the Sliding Window Technique in Arrays

The Sliding Window technique is used to optimize problems that involve a contiguous subarray or substring in an array or string. Instead of using brute force with nested loops, it helps reduce time complexity from O(N²) to O(N) in many cases

Key Benefits of Sliding Window

1. Reduces Unnecessary Computation (Avoids Nested Loops)

   Instead of recalculating sums and checking elements from scratch, we reuse previous calculations by adding new elements and removing old ones.

2. Improves Efficiency

   Many problems that require checking all substrings of a fixed or variable size can be solved in Linear time(O(N)) instead of quadratic time O(N²)).

3. Ideal for Contiguous subarrays or subsequences

   If a problem involves finding maximum/minimum/longest/shortest continuous subarrays, the sliding window technique is a great choice.

4. Optimized Space Usage

   Unlike brute-force methods that might need to store multiple subarrays, the Sliding Window technique often works in-place, reducing extra space complexity.

When to use Sliding Window

1. Fixed-size window → Problems like “Maximum Sum of K-size subarray”

2. Variable-size window → Problems like “Longest Substring Without Repeating Characters”

Without Sliding Window

❌ Brute Force Approach

Find the maximum sum of a subarray with size K = 3 in [1, 3, 5, 2, 8, 6, 7].

let k = 3,
  s = [1, 3, 5, 2, 8, 6, 7];
let maxSum = 0;
for (let i = 0; i <= s.length - k; i++) {
  let sum = 0;
  for (let j = i; j < i + k; j++) {
    sum += s[j]; // Recalculating every subarray
  }
  maxSum = Math.max(maxSum, sum);
}
console.log(maxSum);

🔴 Time Complexity: O(N²) – slow for large inputs

1️⃣ Fixed-Size Sliding Window

Used when the size of the window remains constant throughout the problem.

📌 Example problem: Find the maximum sum of any subarray of size K.

🔹 Brute Force Approach O(N²)

• Loop through all subarrays of size K and calculate the sum each time.

• Inefficient because it repeatedly recalculates overlapping elements.

🔹 Optimized Approach (O(N)) using Sliding Window

Input: arr = [1, 3, 5, 2, 8, 6, 7], K = 3

✅ Instead of calculating each time, we add the new element and remove the old one.

Diagram Explanation

Step 1: Initial window sum → [1, 3, 5]   -> sum = (1+3+5) = 9
Step 2: Slide right (Remove 1, Add 2) → [3, 5, 2] -> sum = (9 - 1 + 2) = 10
Step 3: Slide right (Remove 3, Add 8) → [5, 2, 8] -> sum = (10 - 3 + 8) = 15
Step 4: Slide right (Remove 5, Add 6) → [2, 8, 6] -> sum = (15 - 5 + 6) = 16
Step 5: Slide right (Remove 2, Add 7) → [8, 6, 7] -> sum = (16 - 2 + 7) = 21  ✅ (Max Sum)

⚡ Javascript Code

let k = 3, arr = [1, 3, 5, 2, 8, 6, 7];
let maxsum = 0, slideWindow = 0;
for (let i = 0; i < k; i++) {
    slideWindow += arr[i];
}
maxsum = slideWindow;
for (let i = k; i < arr.length; i++) {
    slideWindow = slideWindow - arr[i - k] + arr[i];
    maxsum = Math.max(slideWindow, maxsum);
}
console.log(maxsum) // Output: 21

✅ Time Complexity: O(N), instead of O(N²)

2️⃣ Variable-Size Sliding Window

used when the window size can grow and shrink dynamically based on the problem's conditions.

📌 Example problem: Find the length of the longest substring without repeating characters.

🔹 Optimized Approach (O(N)) Using Sliding Window

Input:”abcabcbb”

✅ Instead of recomputing the whole substring, we use a hash set to track seen characters and adjust the window dynamically.

Diagram Explanation

⚡ JavaScript Code

let s = 'abcabcbb';
let charSet = new Set();
let left = 0, maxLength = 0;

for (let right = 0; right < s.length; right++) {
    while (charSet.has(s[right])) {
        charSet.delete(s[left]);
        left++;
    }
    charSet.add(s[right]);
    maxLength = Math.max(maxLength, right - left + 1);
}
console.log(maxLength); // Output: 3

🚀 Conclusion

✅ Sliding Window saves time by avoiding unnecessary recalculations.
✅ Works best for contiguous subarray/substring problems.
✅ Understanding Fixed and Variable helps solve problems faster.