Problem Statement:
Given a binary array nums, return the maximum number of consecutive 1’s in the array.
Examples
Example 1:
Input:nums = [1,1,0,1,1,1]
Output:3
Explanation
The first two digits or the last three digits are consecutive 1s. The maximum number of consecutive 1s is 3.
Example 2:
Input:nums = [1,0,1,1,0,1]
Output:2
Constraints:
- 1 <= nums.length <= 105
- nums[i] is either 0 or 1.
Optimal Approach: Single Pass
- Initialize two variables:
currentCount→ to count current streak of 1smaxCount→ to keep track of the maximum streak seen so far- Traverse the array:
-
If
nums[i] == 1, incrementcurrentCount. -
If
nums[i] == 0, comparecurrentCountwithmaxCount, updatemaxCount, then resetcurrentCountto 0. -
After the loop, return the maximum of
maxCountandcurrentCount(to handle case where array ends in 1s)
Visualisation:
Time Complexity:
Time Complexity = O(n)
Space Complexity:
Space Complexity = O(1)
Dry Run
Input: nums = [1, 1, 0, 1, 1, 1]
i = 0 → nums[i] = 1 → currentCount = 1 i = 1 → nums[i] = 1 → currentCount = 2 i = 2 → nums[i] = 0 → maxCount = 2, currentCount = 0 i = 3 → nums[i] = 1 → currentCount = 1 i = 4 → nums[i] = 1 → currentCount = 2 i = 5 → nums[i] = 1 → currentCount = 3
Output: max(2, 3) = 3
var findMaxConsecutiveOnes = function(nums) {
let currentCount = 0;
let maxCount = 0;
for (let i = 0; i < nums.length; i++) {
if (nums[i] == 1) {
currentCount++;
} else {
maxCount = Math.max(currentCount, maxCount);
currentCount = 0;
}
}
return Math.max(maxCount, currentCount);
};
class Solution:
def findMaxConsecutiveOnes(self, nums):
currentCount = 0
maxCount = 0
for num in nums:
if num == 1:
currentCount += 1
else:
maxCount = max(maxCount, currentCount)
currentCount = 0
return max(maxCount, currentCount)
class Solution {
public int findMaxConsecutiveOnes(int[] nums) {
int currentCount = 0;
int maxCount = 0;
for (int num : nums) {
if (num == 1) {
currentCount++;
} else {
maxCount = Math.max(maxCount, currentCount);
currentCount = 0;
}
}
return Math.max(maxCount, currentCount);
}
}
class Solution {
public:
int findMaxConsecutiveOnes(vector& nums) {
int currentCount = 0, maxCount = 0;
for (int num : nums) {
if (num == 1) {
currentCount++;
} else {
maxCount = max(maxCount, currentCount);
currentCount = 0;
}
}
return max(maxCount, currentCount);
}
};
int findMaxConsecutiveOnes(int* nums, int numsSize) {
int currentCount = 0, maxCount = 0;
for (int i = 0; i < numsSize; i++) {
if (nums[i] == 1) {
currentCount++;
} else {
if (currentCount > maxCount)
maxCount = currentCount;
currentCount = 0;
}
}
return currentCount > maxCount ? currentCount : maxCount;
}
public class Solution {
public int FindMaxConsecutiveOnes(int[] nums) {
int currentCount = 0, maxCount = 0;
foreach (int num in nums) {
if (num == 1) {
currentCount++;
} else {
maxCount = Math.Max(maxCount, currentCount);
currentCount = 0;
}
}
return Math.Max(maxCount, currentCount);
}
}
