Max Consecutive Ones III Python Solution

Tested Python solution for LeetCode 1004 with 12 pytest cases. Generate a practice environment with lcpy.

LeetCode 1004, Medium. Topics: Array, Binary Search, Sliding Window, Prefix Sum. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 12 parametrized pytest cases, and a playground notebook:

lcpy gen -n 1004   # by problem number
lcpy gen -s max_consecutive_ones_iii   # by problem name

​

Problem

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.

​

Examples

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.

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

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

class Solution:
    # Time: O(n)
    # Space: O(1)
    def longest_ones(self, nums: list[int], k: int) -> int:
        left = 0
        zeros = 0
        best = 0
        for right, num in enumerate(nums):
            if num == 0:
                zeros += 1
            while zeros > k:
                if nums[left] == 0:
                    zeros -= 1
                left += 1
            best = max(best, right - left + 1)
        return best

​

Complexity

Time	Space
O(n)	O(1)

​

Tags

NeetCode All.