Coldest Stretch

Difficulty: 1200 3000 ms 128 MB

sliding-window

Daily temperatures are given. Find the starting day (1-based) of the K-day stretch with the smallest total temperature; on ties pick the earliest start.

Input: the first line has N and K; the second line has N integers (temperatures).

Output: the 1-based starting index of the minimum-sum window (earliest on ties).

Constraints:

• 1 ≤ K ≤ N ≤ 10⁵
• −10⁹ ≤ a_i ≤ 10⁹

Sample Tests

6 2
5 1 1 4 0 3

2

3 3
1 2 3

1

Read the Editorial