Longest healthy stretch with k re-runs

Scenario

Kestrel Observe runs a health check on every service once a minute. Each check either passes or fails, and the results are stored in order.

Some failures are flaky: the service was fine, but the check timed out. On-call may re-run up to k failed checks, and a re-run check passes.

The reliability report shows each service's longest stretch of consecutive checks that can show all passes after those re-runs. On-call needs its length in minutes, so they know how long the service stayed healthy.

Your task

Write longest_healthy(checks, k).

checks[i] is the result of the check in minute i: 1 for a pass, 0 for a failure.
You may turn at most k failures into passes.
Return the length of the longest stretch of consecutive checks that can then show all passes. That is the longest window with at most k zeros.
If k is 0 and every check failed, no stretch can show all passes: return 0.
k may be larger than the number of failures. Then the whole history counts.

Examples

Example 1 (traced)#

text2 lines

Input:  checks = [1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1], k = 2
Output: 7

right	Joins	Leaves	Failures after	left after	Stretch	Length	Best
0	1	none	0	0	1	1	1
1	0	none	1	0	1, 0	2	2
2	1	none	1	0	1, 0, 1	3	3
3	1	none	1	0	1, 0, 1, 1	4	4
4	0	none	2	0	1, 0, 1, 1, 0	5	5
5	0	1, 0	2	2	1, 1, 0, 0	4	5
6	1	none	2	2	1, 1, 0, 0, 1	5	5
7	1	none	2	2	1, 1, 0, 0, 1, 1	6	6
8	1	none	2	2	1, 1, 0, 0, 1, 1, 1	7	7
9	0	1, 1, 0	2	5	0, 1, 1, 1, 0	5	7
10	1	none	2	5	0, 1, 1, 1, 0, 1	6	7

At minute 5, a third failure joins. Checks leave from the left until one failure has left, so the window holds two again.

Example 2#

text2 lines

Input:  checks = [1, 1, 0, 1, 1, 1, 0], k = 0
Output: 3

With no re-runs, the answer is the longest run of passes: minutes 3 to 5.

Example 3#

text2 lines

Input:  checks = [0, 0, 0, 0], k = 2
Output: 2

Every check failed, so the longest stretch is the k checks that are re-run.

Constraints

1 ≤ checks.length ≤ 10^5 (about 69 days of one check a minute)
checks[i] is 0 or 1
0 ≤ k ≤ 10^5

What does n ≤ 10^5 tell you?

Starting at every minute and extending until a failure cannot be re-run is O(n^2) in the worst case. When k covers every failure, every start scans to the end: about 5 × 10^9 steps. Aim for O(n).

There are only two values, so you do not need a counts map. One number, the failures in the window, tells you whether the window is valid.

Scenario

Kestrel Observe runs a health check on every service once a minute. Each check either passes or fails, and the results are stored in order.

Some failures are flaky: the service was fine, but the check timed out. On-call may re-run up to k failed checks, and a re-run check passes.

Your task

Write longest_healthy(checks, k).

checks[i] is the result of the check in minute i: 1 for a pass, 0 for a failure.
You may turn at most k failures into passes.
Return the length of the longest stretch of consecutive checks that can then show all passes. That is the longest window with at most k zeros.
If k is 0 and every check failed, no stretch can show all passes: return 0.
k may be larger than the number of failures. Then the whole history counts.

Examples

Example 1 (traced)#

text2 lines

Input:  checks = [1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1], k = 2
Output: 7

right	Joins	Leaves	Failures after	left after	Stretch	Length	Best
0	1	none	0	0	1	1	1
1	0	none	1	0	1, 0	2	2
2	1	none	1	0	1, 0, 1	3	3
3	1	none	1	0	1, 0, 1, 1	4	4
4	0	none	2	0	1, 0, 1, 1, 0	5	5
5	0	1, 0	2	2	1, 1, 0, 0	4	5
6	1	none	2	2	1, 1, 0, 0, 1	5	5
7	1	none	2	2	1, 1, 0, 0, 1, 1	6	6
8	1	none	2	2	1, 1, 0, 0, 1, 1, 1	7	7
9	0	1, 1, 0	2	5	0, 1, 1, 1, 0	5	7
10	1	none	2	5	0, 1, 1, 1, 0, 1	6	7

At minute 5, a third failure joins. Checks leave from the left until one failure has left, so the window holds two again.

Example 2#

text2 lines

Input:  checks = [1, 1, 0, 1, 1, 1, 0], k = 0
Output: 3

With no re-runs, the answer is the longest run of passes: minutes 3 to 5.

Example 3#

text2 lines

Input:  checks = [0, 0, 0, 0], k = 2
Output: 2

Every check failed, so the longest stretch is the k checks that are re-run.

Constraints

1 ≤ checks.length ≤ 10^5 (about 69 days of one check a minute)
checks[i] is 0 or 1
0 ≤ k ≤ 10^5

What does n ≤ 10^5 tell you?

Starting at every minute and extending until a failure cannot be re-run is O(n^2) in the worst case. When k covers every failure, every start scans to the end: about 5 × 10^9 steps. Aim for O(n).

There are only two values, so you do not need a counts map. One number, the failures in the window, tells you whether the window is valid.