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.
This is a much more efficient approach that solves the problem in linear time. The core idea is to maintain a "window" (a subarray) that has at most k zeros. We expand this window by moving its right end and shrink it from the left end whenever the condition (at most k zeros) is violated.
Algorithm
- Initialize two pointers,
left = 0andright = 0, to represent the boundaries of the sliding window. - Initialize
zeroCount = 0to count zeros within the window andmaxLength = 0to store the result. - Iterate through the array with the
rightpointer from0tonums.length - 1to expand the window. - If
nums[right]is a 0, incrementzeroCount. - After expanding, check if the window is valid. If
zeroCount > k, the window contains too many zeros. Shrink the window from the left by incrementing theleftpointer until the window is valid again. - While shrinking, if the element at
nums[left]was a 0, decrementzeroCount. - After each expansion and potential shrinking, the window
[left, right]is valid. Calculate its lengthright - left + 1and updatemaxLength = max(maxLength, right - left + 1). - After the
rightpointer has traversed the entire array, returnmaxLength.
Walkthrough
The problem asks for the longest subarray with at most k zeros. This structure is a perfect fit for the sliding window technique. We use two pointers, left and right, to define the current window [left, right].
We iterate through the array with the right pointer to expand the window. As we expand, we keep track of the number of zeros inside the current window.
If the count of zeros exceeds k, the window is no longer valid. To make it valid again, we must shrink it from the left. We move the left pointer to the right, and if the element at the old left position was a zero, we decrement our zero count. We continue shrinking until the window is valid again (i.e., zeroCount <= k).
At each step, after potentially shrinking, the window [left, right] is the longest valid window ending at right. We update our overall maximum length with the current window's size (right - left + 1). By the time the right pointer has traversed the entire array, we will have found the maximum possible length.
class Solution { public int longestOnes(int[] nums, int k) { int left = 0; int zeroCount = 0; int maxLength = 0; for (int right = 0; right < nums.length; right++) { if (nums[right] == 0) { zeroCount++; } // Shrink the window if it's invalid (too many zeros) while (zeroCount > k) { if (nums[left] == 0) { zeroCount--; } left++; } // The window [left, right] is now valid. // Update the max length. maxLength = Math.max(maxLength, right - left + 1); } return maxLength; }}Complexity
Time
O(N), where N is the number of elements in `nums`. Each pointer, `left` and `right`, traverses the array at most once, resulting in a single pass over the data.
Space
O(1), as we only use a constant amount of extra space for pointers and a counter, regardless of the input size.
Trade-offs
Pros
Highly efficient with a linear time complexity, making it suitable for large datasets.
It is the optimal solution for this problem.
Cons
Can be slightly less intuitive to come up with compared to the brute-force approach, especially for those unfamiliar with the sliding window pattern.
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; }}class Solution {public: int longestOnes(vector<int> &nums, int k) { int l = 0, r = 0; while (r < nums.size()) { if (nums[r++] == 0) --k; if (k < 0 && nums[l++] == 0) ++k; } return r - l; }};class Solution: # max-check every for iteration return res ############## class Solution : def longestOnes ( self , nums : List [ int ], k : int ) -> int : l = r = - 1 while r < len ( nums ) - 1 : r += 1 if nums [ r ] == 0 : k -= 1 if k < 0 : l += 1 if nums [ l ] == 0 : k += 1 return r - l def longestOnes(self, nums: List[int], k: int) -> int: res, zero, left = 0, 0, 0 for right in range(len(nums)): if nums[right] == 0: zero += 1 while zero > k: if nums[left] == 0: zero -= 1 left += 1 res = max(res, right - left + 1) return res class Solution_followup: def findMaxConsecutiveOnes(self, nums: List[int]) -> int: res, left, k = 0, 0, 1 q = deque() for right in range(len(nums)): if nums[right] == 0: q . append(right) if len(q) > k: left = q . popleft() + 1 res = max(res, right - left + 1)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.