Max Consecutive Ones III
Problem Description
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 0s.
Binary Array: An array with only 0s or 1s.
Explanation
You're given an array of binary values (0 or 1).
You can flip some of the 0s in the array to 1s. But, you can only flip at most k 0s.
The task is to find the maximum number of consecutive 1s you can get after flipping at most k 0s.
What is a Subarray ?
It's a sequence of elements taken from the original array that are next to each other, without skipping any elements.
For the array [1, 2, 3, 4], here are all possible subarrays:
Single element subarrays:
[1], [2], [3], [4]
Subarrays of length 2:
[1, 2], [2, 3], [3, 4]
Subarrays of length 3:
[1, 2, 3], [2, 3, 4]
Subarray of length 4:
[1, 2, 3, 4] (the entire array)
Note:- { 1, 3 ,4 } or { 2,4 } are not the subarrays of arr[ ] = { 1 , 2 , 3 , 4 }
Example
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.
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 <= 10^5
- nums[i] is either 0 or 1.
- 0 <= k <= nums.length
"Although this problem might seem straightforward, there are different ways to solve it by using two pointers/sliding window, etc. Each approach has its own benefits and challenges in terms of how fast it works and how much memory it uses."
Brute Force Approach
Intuition
The question asks us to find the total number of consecutive 1s after we perform at most k flips.
Is it asking to find the longest subarray of 1s after at most k flips are performed?Yes, since we know what a subarray is.
How to generate the subarrays of an array ?
Pick a starting point (i): This can be any index from 0 to n-1 (where n is the length of the array).
Pick an ending point (j): This can be any index from the current starting point i to n-1.
Extract the subarray: Once you have both the starting (i) and ending (j) points, you can extract the subarray by slicing from index i to j (inclusive).
For arr = [1, 2, 3]:
Start at i = 0:
Subarray [1] (from i = 0 to j = 0)
Subarray [1, 2] (from i = 0 to j = 1)
Subarray [1, 2, 3] (from i = 0 to j = 2)
Start at i = 1:
Subarray [2] (from i = 1 to j = 1)
Subarray [2, 3] (from i = 1 to j = 2)
Start at i = 2:
Subarray [3] (from i = 2 to j = 2)
After we generate the
Moving further with the brute force approach:
We will Try every possible subarray from each possible starting point and ending point of subarrays within the array.
For each subarray, we count how many zeros it contains.
If the subarray has at most k zeros, calculate the length of the subarray and compare it to the maximum length found so far.
If the current subarray has more consecutive 1s (including the flips) than the previous maximum we will update the result.
Let’s visualize the brute force with an example
For example,
nums[ ] = [1, 0, 0, 1, 1]
k = 1 i.e we can flip at most 1 number of 0s to 1s.
We come to know that the highlighted subarray i.e. [ 0 , 1 , 1 ] is the only subarray which has 1 zero, if is flipped to 1 gives the longest consecutive 1s.
Approach
We declare two for loops:
- Outer Loop (i from 0 to nums.length - 1):
- This loop sets the starting point of the subarray.
- Inner Loop (j from i to nums.length - 1):
- This loop sets the ending point of the subarray.
- We count the number of 0s in the subarray [i, j].
- For each subarray, we increase the count of 0s if we encounter a 0.
- If the count of 0s is less than or equal to k, the subarray is valid, and we calculate its length (j - i + 1).
- Update the maxLength if the current subarray is longer than the previous longest.
- Break the loop if the number of 0s exceeds k because any further extensions of the subarray will also be invalid.
Dry-Run
Nums[ ] = {0, 1, 1, 0, 0, 1}, k = 2
Answer= 5
Explanation:-[ 0,1, 1, 1, 1, 1]
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.
Initialize Variables:
Initialize:
max_length = 0
n = 6
Iterate through subarrays:
Subarray from index 0 to 0:
[0]
Count of 0s: 1 (valid, ≤ 2)
Length = 1
Update max_length = 1
Subarray from index 0 to 1:
[0, 1]
Count of 0s: 1 (valid, ≤ 2)
Length = 2
Update max_length = 2
Subarray from index 0 to 2:
[0, 1, 1]
Count of 0s: 1 (valid, ≤ 2)
Length = 3
Update max_length = 3
Subarray from index 0 to 3:
[0, 1, 1, 0]
Count of 0s: 2 (valid, ≤ 2)
Length = 4
Update max_length = 4
Subarray from index 0 to 4:
[0, 1, 1, 0, 0]
Count of 0s: 3 (invalid, > 2)
No update to max_length.
Subarray from index 0 to 5:
[0, 1, 1, 0, 0, 1]
Count of 0s: 3 (invalid, > 2)
No update to max_length.
Subarray from index 1 to 1:
[1]
Count of 0s: 0 (valid, ≤ 2)
Length = 1
No update to max_length.
Subarray from index 1 to 2:
[1, 1]
Count of 0s: 0 (valid, ≤ 2)
Length = 2
No update to max_length.
Subarray from index 1 to 3:
[1, 1, 0]
Count of 0s: 1 (valid, ≤ 2)
Length = 3
No update to max_length.
Subarray from index 1 to 4:
[1, 1, 0, 0]
Count of 0s: 2 (valid, ≤ 2)
Length = 4
No update to max_length.
Subarray from index 1 to 5:
[1, 1, 0, 0, 1]
Count of 0s: 2 (valid, ≤ 2)
Length = 5
Update max_length = 5.
Subarray from index 2 to 2:
[1]
Count of 0s: 0 (valid, ≤ 2)
Length = 1
No update to max_length.
Subarray from index 2 to 3:
[1, 0]
Count of 0s: 1 (valid, ≤ 2)
Length = 2
No update to max_length.
Subarray from index 2 to 4:
[1, 0, 0]
Count of 0s: 2 (valid, ≤ 2)
Length = 3
No update to max_length.
Subarray from index 2 to 5:
[1, 0, 0, 1]
Count of 0s: 2 (valid, ≤ 2)
Length = 4
No update to max_length.
Subarray from index 3 to 3:
[0]
Count of 0s: 1 (valid, ≤ 2)
Length = 1
No update to max_length.
Subarray from index 3 to 4:
[0, 0]
Count of 0s: 2 (valid, ≤ 2)
Length = 2
No update to max_length.
Subarray from index 3 to 5:
[0, 0, 1]
Count of 0s: 2 (valid, ≤ 2)
Length = 3
No update to max_length.
Subarray from index 4 to 4:
[0]
Count of 0s: 1 (valid, ≤ 2)
Length = 1
No update to max_length.
Subarray from index 4 to 5:
[0, 1]
Count of 0s: 1 (valid, ≤ 2)
Length = 2
No update to max_length.
Subarray from index 5 to 5:
[1]
Count of 0s: 0 (valid, ≤ 2)
Length = 1
No update to max_length.
Result: Max length is 5.Example
Nums[ ] = {0, 1, 1, 0, 0, 1}, k = 2
Answer= 5
Explanation:-[ 0,1, 1, 1, 1, 1]
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.
Brute Force Codes in all Languages
1. C++ Try on Compiler
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum number of consecutive 1s after flipping at most k zeros
int findMaxConsecutiveOnes(vector<int>& nums, int k) {
// Variable to store the maximum length of valid subarray
int maxLength = 0;
// Get the length of the array
int n = nums.size();
// Loop over all possible starting points for subarrays
for (int i = 0; i < n; i++) {
// Initialize a count for the number of zeros in the current subarray
int zeroCount = 0;
// Loop over all possible ending points for subarrays starting at i
for (int j = i; j < n; j++) {
// If we encounter a zero, increment the zero count
if (nums[j] == 0) {
zeroCount++;
}
// If the zero count is within the allowed limit (k), check the subarray length
if (zeroCount <= k) {
// Calculate the length of the current subarray
int currentLength = j - i + 1;
// Update the maximum length if the current subarray is longer
maxLength = max(maxLength, currentLength);
} else {
// If zero count exceeds k, break out of the inner loop
break;
}
}
}
// Return the maximum length of the subarray found
return maxLength;
}
2. Java Try on Compiler
import java.util.*;
public class MaxConsecutiveOnes {
// Function to find the maximum number of consecutive 1s after flipping at most k zeros
public static int findMaxConsecutiveOnes(int[] nums, int k) {
// Variable to store the maximum length of valid subarray
int maxLength = 0;
// Get the length of the array
int n = nums.length;
// Loop over all possible starting points for subarrays
for (int i = 0; i < n; i++) {
// Initialize a count for the number of zeros in the current subarray
int zeroCount = 0;
// Loop over all possible ending points for subarrays starting at i
for (int j = i; j < n; j++) {
// If we encounter a zero, increment the zero count
if (nums[j] == 0) {
zeroCount++;
}
// If the zero count is within the allowed limit (k), check the subarray length
if (zeroCount <= k) {
// Calculate the length of the current subarray
int currentLength = j - i + 1;
// Update the maximum length if the current subarray is longer
maxLength = Math.max(maxLength, currentLength);
} else {
// If zero count exceeds k, break out of the inner loop
break;
}
}
}
// Return the maximum length of the subarray found
return maxLength;
}
}
3. Python Try on Compiler
def find_max_consecutive_ones(nums, k):
# Variable to store the maximum length of valid subarray
max_length = 0
n = len(nums)
# Loop over all possible starting points for subarrays
for i in range(n):
# Initialize a count for the number of zeros in the current subarray
zero_count = 0
# Loop over all possible ending points for subarrays starting at i
for j in range(i, n):
# If we encounter a zero, increment the zero count
if nums[j] == 0:
zero_count += 1
# If the zero count is within the allowed limit (k), check the subarray length
if zero_count <= k:
# Calculate the length of the current subarray
current_length = j - i + 1
# Update the maximum length if the current subarray is longer
max_length = max(max_length, current_length)
else:
# If zero count exceeds k, break out of the inner loop
break
# Return the maximum length of the subarray found
return max_length
4. JavaScript Try on Compiler
function findMaxConsecutiveOnes(nums, k) {
// Variable to store the maximum length of valid subarray
let maxLength = 0;
let n = nums.length;
// Loop over all possible starting points for subarrays
for (let i = 0; i < n; i++) {
// Initialize a count for the number of zeros in the current subarray
let zeroCount = 0;
// Loop over all possible ending points for subarrays starting at i
for (let j = i; j < n; j++) {
// If we encounter a zero, increment the zero count
if (nums[j] === 0) {
zeroCount++;
}
// If the zero count is within the allowed limit (k), check the subarray length
if (zeroCount <= k) {
// Calculate the length of the current subarray
let currentLength = j - i + 1;
// Update the maximum length if the current subarray is longer
maxLength = Math.max(maxLength, currentLength);
} else {
// If zero count exceeds k, break out of the inner loop
break;
}
}
}
// Return the maximum length of the subarray found
return maxLength;
}
Time Complexity: O(n^2)
Outer Loop:
The first loop runs from the starting index i = 0 to n-1 (where n is the size of the array). This loop runs n times.
Inner Loop:
For each starting point i, the inner loop runs from j = i to n-1.
In the worst case (when i = 0), the inner loop runs n times, then for i = 1, it runs n-1 times, and so on.
This creates a triangular sum of iterations:
n + (n-1) + (n-2) + ... + 1 = n * (n + 1) / 2
This evaluates to O(n²).
Counting Zeros:
Inside the inner loop, for every subarray, we check each element and count zeros. This takes O(1) time for each element, as we're just checking and updating the zeroCount.
Hence, this step does not add extra complexity.
The overall time complexity is dominated by the nested loops, which makes it O(n²) where n is the length of the array.
Space Complexity: O(n)
Auxiliary Space Complexity
The only extra space used is a few integer variables like maxLength, zeroCount, and loop variables (i, j), which all use O(1) space.
There is no recursion or significant data structure allocation during the algorithm.
Therefore, the auxiliary space complexity is O(1).
Total Space Complexity
The input array nums is provided as part of the problem, so it counts towards the total space used.
The input array nums takes O(n) space.
Adding the auxiliary space, the total space complexity is O(n) due to the array.
This is extremely slow and not feasible within typical time limits (usually 1-2 seconds). Most programming environments allow around 10^8 operations per second, so 10^15 operations would take about 10 million seconds (over 115 days!), which is far too long.
The interviewer won’t be happy with your solution. We have to optimize the Time Complexity to move further in the interview!
Optimal Approach
Intuition
The first key observation is that , since the Brute Force Approach gives us a time complexity of O(n^2). So, we need to optimize it to either O(n) or O(logn).
Since, the the string size can 10^5, O(n^2) will also result in Time Limit Exceeded.
Can we assume that the optimal solution will be a O(n) solution as we have to traverse the whole string to get the answer.
Are we wasting a lot of time trying to generate subarrays from a given starting point till the end of the array ?
Yes, we are.
Can’t we directly determine the subarray size that will have k or less than k zeros?
Let’s take an example and understand if
nums[ ] = {0, 1, 1, 0, 0, 1}
k = 2
First subarray= [ 0 ], k=2-1 =1
The second subarray = [ 0, 1 ], k remains the same i.e k=1
The third subarray = [ 0,1,1 ], k remains same i.e. k=1
The fourth subarray = [ 0,1,1,0 ] k=1-1=0
The fifth subarray = [ 0,1,1,0,0 ] k= 0-1=-1
Hey !! Wait !! , Was constructing the 1st,2nd 3rd and 5th subarray useful ?,
Can’t we just extract the subarray which has k 0s without much iterations ?
Let’s observe
Can we visualize a “frame” , where elements comes inside and go out ??
Possibly a yes.
How ??
In nums [ ] = {0, 1, 1, 0, 0, 1}
The first subarray with 2 0s is the highlighted part of {0, 1, 1, 0, 0, 1}
The max no of 1s after the k=2 flips will be 4.
What we gonna do is , just remove the left most integer i.e. 0 and add the next integer to the rightmost of 0 i.e. 0
The second subarray with 2 0s is the highlighted part of {0, 1, 1, 0, 0, 1}
Now, the max no of 1s after the flip is 5.
Yes , what we did was we maintained a dynamic “frame” which was designed in such a way that if the the value of k reaches zero, the frame will shrink from left, else it will expand.
When the frame shrinks, the leftmost character is excluded and during expansion of the frame, the integer next to the rightmost integer enters the frame.
This way we can save time generating every subarray and we can directly reach to the needed subarray and calculate it’s length.
How to calculate the subarray’s length?
The length will be nothing but the difference between the right boundary and the left boundary of the frame added by 1.
We are adding 1 , since we are following 0 based indexing.
Therefore, the length of each subarray is (right-left+1).
Finally, we got the approach.
We will construct the frame which has two ends, the left end and the right end. We will expand the frame i.e moving the right end until the value of k becomes 0.
Once, the value of k is 0, we will shrink the frame and calculate the length of that subarray and compare it with the maximum ones.
Lets call this dynamic frame as a window which slides and the algorithm we figured out is sliding window algorithm.
Lets Visualize with an Example in the given Video
Dry-Run
Example
Nums[ ] = {0, 1, 1, 0, 0, 1}, k = 2
Answer= 5
Explanation:-[ 0,1, 1, 1, 1, 1]
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.
Initial Setup:
nums = {0, 1, 1, 0, 0, 1}
k = 2
left = 0, right = 0
zeroCount = 0, maxLength = 0
Iteration 1 (right = 0):
Current Element: nums[0] = 0
Increment zeroCount because it's a zero: zeroCount = 1
Since zeroCount (1) <= k (2), we do not shrink the window.
Calculate the current length: length = right - left + 1 = 0 - 0 + 1 = 1
Update maxLength: maxLength = max(0, 1) = 1
State:
left = 0, right = 0, zeroCount = 1, maxLength = 1
Subarray: [0]
Iteration 2 (right = 1):
Current Element: nums[1] = 1
zeroCount remains 1 (no change).
Since zeroCount (1) <= k (2), we do not shrink the window.
Calculate the current length: length = right - left + 1 = 1 - 0 + 1 = 2
Update maxLength: maxLength = max(1, 2) = 2
State:
left = 0, right = 1, zeroCount = 1, maxLength = 2
Subarray: [0, 1]
Iteration 3 (right = 2):
Current Element: nums[2] = 1
zeroCount remains 1 (no change).
Since zeroCount (1) <= k (2), we do not shrink the window.
Calculate the current length: length = right - left + 1 = 2 - 0 + 1 = 3
Update maxLength: maxLength = max(2, 3) = 3
State:
left = 0, right = 2, zeroCount = 1, maxLength = 3
Subarray: [0, 1, 1]
Iteration 4 (right = 3):
Current Element: nums[3] = 0
Increment zeroCount because it's a zero: zeroCount = 2
Since zeroCount (2) <= k (2), we do not shrink the window.
Calculate the current length: length = right - left + 1 = 3 - 0 + 1 = 4
Update maxLength: maxLength = max(3, 4) = 4
State:
left = 0, right = 3, zeroCount = 2, maxLength = 4
Subarray: [0, 1, 1, 0]
Iteration 5 (right = 4):
Current Element: nums[4] = 0
Increment zeroCount because it's a zero: zeroCount = 3
Now, zeroCount (3) > k (2), so we need to shrink the window:
Move left to 1: nums[0] is a zero, so decrement zeroCount: zeroCount = 2
Now zeroCount (2) <= k (2), we stop shrinking.
Calculate the current length: length = right - left + 1 = 4 - 1 + 1 = 4
maxLength remains unchanged: maxLength = max(4, 4) = 4
State:
left = 1, right = 4, zeroCount = 2, maxLength = 4
Subarray: [1, 1, 0, 0]
Iteration 6 (right = 5):
Current Element: nums[5] = 1
zeroCount remains 2 (no change).
Since zeroCount (2) <= k (2), we do not shrink the window.
Calculate the current length: length = right - left + 1 = 5 - 1 + 1 = 5
Update maxLength: maxLength = max(4, 5) = 5
State:
left = 1, right = 5, zeroCount = 2, maxLength = 5
Subarray: [1, 1, 0, 0, 1]
Final State:
After processing all elements, the final value of maxLength is 5.
This corresponds to the subarray [1, 1, 0, 0, 1].
Summary of Iterations:
Iteration 1: maxLength = 1, Subarray: [0]
Iteration 2: maxLength = 2, Subarray: [0, 1]
Iteration 3: maxLength = 3, Subarray: [0, 1, 1]
Iteration 4: maxLength = 4, Subarray: [0, 1, 1, 0]
Iteration 5: maxLength = 4, Subarray: [1, 1, 0, 0]
Iteration 6: maxLength = 5, Subarray: [1, 1, 0, 0, 1]
Final Result = 5
Optimal Codes in all Languages
1. C++ Try on Compiler
#include <bits/stdc++.h>
using namespace std;
int findMaxConsecutiveOnes(vector<int>& nums, int k) {
int left = 0, right = 0;
int zeroCount = 0;
int maxLength = 0;
for (right = 0; right < nums.size(); right++) {
if (nums[right] == 0) {
zeroCount++;
}
while (zeroCount > k) {
if (nums[left] == 0) {
zeroCount--;
}
left++;
}
maxLength = max(maxLength, right - left + 1);
}
return maxLength;
}
2. Java Try on Compiler
import java.util.*;
public class MaxConsecutiveOnes {
// Function to find the maximum consecutive ones after flipping at most k zeros
public static int findMaxConsecutiveOnes(int[] nums, int k) {
int left = 0, right = 0;
int zeroCount = 0;
int maxLength = 0;
// Traverse the array using the right pointer
for (right = 0; right < nums.length; right++) {
// If current element is 0, increment the zeroCount
if (nums[right] == 0) {
zeroCount++;
}
// If the number of zeros exceeds k, shrink the window from the left
while (zeroCount > k) {
if (nums[left] == 0) {
zeroCount--;
}
left++; // Move the left pointer to shrink the window
}
// Calculate the maximum length of valid window
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}
}
3. Python Try on Compiler
def findMaxConsecutiveOnes(nums, k):
left = 0
zero_count = 0
max_length = 0
# Traverse the array using the right pointer
for right in range(len(nums)):
if nums[right] == 0:
zero_count += 1
# Shrink the window from the left if zero_count exceeds k
while zero_count > k:
if nums[left] == 0:
zero_count -= 1
left += 1
# Calculate the maximum length of the valid window
max_length = max(max_length, right - left + 1)
return max_length
4. JavaScript Try on Compiler
function findMaxConsecutiveOnes(nums, k) {
let left = 0, zeroCount = 0, maxLength = 0;
// Traverse the array using the right pointer
for (let right = 0; right < nums.length; right++) {
if (nums[right] === 0) {
zeroCount++;
}
// Shrink the window from the left if zeroCount exceeds k
while (zeroCount > k) {
if (nums[left] === 0) {
zeroCount--;
}
left++;
}
// Calculate the maximum length of the valid window
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}
Time Complexity : O(n)
The outer loop iterates through the array with the variable right, which runs from 0 to n - 1 (where n is the length of the array).
This loop runs n times.
Inside the outer loop, there is a while loop that may be executed when zeroCount exceeds k. This loop moves the left pointer to the right until zeroCount is less than or equal to k.
In the worst case, each element can be visited twice: once by right and once by left.
Putting these together, the total time complexity of the algorithm is O(n)
Space Complexity: O(n)
Auxiliary Space Complexity
The algorithm uses a few integer variables (left, zeroCount, and maxLength), which occupy constant space.
No additional data structures (like arrays or lists) are created that depend on the size of the input.
Thus, the auxiliary space complexity is O(1).
Total Space Complexity
The input array nums is provided as part of the problem and takes O(n) space.
As noted above, the auxiliary space used is O(1).
Therefore, the total space complexity, which accounts for the input and auxiliary space, is O(n).
Learning Tip:
Given a binary array nums, return the maximum number of consecutive 1's in the array.
An alphabetical continuous string is a string consisting of consecutive letters in the alphabet. In other words, it is any substring of the string "abcdefghijklmnopqrstuvwxyz".
- For example, "abc" is an alphabetical continuous string, while "acb" and "za" are not.
Given a string s consisting of lowercase letters only, return the length of the longest alphabetical continuous substring.