1·Easy·General·O(n) time, O(k) space
Sliding Window Min Sum
EasyGeneralArraySliding WindowDeque0.0%accepted0submissions
Given an integer array arr and an integer k, consider every contiguous subarray (window) of length k.
For each window, take its minimum element, multiply it by -1, and add it to a running total.
Return the resulting total sum. In other words, the answer is -1 × (sum of the minimums of every window of size k).
Examples
Inputarr = [1, 3, -1, 2, 5], k = 3Output3
Windows: [1,3,-1] min=-1 -> +1; [3,-1,2] min=-1 -> +1; [-1,2,5] min=-1 -> +1. Total = 3.
Inputarr = [4, 2, 12, 3, 8], k = 2Output-10
Windows: [4,2] min=2 -> -2; [2,12] min=2 -> -2; [12,3] min=3 -> -3; [3,8] min=3 -> -3. Total = -10.
Inputarr = [5, 5, 5, 5], k = 2Output-15
Three windows, each min = 5 -> -5. Total = -15.
Constraints
- 1 <= arr.length <= 10^5
- 1 <= k <= arr.length
- -10^9 <= arr[i] <= 10^9
Hints
- Stuck? Reveal a hint — try to solve it yourself first.
minSumWindows.js
13.5
Examples
Hidden Test Cases