#1004

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Max Consecutive Ones III

Find the longest consecutive ones in a binary array by optimally flipping at most k zeros using sliding window techniques.

array binary search sliding window prefix sum

Problem Statement

Given a binary array nums and an integer k, determine the maximum length of a contiguous subarray of 1s that can be obtained by flipping at most k zeros to 1s. Each flip should be used to extend an existing block of consecutive 1s for maximum effect.

Return the length of the longest subarray that satisfies this condition. Constraints ensure nums contains only 0s and 1s, and the length of nums ranges from 1 to 10^5, with 0 <= k <= nums.length.

Examples

Example 1

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

Output: 6

[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

[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 <= 105
nums[i] is either 0 or 1.
0 <= k <= nums.length

Solution Approach

Sliding Window with Zero Count

Maintain a window [left, right] over nums and count the number of zeros inside. Expand the right boundary while the zero count <= k. If zeros exceed k, move left forward until the window is valid again. Track the maximum window size throughout.

Binary Search over Window Size

Consider using binary search to test possible window lengths. For each candidate length, check if a window exists with at most k zeros. Adjust search boundaries based on feasibility. This leverages the primary pattern of searching over valid answer space efficiently.

Prefix Sum Optimization

Precompute a prefix sum array of zeros to quickly query the number of zeros in any subarray. This allows constant-time validation for any candidate window, reducing redundant counting when sliding or binary searching.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) for sliding window, O(n log n) if using binary search over window size, and space complexity is O(1) for sliding window or O(n) for prefix sum. Each method aligns with the maximum-consecutive-ones pattern and handles large input efficiently.

What Interviewers Usually Probe

Focus on maximizing 1s using minimal zero flips.
Consider the sliding window as the main pattern for handling consecutive sequences.
Be aware of off-by-one errors when adjusting the window boundaries.

Common Pitfalls or Variants

Common pitfalls

Flipping zeros that do not extend a 1s sequence, wasting k flips.
Failing to shrink the window correctly when zero count exceeds k.
Incorrectly updating maximum length after window adjustment.

Follow-up variants

Return the subarray itself instead of its length.
Allow flipping zeros with different weights or costs.
Find maximum consecutive ones for multiple queries of k in the same array.

FAQ

What is the optimal approach for Max Consecutive Ones III?

Use a sliding window to count zeros and expand or shrink the window based on k flips allowed, ensuring the longest 1s sequence.

Can binary search be applied to Max Consecutive Ones III?

Yes, binary search over the possible window lengths combined with prefix sums can validate feasibility efficiently.

Why do we track zeros inside the window?

Tracking zeros ensures we do not exceed k flips, which is the key constraint for forming the maximum consecutive ones subarray.

What mistakes should be avoided when implementing this pattern?

Avoid flipping zeros that don't extend 1s sequences, mishandling window boundaries, or forgetting to update the max length after adjustment.

Does prefix sum improve performance in this problem?

Yes, prefix sums allow constant-time zero counts for any subarray, optimizing validation during sliding or binary search methods.

terminal

Solution

Solution 1: Sliding Window

We can iterate through the array, using a variable $\textit{cnt}$ to record the current number of 0s in the window. When $\textit{cnt} > k$, we move the left boundary of the window to the right by one position.

1

2

3

4

5

6

7

8

9

class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        l = cnt = 0
        for x in nums:
            cnt += x ^ 1
            if cnt > k:
                cnt -= nums[l] ^ 1
                l += 1
        return len(nums) - l

Continue Practicing

#862 shortest subarray with sum at least k #713 subarray product less than k #1658 minimum operations to reduce x to zero