Arrays are the most basic data structures that must be mastered before any coding interview. There are a lot of leetcode questions about it, but here we will discuss how to Find the Maximum Consecutive Ones in a binary array based on binary numbers.
Maximum Consecutive Ones problem
In the Maximum Consecutive Ones problem, we are given a binary array (consisting of 1s and 0s) and we have to find the maximum consecutive 1s in the array.
For example, the given array above is [ 1, 0, 0, 1, 1, 1, 0, 1]. Then, the maximum number of consecutive ones is 3 as shown below:
This problem is very important when we need to manipulate arrays or real-world applications where binary sequences are involved.
Solution
It is quite an easy problem at first glance! We just need to iterate over the array and keep adding consecutive ones.
If we find 0 at any index compare the previous sum with the maximum consecutive 1s. If the previous sum exceeds the maximum consecutive 1s then update the maximum with the previous sum. Make the previous sum = 0 and repeat the same process.
Let’s take another example of understand this solution:
- First create two variables, the previous sum, and the maximum consecutive ones. Initialize both with 0.
- Now iterate over the array and if you find 1 then update our previous sum to previous sum + 1.
- Otherwise, update the previous sum = 0.
- At last, check if the maximum consecutive ones is less than the previous sum or not. If it is less update the maximum consecutive ones to the previous sum.
- Return the maximum consecutive ones at last.
Finally, it’s time to implement it.
C++ Code
Here is the C++ program to find maximum consecutive 1s in a binary array:
#include<bits/stdc++.h>
using namespace std;
int max_ones(vector<int>& nums){
int max_consecutive_ones=0, previous_sum=0;
for(int i=0;i<nums.size();i++){
if(nums[i]==0) previous_sum=0;
else {
previous_sum++;
max_consecutive_ones = max(max_consecutive_ones, previous_sum);
}
}
return max_consecutive_ones;
}
int main(){
vector<int> nums = {1, 0, 0, 1, 1, 1, 0, 1};
int result = max_ones(nums);
cout<<"Maximum Consecutive Ones in the array: "<<result;
return 0;
}Java Code
We can implement the solution in Java also:
import java.util.*;
class Main {
public static int maxOnes(List<Integer> nums) {
int maxConsecutiveOnes = 0;
int previousSum = 0;
for (int i = 0; i < nums.size(); i++) {
if (nums.get(i) == 0)
previousSum = 0;
else {
previousSum++;
maxConsecutiveOnes = Math.max(maxConsecutiveOnes, previousSum);
}
}
return maxConsecutiveOnes;
}
public static void main(String[] args) {
List<Integer> nums = new ArrayList<>(Arrays.asList(1, 0, 0, 1, 1, 1, 0, 1));
int result = maxOnes(nums);
System.out.println("Maximum Consecutive Ones in the array: " + result);
}
}Python Code
Below is the Python program for the solution:
def max_ones(nums):
max_consecutive_ones = 0
previous_sum = 0
for num in nums:
if num == 0:
previous_sum = 0
else:
previous_sum += 1
max_consecutive_ones = max(max_consecutive_ones, previous_sum)
return max_consecutive_ones
def main():
nums = [1, 0, 0, 1, 1, 1, 0, 1]
result = max_ones(nums)
print("Maximum Consecutive Ones in the array:", result)
if __name__ == "__main__":
main()Output:
Maximum Consecutive Ones in the array: 3The time complexity to find the maximum consecutive ones in a binary array is O(n) where n is the size of the array. We are iterating the array once which took O(n) time complexity. The space complexity will be O(1) as we are not using any extra space.
In programming competitions, such easy problems become tricky at first but if the participant can solve it efficiently, it demonstrates proficiency in algorithmic problem-solving skills. Here is a guide to practising leetcode problems to master the skills.
Conclusion
In this article, we solved the leetcode problem titled Maximum Consecutive Ones. Some similar array problems to try are finding the minimum in a rotated sorted array, finding the maximum product subarray, and finding kth largest element in an array.
