Leet Code - Sliding Window - maximum sum of a subarray of size k

 

---

Sliding Window Technique 

---

What is Sliding Window?

Sliding window is a way to process a subset (window) of elements in an array or string efficiently by moving the window step-by-step, instead of recalculating everything every time.

---

Example Problem:

Find the maximum sum of a subarray of size k

Given:
nums = [2, 1, 5, 1, 3, 2], and k = 3 (window size)

Goal: Find the maximum sum of any consecutive 3 elements.

---

Step-by-step C++ code:

#include <iostream>
#include <vector>
using namespace std;

int maxSumSubarray(vector<int>& nums, int k) {
    int windowSum = 0, maxSum = 0;
    int windowStart = 0;

    // Loop through each element to slide the window
    for (int windowEnd = 0; windowEnd < nums.size(); windowEnd++) {
        windowSum += nums[windowEnd];  // Add the next element into the window

        // When we hit size k, start sliding the window
        if (windowEnd >= k - 1) {
            maxSum = max(maxSum, windowSum);    // Update maxSum if needed
            windowSum -= nums[windowStart];     // Remove the element going out of the window
            windowStart++;                       // Slide the window forward
        }
    }
    return maxSum;
}

int main() {
    vector<int> nums = {2, 1, 5, 1, 3, 2};
    int k = 3;
    cout << "Maximum sum of subarray of size " << k << " is " << maxSumSubarray(nums, k) << endl;
    return 0;
}

---

What happens in each iteration? (Detailed):

Iteration (windowEnd)	windowSum (after adding nums[windowEnd])	windowStart	maxSum update?	windowSum after sliding	Notes
0	2	0	No	—	Window size < k (1 < 3)
1	2 + 1 = 3	0	No	—	Window size < k (2 < 3)
2	3 + 5 = 8	0	Yes (maxSum=8)	8 - 2 = 6	Window size = k (3)
3	6 + 1 = 7	1	No (maxSum=8)	7 - 1 = 6	Slide window by removing nums[0]=2
4	6 + 3 = 9	2	Yes (maxSum=9)	9 - 5 = 4	Slide window by removing nums[1]=1
5	4 + 2 = 6	3	No (maxSum=9)	6 - 1 = 5	Slide window by removing nums[2]=5

---

Explanation Summary:

• We keep adding elements to windowSum until the window reaches size k.

• Once the window size is k, we compare and update maxSum.

• Then slide the window forward:

  • Remove the element at windowStart from the sum.

  • Increment windowStart to shrink the window from the left.

• Repeat until the end.

 Time and Space Complexity

• Time Complexity: O(n)
  ✔️ Each element is added and removed from windowSum once — very efficient.

• Space Complexity: O(1)
  ✔️ Uses only a few integer variables (no extra arrays or data structures).

Can We Do Better?

Short answer: No — not for this specific problem.