1004.Max_Consecutive_Ones_III(Medium).md

1004. Max Consecutive Ones III (Medium)

Date and Time: Oct 8, 2024, 16:24 (EST)

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

Question:

Given a binary array nums and an integer k, return the maximum number of consecutive 1's in the array if you can flip at most k 0's.

Example 1:

Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2

Output: 6

Explanation: [1,1,1,0,0,1,1,1,1,1,1]
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.

Example 2:

Input: nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], k = 3

Output: 10

Explanation: [0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.

Constraints:

• 1 <= nums.length <= 10^5

• nums[i] is either 0 or 1.

• 0 <= k <= nums.length

Walk-through:

Use l, r pointer to keep track of a window's size. When nums[r] == 0, we decrement k until k is negative, then we can start shrinking the window while we are still expanding this window (we just keep the same current maxmimum window size by moving the window to the right by 1).

When nums[l] == 0, we can increment k += 1, until k >= 0 we can start expanding the window again.

Finally, since we will keep the current maximum window's length, so until the end of the list, we can just return r - l + 1, which is the maximum size of the window we have.

Python Solution:

class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        # When k is negative, update l += 1, if nums[l] == 0, k += 1, same as moving the window to the right by 1
        # return r - l + 1 in the end, because we will always keep the same size of the max window

        # TC: O(n), SC: O(1)
        l = 0
        for r in range(len(nums)):
            if nums[r] == 0:
                k -= 1
            if k < 0:
                if nums[l] == 0:
                    k += 1
                l += 1
        return r - l + 1

Time Complexity: $O(n)$
Space Complexity: $O(1)$