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
withk=1
- The distance covered by
right
is all valid max window up until we go below k when we have to shrink window by increasingleft
. Concern I had was howleft
would even catch up if we increment bothright
andleft
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 tok=-1
- since
k<0
the window from left will have to shrinkleft++ => 1
- end loop with
right++ => 9
1(1)011110(0)1111111: left=1, right=9
k
reduces further tok=-2
k<0
soleft++ => 2
- end loop with
right++ => 10
11(0)111100(1)111111: left=2, right=10
- at this point
k=-2
andleft=2
k<0
and alsonums[left]==0
- so
k++ => -1
left++ => 3
- so
- 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
andright++ => 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)