LC: 1004

I was trying to solve this leetcode problem and had to refer the solutions after some minutes attempting it. Then came across this super simple ingenious solution. Took a lot of time trying to wrap my head around it. So I thought I’d just share my thought process was like trying to digest this super simple looking yet miraculous code:

Max consecutive ones iii

Link: https://leetcode.com/problems/max-consecutive-ones-iii

Note: you’ll need basic understanding of what this problem is asking for and may a preliminary very high level overview of the code flow

class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        left = 0
        right = 0

        while right<len(nums):
            if nums[right] == 0:
                k -= 1
            if k<0:
                if nums[left] == 0:
                    k += 1
                left +=1
            right += 1
        return right-left

Q. How does left catch up to the next 0 if there are lots of 1 in between without impacting what right is covering?

• Say 1101111001111111 with k=1
• The distance covered by right is all valid max window up until we go below k when we have to shrink window by increasing left. Concern I had was how left would even catch up if we increment both right and left together (left never increments alone).
  • Window expands to a max valid and may expand more but will be invalid size
  • Window can then shrink again but it will never go smaller than the max valid attained
• So the logic here is that there is no need for left to catch up to close the gap ever gain because it’s of no use since the valid max window attained if it grows will only record a bigger window for us. If it shrinks it only shrinks the inflated invalid window size and stops at the valid size.
• This window may move to another spot with invalid 0-1 combinations but that’s also not a concern. If there’s any bigger valid window then things will fix again.

(1)101111(0)01111111: left=0, right=7

• pretty straight foward till this point
• k reduces to k=-1
• since k<0 the window from left will have to shrink
  • left++ => 1
• end loop with right++ => 9

1(1)011110(0)1111111: left=1, right=9

• k reduces further to k=-2
• k<0 so left++ => 2
• end loop with right++ => 10

11(0)111100(1)111111: left=2, right=10

• at this point k=-2 and left=2
• k<0 and also nums[left]==0
  • so k++ => -1
  • left++ => 3
• end loop with right++ => 9

110(1)11100(1)111111: left=3, right=9

• at this point k=-1
• k<0
  • left++ => 4
• end loop with right++ => 10

1101(1)11001(1)11111

left++ => 5 and right++ => 11

11011(1)10011(1)1111

left++ => 6 and right++ => 12

110111(1)00111(1)111

left++ => 7 and right++ => 13

1101111(0)01111(1)11

• k=-1
• k<0
  • k++ => 0
  • left++ => 8 left++ => 8 and right++ => 14

11011110(0)11111(1)1

• k=0
• so no left window shrinking, keep expanding on right until below k-quota again
• right++ => 15

11011110(0)111111(1)

• k=0
• right++ => 16
• right is now exhausted and we exit the loop

Conclusion

Now we calculate the max window size attained: right-left (no +1 since right is an out of boundary index)