Problem intuition
- The brute-force version recalculates each window sum from scratch.
- The sliding-window version keeps the current sum and updates it by removing the outgoing number and adding the incoming one.
Solution
The solutions below are ordered from least optimal to most optimal, so you can see the improvement path instead of only the final answer.
Solution 1
Recompute each length-k sum
- For every start index, sum the whole length-k window again.
- This is easy to write, but it repeats most of the same work.
- Time complexity: O(n * k)
- for each starting index, you sum the full window of size k again from scratch.
- Space complexity: O(1)
- only a running sum and the best answer are stored.
Solution 2
Fixed-size sliding window
- Compute the first window sum once.
- Update the sum in O(1) as the window slides forward.
- Time complexity: O(n)
- after the first window, each step only adds one value and removes one value.
- Space complexity: O(1)
- the solution keeps just the current window sum and the best sum seen so far.