**Difficulty:** Easy, **Asked-In:** Amazon, Adobe, Hike

**Key takeaway:** An excellent problem to learn problem-solving using the sliding window approach and incremental approach using a single loop.

An input array X[] is given where all elements are either 0 or 1. Write a program to find the maximum number of consecutive 1's in the binary array.

Input: X[] = [**1, 1**, 0, **1, 1, 1,** 0, 0, **1**], Output: 3

Explanation: There are 6 ones in the array: Two consecutive 1's from index 0 to 1, three 1's are present from index 3 to 5, and one 1 is present at index 8. So the max consecutive 1's count is 3.

Input: X[] = [0, **1, 1, 1, 1,** 0, 0, 1, 1], Output: 4

Explanation: There are 6 ones in the array: Four 1's are occurring consecutively from index 1 to 5 and two 1's are present sequentially from index 7 to 8. So the max consecutive 1's count is 4.

Input: X[] = [**1, 1, 1, 1**], Output: 4

Explanation: All values in the array are 1. So the max consecutive 1's count is 4.

Input: X[] = [0, 0, **1,** 0, 1], Output: 1

Explanation: There is only 1 one in the array. So the max consecutive 1's count is 1.

**Important note:** Before moving on to the solutions, we recommend trying this problem on paper for atleast 15 or 30 minutes. Enjoy problem-solving!

- Brute force solution by considering every sub-array
- Optimized solution using the sliding window approach
- Efficient solution using a single scan

The subarray with max continuous 1's must be starting from some index i and ending at some index j. So one basic idea would be to explore each subarray **[i, j]** and track the max 1's count. For this, we can run two nested loops: Outer loop to track the starting index (i) of each subarray and inner loop to calculate consecutive 1's count starting from index i. Using a variable, we also track the overall max 1's count seen so far.

- We initialize variable
**maxOneCount = 0**to track max one count so far. - We run nested loops to explore each subarray i.e. outer loop from
**i = 0 to n - 1**and inner loop from**j = i to n - 1.**Before starting the inner loop, we also initialize variable**oneCount = 0**to track the ones count in each subarray. - Inside inner loop, when X[j] == 1, we increment oneCount by 1. Otherwise, we will be present at the end of 1's sequence, so we break the inner loop.
- Before moving to the next iteration of the outer loop, we compare maxOneCount with oneCount. If
**maxOneCount < oneCount**, we update**maxOneCount = oneCount.** - Similarly, we continue exploring all sub-array starting from index i and updating maxOneCount. By the end of nested loops, we return
**maxOneCount**.

```
// Finds the maximum consecutive number of ones in the given array
int findMaxConsecutiveOnes(int X[], int n)
{
int maxOneCount = 0;
for (int i = 0; i < n; i = i + 1)
{
int oneCount = 0;
for (int j = i; j < n; j = j + 1)
{
if (X[j] == 1)
oneCount = oneCount + 1;
else
break;
}
if (oneCount > maxOneCount)
maxOneCount = oneCount;
}
return maxOneCount;
}
```

```
def findMaxConsecutiveOnes(X, n):
maxOneCount = 0
for i in range(n):
oneCount = 0
for j in range(i, n):
if X[j] == 1:
oneCount = oneCount + 1
else:
break
if oneCount > maxOneCount:
maxOneCount = oneCount
return maxOneCount
```

We are running nested loops to explore each subarray. Total number of loop iterations in the worst case = n + n - 1 + ...+ 2 + 1 = n(n + 1)/2 = O(n^2). At each iteration, we are performing constant or O(1) operations. So time complexity = O(n^2) * O(1) = O(n^2). What would be the scenario of the worst and best case input? Think! Space complexity = O(1), as we are using a constant extra space for variables.

Now critical questions are: Can we improve the time complexity further? Do we need to consider each subarray? If we observe the input closely, we can identify one thing: There will be many groups of consecutive 1's, and we need to identify a group with max consecutive 1's. So rather than exploring every subarray, can we think of an efficient idea to track a group of 1's with the maximum one count?

One idea would be to track the left and right ends of each subarray with consecutive 1's, i.e., left end tracks the first occurrence of 1, and right end tracks the last occurrence of 1's in each group. We also need to update the max 1's count found so far. Think!

This solution idea is a sliding window approach, where we move left end of the window to the first occurrence of 1 in each group and increment the right end until we find 1 in that group. Once the right end reaches the last 1 of the group, we calculate 1's count and update the max one count so far. Think!

- We initialize a window pointer
**leftEnd = 0**to track the left end of window. - We also initialize a variable
**maxOneCount**to track max continuous 1's so far. - Now we run a loop till
**leftEnd < n.** - We first move
**leftEnd**to the first occurrence of 1.**If (X[leftEnd] == 0)**, we keep incrementing leftEnd by 1. After this process, we will be at the starting end of first group. - Now we initialize another window pointer
**rightEnd**with leftEnd and run another loop until we find the next zero in the sequence. In this loop, we continue incrementing rightEnd by 1 when we find**rightEnd < n - 1**and**X[rightEnd + 1] == 1.** - By the end of above loop, window pointer rightEnd will be at the right end of first group. So total number of consecutive 1's in that group
**= rightEnd - leftEnd + 1.** - Now we update the value of maxOneCount:
**if(maxOneCount < rightEnd - leftEnd + 1),**we update maxOneCount with rightEnd - leftEnd + 1. Before moving to the next iteration of outer loop, we also update the leftEnd with rightEnd + 1 to search next group of consecutive 1's. - Now we follow similar procedure for all iterations of the outer loop: Track the first and last occurrence of 1 in each group using window pointers, and update the value of maxOneCount.
- By the end of nested loops, we return maxOneCount.

```
// Finds the maximum consecutive number of ones in the given array
int findMaxConsecutiveOnes(int X[], int n)
{
if (n == 0)
return 0;
int maxOneCount = 0;
int leftEnd = 0;
while (leftEnd < n)
{
if (X[leftEnd] == 0)
leftEnd = leftEnd + 1;
else
{
int rightEnd = leftEnd;
while (rightEnd < n - 1 && X[rightEnd + 1] == 1)
rightEnd = rightEnd + 1;
maxOneCount = std::max(maxOneCount, rightEnd - leftEnd + 1);
leftEnd = rightEnd + 1;
}
}
return maxOneCount;
}
```

```
def find_max_consecutive_ones(X, n):
if n == 0:
return 0
max_one_count = 0
left_end = 0
while left_end < n:
if X[left_end] == 0:
left_end = left_end + 1
else:
right_end = left_end
while right_end < n - 1 and X[right_end + 1] == 1:
right_end = right_end + 1
max_one_count = max(max_one_count, right_end - left_end + 1)
left_end = right_end + 1
return max_one_count
```

We are running two nested loops based on different conditions. Does this time complexity look O(n^2)? Let's analyze it clearly to get an answer.

At each iteration of the outer loop, whenever we find 0, we increment the left pointer. But when we see 1 first time in a group, we continuously increment the right pointer till we find the next 0. At this point, we update the max 1's count and reset the left pointer. So we are accessing each element at once using the left and right pointers. In other words, all the 0's will be accessed by the left pointer, and all the 1's will be accessed by the right pointer.

The total number of nested loop iterations will be O(n), and at each iteration, we perform O(1) operations. So time complexity = O(n) * O(1) = **O(n)**. We are using constant extra space, so space complexity = **O(1)**.

The critical question is: Can we solve the problem using a single scan without using two window pointers? Here is a simple idea: We scan the array from left to right and track the 1's count in each consecutive group of 1's. We also initialize two variables outside the loop: **oneCount** to store the 1's count of the current group and **maxOneCount** to store the max 1's count seen so far.

- When we find X[i] == 1, we increment oneCount by 1 and compare it with maxOneCount. If (oneCount > maxOneCount), we update maxOneCount = oneCount .
- When we encounter X[i] == 0, we reset the value of oneCount as 0.
- By the end of the loop, we return the value stored in variable maxOneCount.

```
int findMaxConsecutiveOnes(int X[], int n)
{
int oneCount = 0;
int maxOneCount = 0;
for (int i = 0; i < n; i = i + 1)
{
if (X[i] == 0)
oneCount = 0;
else
{
oneCount = oneCount + 1;
maxOneCount = max(maxOneCount, oneCount);
}
}
return maxOneCount;
}
```

```
def find_max_consecutive_ones(X, n):
one_count = 0
max_one_count = 0
for i in range(n):
if X[i] == 0:
one_count = 0
else:
one_count = one_count + 1
max_one_count = max(max_one_count, one_count)
return max_one_count
```

We are running a single loop and performing constant operations at each iteration. So time complexity = **O(n)**. Space complexity = **O(1)**, as we are using constant extra space.

- Can we solve this problem using other approaches like recursion or bit manipulation?
- What would be the worst and best case scenario of the 1st approach?
- How the time complexity of the 2nd approach is O(n)?
- Suppose there are three repeated elements in the array: 0, 1, and 2. How do we modify the above code to count the number of 1's? Can we solve this problem in O(n) time?

- Considering each sub-array: Time = O(n^2), Space = O(1)
- Using sliding window: Time = O(n^2), Space = O(1)
- Using a single scan: Time = O(n^2), Space = O(1)

- Maximum number of consecutive 1's in the array if you flip at most k 0's.
- Find the maximum length of a non-empty substring with only one unique character.
- Longest substring without repeating character
- Given a binary string s, return true if the longest contiguous segment of 1's is strictly longer than the longest contiguous segment of 0's in s. Return false otherwise.

Write in the message below if you find anything incorrect, or you want to share more insight, or you know some different approaches to solve this problem. Enjoy learning, Enjoy algorithms, Enjoy coding!