Problem 338125 · easy · Level 03 Linear Management & Searching

Skip One Bad Day

sliding window · variable-size window · binary arrays

days is a list of 0s and 1s where 1 means you completed your workout. You are allowed to strike exactly one day from the record (it can be a 1 or a 0). Return the length of the longest run of consecutive 1s in the record after the strike.

Examples

Input:  days = [1, 1, 0, 1]
Output: 3
Explanation: strike the 0 and the remaining record is [1, 1, 1].

Input:  days = [0, 1, 1, 1, 0, 1, 1, 0, 1]
Output: 5

Input:  days = [1, 1, 1]
Output: 2
Explanation: you must strike one day, so only two 1s remain.

Constraints

  • 1 <= len(days) <= 10**5
  • days[i] is 0 or 1
  • Target complexity: O(n) time; trying every strike position separately is too slow for the largest tests.

Goals

  • Grow a window while it contains at most one zero
  • Remember that exactly one element must be removed, even from an all-ones list
Starting Python…