Max Consecutive Ones
Problem link: https://leetcode.com/problems/max-consecutive-ones/
Problem Statement
Given a binary array nums, return the maximum number of consecutive 1s in the array.
Input
A binary array nums consisting only of 0s and 1s.
Output
An integer representing the maximum count of consecutive 1s.
Example
Input: nums = [1,1,0,1,1,1] Output: 3 Explanation: The first two digits are consecutive 1s. The last three digits are consecutive 1s. The maximum number of consecutive 1s is 3.
Explanation
We track the current streak of 1s. When we see a 1, we increment. When we see a 0, we check if the current streak was the longest we've seen so far, then reset to zero.
Brute Force
Intuition
Check every possible subarray. If a subarray contains only 1s, calculate its length and keep track of the maximum length found.
Approach
- Use nested loops to generate all possible subarrays.
- For each subarray, check if every element is 1.
- If it is, update the maximum length.
Dry Run
nums = [1,0,1,1] Subarrays of 1s: [1], [1], [1,1] Max length: 2
Code (Java)
class Solution {
public int findMaxConsecutiveOnes(int[] nums) {
int max = 0;
for (int i = 0; i < nums.length; i++) {
for (int j = i; j < nums.length; j++) {
boolean allOnes = true;
for (int k = i; k <= j; k++) {
if (nums[k] != 1) {
allOnes = false;
break;
}
}
if (allOnes) max = Math.max(max, j - i + 1);
}
}
return max;
}
}
Complexity Analysis
Generating all subarrays is O(N^2), and checking each one is O(N).
Optimal Solution
Intuition
As we walk through the array, we only need to know two things: 'What is my current streak?' and 'What is the longest streak I have seen so far?'. We don't need to look back at previous elements.
Approach
- Initialize
count = 0andmax = 0. - Iterate through each number in the array.
- If the number is 1, increment
count. - Update
maxusingMath.max(max, count). - If the number is 0, reset
countto 0. - Return
max.
Dry Run
nums = [1,1,0,1]
- i=0: count=1, max=1
- i=1: count=2, max=2
- i=2: count=0, max=2
- i=3: count=1, max=2 Result: 2
Code (Java)
class Solution {
public int findMaxConsecutiveOnes(int[] nums) {
int max = 0;
int currentCount = 0;
for (int num : nums) {
if (num == 1) {
currentCount++;
if (currentCount > max) max = currentCount;
} else {
currentCount = 0;
}
}
return max;
}
}
Complexity Analysis
We traverse the array once, performing constant time operations at each step.
Quick Revision (Brute Force)
- Check every subarray
- O(N^3) or O(N^2) time
Quick Revision (Optimal)
- Linear Scan
- Maintain current streak counter
- Reset counter when element is 0
- Keep global maximum
- O(N) time