Max Consecutive Ones III
- 1 min read
- LC-Medium
- Sliding Window
3 years ago
Solution
- Very similar to Minimum Window Substring, but easier since instead of character frequency we only care about frequencies of zeroes and ones
- I initially forgot to update the answer when a valid sliding window was still being built, I only updated the answer when I moved the sliding window from the left, which is wrong
- You also need to update the answer when it's moving from the right!!
| Time | Space | Explanation |
|---|---|---|
O(n) | O(1) |
def longestOnes(self, nums: List[int], k: int) -> int:
l = num_zeroes_in_window = max_ones = 0
for r in range(len(nums)):
if nums[r] == 0:
num_zeroes_in_window += 1
while l <= r and num_zeroes_in_window > k:
if nums[l] == 0:
num_zeroes_in_window -= 1
l += 1
max_ones = max(max_ones, r - l + 1)
return max_ones