Wraparound Window Totals
EasySliding Window
Problem
Seats around a round table hold nums[i] guests each, and seat n - 1 is next to seat 0. For a seating plan you need, for every seat i, the total number of guests in the k seats starting at i and going clockwise (wrapping past the end).
Return an array result of length n where result[i] = nums[i] + nums[(i + 1) % n] + ... + nums[(i + k - 1) % n].
Example 1
- Input:
- nums = [1, 2, 3, 4], k = 2
- Output:
- [3, 5, 7, 5]
The last window wraps: nums[3] + nums[0] = 4 + 1 = 5.
Example 2
- Input:
- nums = [5, -1, 2], k = 3
- Output:
- [6, 6, 6]
With k = n every window is the whole table.
Constraints
- 1 ≤ k ≤ nums.length ≤ 10^5
- -10^4 ≤ nums[i] ≤ 10^4
Hint
Show the first hint
Without wrapping this is the classic running window sum. How do you deal with the end of the array?
Walkthrough
How to approach it
01Clarify before coding
- Does every seat get a window, even near the end? Yes, n results, each wrapping as needed.
- Can k equal n? Yes; every result is the total.
- Can values be negative? Yes.
02Brute force
For each i, add the k values nums[(i + d) % n] for d = 0..k-1.
Cost: O(n·k) time; with n = 10^5 and k = n that is 10^10 additions.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.