Back to Sliding Window
Medium
Max Consecutive Ones III
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
Flip the zeros at indices 5 and 10 to get the longest sequence of 1s.
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
Flip the zeros at indices 4, 5, and 9 to get the longest sequence of 1s.
Constraints
1 <= nums.length <= 10^5nums[i] is either 0 or 1.0 <= k <= nums.length
Approach
Check every possible subarray. For each subarray, count the number of zeros. If the number of zeros is less than or equal to `k`, the subarray is valid. Keep track of the maximum length of a valid subarray.
Complexity Analysis
Time Complexity
O(n^2)
Space Complexity
O(1)
This approach is too slow for large inputs and will result in TLE.
Solution.java
class Solution { public int longestOnes(int[] nums, int k) { int maxLength = 0; for (int i = 0; i < nums.length; i++) { int zeroCount = 0; for (int j = i; j < nums.length; j++) { if (nums[j] == 0) { zeroCount++; } if (zeroCount <= k) { maxLength = Math.max(maxLength, j - i + 1); } else { break; } } } return maxLength; }}