Watch 10 video solutions for Max Consecutive Ones III, a medium level problem involving Array, Binary Search, Sliding Window. This walkthrough by take U forward has 326,281 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 105nums[i] is either 0 or 1.0 <= k <= nums.lengthProblem Overview: You get a binary array nums and an integer k. You can flip at most k zeros to ones. The goal is to return the length of the longest contiguous subarray containing only ones after performing those flips.
Approach 1: Brute Force Enumeration (O(n^2) time, O(1) space)
Check every possible subarray. For each starting index, extend the subarray to the right while counting how many zeros appear. If the zero count exceeds k, stop expanding that window. Track the maximum valid length seen. This approach works because the array is small enough to brute force in theory, but it performs up to n expansions for each starting index, leading to quadratic time. It helps you reason about the constraint: the window is valid as long as the number of zeros is ≤ k.
Approach 2: Prefix Sum + Binary Search (O(n log n) time, O(n) space)
Build a prefix sum array that stores how many zeros appear up to each index. For each right boundary, compute how many zeros exist in the window using prefix subtraction. If the count exceeds k, binary search the farthest left boundary that keeps the zero count ≤ k. This method converts the constraint into a range query problem. It’s useful when practicing prefix sum techniques combined with binary search, but the extra log factor and additional memory make it less optimal than the linear solution.
Approach 3: Sliding Window (O(n) time, O(1) space)
Maintain a window with two pointers left and right. As you expand right, track how many zeros exist in the current window. If the zero count exceeds k, move left forward until the window becomes valid again. At every step, update the maximum window length. The key insight: once a window has more than k zeros, the only fix is shrinking it from the left. Each element enters and leaves the window at most once, so the algorithm runs in linear time. This pattern is common in problems involving longest valid subarrays and is a core technique in sliding window and array optimization problems.
Recommended for interviews: The sliding window solution is the expected answer. Interviewers want to see that you recognize the "at most k constraint" and translate it into a dynamic window that expands and shrinks. Mentioning the brute force approach shows baseline reasoning, but implementing the O(n) sliding window demonstrates strong algorithmic intuition.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n^2) | O(1) | Understanding the constraint and validating smaller inputs |
| Prefix Sum + Binary Search | O(n log n) | O(n) | When practicing prefix sum queries and binary search on ranges |
| Sliding Window | O(n) | O(1) | Optimal approach for large arrays and typical interview solution |