Traversals - 5
Max Consecutive Ones
In this problem, we'll have an array of integers only, but it'll contain just 0's and 1's. Our target is to find out the maximum number of consecutive 1
's
In other words, our target is to find the length of the largest subarray, that contains no 0's at all.
Subarray is a contiguous sub-part of an array. E.g. [2, 3] , [3, 4, 5], [1] are subarrays of [1, 2, 3, 4, 5], whereas [2, 4, 5], [1, 3] are not.
How to solve it?
If I try to think like a beginner, the first approach that comes to my mind is:
The Approach
Let's keep a variable final_ans that is initialised with 0 in the beginning, and then do the following:- Let's iterate over all the subarrays
-
Somehow, check if the condition of all ones is satisfied.
- If yes, update the final_ans variable if length of this subarray is greater than final_ans
- Else, keep going.
Code
int findMaxConsecutiveOnes(vector<int>& arr) {
int final_ans = 0, n = arr.size();
// iterate over all possible
// start values for a subarray
for(int l = 0; l < n; ++l) {
int num_of_zeroes = 0;
// iterate over all possible
// end values for a subarray
// for this particular l value.
for(int r = l; r < n; ++r) {
if(arr[r] == 0)
num_of_zeroes++;
if(num_of_zeroes == 0)
final_ans = max(final_ans, r - l + 1); // because current_length = (r - l + 1)
}
}
return final_ans;
}
Explaining some elements of the code
I hope the overal idea is clear, as it has already been explained in The Approach section.
I'll just cover the inner loop part here, which is to explain why are we checking if arr[r] is equal to 0 or not. Some of you may think, don't we need to check all the elements? why are we just checking for arr[r]?
The answer is that if you check for all the elements b/w the indices l and r, that'll be absolutely right, but that'll make our code even slower. Care to guess the time complexity in that case?
Click to reveal.
The time complexity in that case will be O(N3). I urge you to think about the reason yourself.Okay, coming back to the question that is checking for just arr[r] enough? The answer is yes; take an example array and try to dry-run the code line-by-line on that, you'll see that although we're only checking for arr[r], yet it's correct because we've already stored the number of 0's in the num_of_zeroes variable for the range [l, r-1] during the previous iterations.
Time and Space Complexity
- Time Complexity: O(N2)
- Space Complexity: O(1)
A more efficient solution
The above discussed solution is kinda brute force, as we're going to every subarray and checking if it meets the condition.
Can we do it by traversing through the array just once? Let's give it a try.
Hint
Traversing is like a box of chocolates, you never know what you'll get.
Well, in this case, it'll be either 1 or 0. If it's one, then the window of 1's is basically expanding as you've gotten one more 1. If you get 0, then the window of 1's has to be reset, right?
Complete Explanation
The idea is similar to what's already told in the hint. We'll keep track of the number of 1's as we get 1's while iterating, and we'll reset the count to 0 if a 0 is enocountered in between.
We'll keep 2 variables, final_ans and cur_count, both initialised with 0. Then, we'll iterate over the array and do the following in each iteration:
- If arr[i] == 1, then increment the value of cur_count by 1.
- Otherwise if arr[i] == 0, then reset the value of cur_count equal to 0.
- Keep updating the value of final_ans appropriately in each iteration so that we have the maximum number of consecutive 1's so far saved safely.
Code
int findMaxConsecutiveOnes(vector<int>& arr) {
// final_ans: stores the maximum consecutive ones.
// cur_count: stores the number of consecutive ones in the current window.
int final_ans = 0, cur_count = 0;
for(int num : arr) {
if(num == 1)
cur_count++;
else
cur_count = 0;
final_ans = max(final_ans, cur_count);
}
return final_ans;
}
Time and Space Complexity
If we look at the above code carefully, all we've done is traverse tha array once and a couple of if-else operations in each iteration. Also, for space, we've just used a couple of int variables, nothing more. Therefore:- Time Complexity: O(N)
- Space Complexity: O(1)
I hope that you're enjoying the articles so far. Please use this form to provide some feedback and/or to show your appreciation.