hey, i understand this solution because it just works here and it feels like since the way the variables are set to come up to the solution but i don’t know how to think like this and especially how can i think of this zero_count to set a logic like this
question : https://leetcode.com/problems/max-consecutive-ones-iii/description/
def max_consecutive_one_with_flip(nums,k):
left = 0
zero_count = 0
for right in range(len(nums)):
if nums[right] == 0:
zero_count += 1
if zero_count > k:
if nums[left] == 0:
zero_count -= 1
left += 1
return len(nums) - lefthey, i understand this solution because it just works here and it feels like since the way the variables are set to come up to the solution but i don't know how to think like this and especially how can i think of this zero_count to set a logic like this :
def max_consecutive_one_with_flip(nums,k):
left = 0
zero_count = 0
for right in range(len(nums)):
if nums[right] == 0:
zero_count += 1
if zero_count > k:
if nums[left] == 0:
zero_count -= 1
left += 1
return len(nums) - left
I think that the last line has too much indentation.
def max_consecutive_one_with_flip(nums,k):
left = 0
zero_count = 0
for right in range(len(nums)):
if nums[right] == 0:
zero_count += 1
if zero_count > k:
if nums[left] == 0:
zero_count -= 1
left += 1
return len(nums) - left # Indented at same level as the FOR
Maybe understand first this version
def max_consecutive_one_with_flip(nums,k):
left = 0
zero_count = 0
max_len = 0
for right in range(len(nums)):
if nums[right] == 0:
zero_count += 1
while zero_count > k:
if nums[left] == 0:
zero_count -= 1
left += 1
max_len = max(max_len, right - left + 1)
return max_len
Motivation:
-
Using sliding window. This is useful in many problems for computing something in an array. So, we can try it for no other reason than to see if it helps.
-
left and right indicate the position of the window. In sliding window the window could need to move in many ways. Who knows in this problem, but let’s try the most naive way, right moving from left to right along the array and nothing else. This choice forces pretty much everything else. The position right is testing all possible end locations of a solution.
-
left, to test all cases, would need (for every value of right) to start at 0 and test all positions until right. That leads to a program that solves the problem, but it does too many tests.
-
The observation that if left is at a position for which there are too many zeros inside the window, then no smaller value works either for the same right tells that left doesn’t need to decrease. This gives a program like the second version. Note how it moves right along the array, the left only increases when needed (more than k zeros inside the window) and zero_count is counting the number of zeros inside the window. The variable max_len is keeping track of the maximum length of a valid window ever found.
-
The first version follows from one more observation, that if once a solution is found we don’t shrink the window to less than that length (even if it has too many zeros inside), then the current length of the window already contains the information of max_len. This is why the first version replaced the while with an if. So, when moving right to the right causes more than k zeros to be inside the window, we only increase left by one, thus keeping the size of the window as large as it was before (when it was valid). Note that the window always begins being valid, with length zero. So, its length being the length of some valid position and never shrinking is an invariant that proves that the algorithm solves the problem.
This variant of sliding window, in which the window doesn’t shrink is also common to multiple problems. There might be other places to read about it, but this is the first link that I found with more examples.