Max Consecutive Ones III
MedPrompt
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 either0or1.0 <= k <= nums.length
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves checking every possible contiguous subarray within the given array. For each subarray, we count the number of zeros. If the count is within the allowed limit k, we consider its length as a potential answer and update our maximum length found so far.
Algorithm
- Initialize a variable
maxLengthto 0 to store the length of the longest valid subarray found. - Use a nested loop structure. The outer loop with index
iwill determine the starting point of a subarray. - The inner loop with index
jwill determine the ending point of the subarray, starting fromi. - For each subarray defined by
[i, j], maintain a count of zeros,zeroCount. - If
nums[j]is 0, incrementzeroCount. - If
zeroCountis less than or equal tok, the current subarray is valid. Calculate its lengthj - i + 1and updatemaxLength = max(maxLength, j - i + 1). - If
zeroCountexceedsk, the subarray is invalid. Since any further extension of this subarray (by increasingj) will also be invalid, we can break the inner loop as an optimization. - After checking all possible starting points
i, returnmaxLength.
Walkthrough
We use two nested loops to define the start and end of each subarray. The outer loop iterates through all possible start indices i, and the inner loop iterates through all possible end indices j starting from i.
For each subarray nums[i...j], we maintain a count of zeros. If the number of zeros in the current subarray is less than or equal to k, it's a valid subarray. We calculate its length (j - i + 1) and update the maximum length if this subarray is longer than any valid one found previously.
If the number of zeros exceeds k, we can stop extending the current subarray (by breaking the inner loop) because any longer subarray starting at i will also have more than k zeros. This process is repeated for all possible starting positions i.
class Solution { public int longestOnes(int[] nums, int k) { int maxLength = 0; int n = nums.length; for (int i = 0; i < n; i++) { int zeroCount = 0; for (int j = i; j < n; j++) { if (nums[j] == 0) { zeroCount++; } if (zeroCount <= k) { maxLength = Math.max(maxLength, j - i + 1); } else { // Optimization: if zero count exceeds k, no need to extend this subarray break; } } } return maxLength; }}Complexity
Time
O(N^2), where N is the number of elements in `nums`. The two nested loops lead to a quadratic runtime, as in the worst case, we might check all N*(N+1)/2 subarrays.
Space
O(1), as we only use a few variables to store counts and indices, requiring constant extra space.
Trade-offs
Pros
Simple to understand and implement.
Directly translates the problem statement into a straightforward solution.
Cons
Highly inefficient for large input sizes due to its quadratic time complexity.
Will likely result in a 'Time Limit Exceeded' (TLE) error on competitive programming platforms for the given constraints.
Solutions
Solution
class Solution {public int longestOnes(int[] nums, int k) { int l = 0, r = 0; while (r < nums.length) { if (nums[r++] == 0) { --k; } if (k < 0 && nums[l++] == 0) { ++k; } } return r - l; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.