Max Consecutive Ones I and III: From a Counter to a Sliding Window
Max Consecutive Ones (LeetCode 485) and Max Consecutive Ones III (LeetCode 1004) are a natural pair. The first needs a running counter. The second, where you may flip up to k zeros, is the cleanest introduction to the variable-size sliding window.
Part I: a running counter
def find_max_consecutive_ones(nums):
best = run = 0
for x in nums:
run = run + 1 if x == 1 else 0
best = max(best, run)
return best
O(n) time, O(1) space. Nothing more is needed.
Part III: allow up to k flips
Rephrase the problem: find the longest window that contains at most k zeros. Grow the window on the right. When it holds too many zeros, shrink it from the left until it is valid again.
def longest_ones(nums, k):
left = zeros = best = 0
for right, x in enumerate(nums):
if x == 0:
zeros += 1
while zeros > k:
if nums[left] == 0:
zeros -= 1
left += 1
best = max(best, right - left + 1)
return best
Each index enters and leaves the window at most once, so this is O(n) even with the inner loop.
The non-shrinking trick
You can replace while with if. The window then never shrinks, it only slides, and its size stays at the best answer seen so far. The final answer is len(nums) - left. It is a neat optimisation to mention, but write the while version first because it is easier to justify.
Related questions
Longest Substring Without Repeating Characters, Fruit Into Baskets, and Longest Repeating Character Replacement all use the same "at most k bad items in the window" template.
Disclosure: I work on Linkjob AI. It is a real-time AI interview assistant for live interviews for rounds like this.
Further reading: Linkjob AI resource directory
评论
发表评论