Traversals - 5

1. Let's iterate over all the subarrays
2. 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.

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;
}

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?

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 Complexity: O(N²)
• Space Complexity: O(1)

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?

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:

1. If arr[i] == 1, then increment the value of cur_count by 1.
2. Otherwise if arr[i] == 0, then reset the value of cur_count equal to 0.
3. 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.

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 Complexity: O(N)
• Space Complexity: O(1)