Difficulty: Medium, Asked-in: Amazon, VMware
Key takeaway: This is one of the best problems to understand the idea of the sliding window technique. Using this approach, we can solve several interview problems efficiently in O(n) time and O(1) space.
You are given an array of 1s and 0s and you are given an integer k which signifies the number of flips allowed. Write a program to return the count of the maximum number of consecutive 1's in the array if you can flip at most k 0's.
Input: X[]= [1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1], k = 2, Output: 8
Explanation: We are allowed to flip a maximum of 2 zeroes. If we flip X[5] and X[7], we get 8 consecutive 1’s which is the maximum possible under given constraints.
Input: X[] = [1, 1, 0, 1, 0, 1, 0, 0, 1], k = 1, Output: 4
Explanation: We are allowed to flip a maximum of 1 zero. If we flip X[2], we get 4 consecutive 1's which is the maximum possible under given constraints.
A brute force solution is to consider every subarray by running two nested loops. For every subarray, we count the number of zeroes in it and return the maximum size subarray with k or fewer zeroes. (Think!)
int maxContinuousOnes(int X[], int n, int k)
{
int maxOneCount = 0;
for(int i = 0; i < n; i = i + 1)
{
int countZeros = 0;
int j = i;
while (j < n)
{
if(X[j] == 0)
{
countZeros = countZeros + 1;
if(countZeros > k)
break;
}
j = j + 1;
}
maxOneCount = max(maxOneCount, j - i);
}
return maxOneCount;
}
def max_continuous_ones(X, n, k):
max_one_count = 0
for i in range(n):
count_zeros = 0
j = i
while j < n:
if X[j] == 0:
count_zeros = count_zeros + 1
if count_zeros > k:
break
j = j +1
max_one_count = max(max_one_count, j - i)
return max_one_count
In the worst case, we need to check every small subarray. For this, we are running two nested loops in the solution where for every value of i, j is going from i to n-1. Total no of loop count = n + n -1 + n-2 …+ 1 = n(n-1)/2 = O(n²).
We are only using a constant number of extra variables, so space complexity = O(1)
The critical question is: can we improve the solution further and solve this problem using a single traversal array? Is there some insight into the problem which could help us to build a better solution? Let's think!
There are only 0's and 1's in the array. So there would be two scenarios:
So the idea using the sliding window would be to track each window with k number of 0's and find the maximum size of such window. How do we do this? Let's think! The idea is to scan the array using a loop and count the 0's in each window:
int maxConsecutiveOne(int X[], int n, int k)
{
int zeroCount = 0;
int l = 0;
int maxOneCount = 0;
for (int r = 0 ; r < n; r = r + 1)
{
if(X[r] == 0)
zeroCount = zeroCount + 1;
if(zeroCount > k)
{
if(X[l] == 0)
zeroCount = zeroCount - 1;
l = l + 1;
}
maxOneCount = max(maxOneCount, r - l + 1);
}
return maxOneCount;
}
def max_consecutive_one(X, n, k):
zero_count = 0
l = 0
max_one_count = 0
for r in range(n):
if X[r] == 0:
zero_count = zero_count + 1
if zero_count > k:
if X[l] == 0:
zero_count = zero_count - 1
l = l + 1
max_one_count = max(max_one_count, r - l + 1)
return max_one_count
In the above code, we are running a single loop and doing a constant number of operations at each iteration. So time complexity = n*O(1) = O(n). We are only using a constant number of extra variables, so space complexity = O(1)
Enjoy learning, Enjoy coding!
Subscribe to get well designed content on data structure and algorithms, machine learning, system design, object orientd programming and math.
©2023 Code Algorithms Pvt. Ltd.
All rights reserved.