Leetcode - Max Consecutive Ones III (Python)

June 2021 Leetcode Challenge
Leetcode - Max Consecutive Ones III #1004
Difficulty: Medium

[davidespinosa]

Nice solution ! It's actually unique on YouTube.
It also solves Leetcode 1493, if we set k = 1 and return r - l (instead of r - l + 1).
Here's a longer explanation. By convention, I write "we", but all credit goes to Tim.

We consider intervals [l, r], so their length is r - l + 1.
Let k0 be the initial value of k.
The *value* of an interval is k0 minus the number of zeros in the interval.
An interval is *admissible* if its value is greater than or equal to zero.
We want to find the length of a longest admissible interval.

Most solutions track the longest admissible interval ending at r.
Those solutions keep a max and use a while loop to update l.
But that's NOT what we do here. In fact, the initial solution using max is a red herring.

Instead, we keep the length of [l, r] equal to the length of the longest admissible interval seen so far. And we keep k equal to the value of [l, r]. For each new r, we update k (line 5). If the interval is admissible (k >= 0), then we don't increment l, so that [l, r] is now the longest admissible interval. If the interval is not admissible (k < 0), then we increment l (to keep the length unchanged) and update the value accordingly (line 7).

[meayliizzsuju]

best explanation I have seen so far than k you!

[kshitijzutshi]

Perhaps need to see two more YT videos to understand this video! 😂

[hangchen]

The best sentence I hear recently is "Welcome to X's leetcode challenge!"