Max Consecutive Ones
EasyPrompt
Given a binary array nums, return the maximum number of consecutive 1's in the array.
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 <= 105nums[i]is either0or1.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach uses nested loops to check for consecutive ones starting from every possible position in the array. It is straightforward but inefficient.
Algorithm
- Initialize
maxCount = 0. - Iterate through the array with an outer loop using index
ifrom0ton-1. - For each
i, initialize acurrentCount = 0. - Start a nested loop with index
jfromiton-1. - If
nums[j]is1, incrementcurrentCount. - If
nums[j]is0, break the inner loop because the sequence of ones is broken. - After the inner loop completes, update
maxCount = Math.max(maxCount, currentCount). - After the outer loop finishes,
maxCountholds the maximum length found.
Walkthrough
The brute-force method involves iterating through each element of the array with an outer loop. For each element, we consider it as a potential starting point of a sequence of ones. Then, a nested inner loop starts from this point and counts how many consecutive ones follow until a zero or the end of the array is encountered.
A variable maxCount keeps track of the maximum length found so far. After each inner loop finishes counting a sequence, the count is compared with maxCount, and maxCount is updated if the new count is larger. This process is repeated for all possible starting positions.
Here is the Java implementation:
class Solution { public int findMaxConsecutiveOnes(int[] nums) { int maxCount = 0; for (int i = 0; i < nums.length; i++) { int currentCount = 0; for (int j = i; j < nums.length; j++) { if (nums[j] == 1) { currentCount++; } else { // End of the current sequence of ones break; } } if (currentCount > maxCount) { maxCount = currentCount; } } return maxCount; }}Complexity
Time
O(n^2), where n is the length of the input array. In the worst-case scenario, such as an array filled with all ones, the inner loop runs up to n times for each of the n elements, resulting in quadratic time complexity.
Space
O(1), as we only use a constant amount of extra space for counter variables, regardless of the input array size.
Trade-offs
Pros
Simple logic that is easy to understand and implement.
Cons
Highly inefficient for large inputs due to the O(n^2) time complexity.
Performs redundant work by re-scanning parts of the array multiple times.
This is an optimal and efficient approach that finds the solution by iterating through the array only once. It maintains a running count of consecutive ones and updates a maximum count whenever a sequence of ones is broken.
Algorithm
- Initialize two integer variables,
maxCount = 0andcurrentCount = 0. - Iterate through each
numin thenumsarray. - If
numis1, incrementcurrentCount. - If
numis0:- The sequence of ones is broken. Update
maxCount = Math.max(maxCount, currentCount). - Reset
currentCountto0.
- The sequence of ones is broken. Update
- After the loop finishes, there might be a trailing sequence of ones. Perform a final update:
maxCount = Math.max(maxCount, currentCount). - Return
maxCount.
Walkthrough
The single-pass approach is a greedy algorithm that provides an optimal solution. We traverse the array from left to right, keeping track of the length of the current sequence of consecutive ones (currentCount). We also maintain a variable maxCount to store the maximum length found so far.
As we iterate through the array:
- If we encounter a
1, we simply incrementcurrentCount. - If we encounter a
0, it signifies the end of a sequence of ones. We then compare thecurrentCountwithmaxCountand updatemaxCountif the current sequence was longer. After that, we resetcurrentCountto0.
One important edge case is when the array ends with a sequence of ones (e.g., [1, 1, 0, 1, 1, 1]). The final update to maxCount for the trailing sequence happens after the loop concludes.
Here is the Java implementation:
class Solution { public int findMaxConsecutiveOnes(int[] nums) { int maxCount = 0; int currentCount = 0; for (int num : nums) { if (num == 1) { // Increment the count of consecutive ones currentCount++; } else { // Found a 0, so the sequence is broken // Update the max count if the current one is larger maxCount = Math.max(maxCount, currentCount); // Reset the current count currentCount = 0; } } // Final check to account for a sequence at the end of the array return Math.max(maxCount, currentCount); }}Complexity
Time
O(n), where n is the number of elements in the array. This is because we perform a single pass through the array.
Space
O(1), as it only requires a couple of integer variables to store the current and maximum counts.
Trade-offs
Pros
Extremely efficient with a linear time complexity of O(n).
Space-efficient, using only a constant amount of extra memory.
It is the optimal solution since every element must be visited at least once.
Cons
There are no significant disadvantages to this approach as it is optimal for this problem.
Solutions
Solution
class Solution {public int findMaxConsecutiveOnes(int[] nums) { int cnt = 0, ans = 0; for (int v : nums) { if (v == 1) { ++cnt; } else { ans = Math.max(ans, cnt); cnt = 0; } } return Math.max(cnt, ans); }}/** * @param {number[]} nums * @return {number} */ var findMaxConsecutiveOnes = function (nums) { let res = 0, t = 0; for (let num of nums) { if (num == 1) { ++t; } else { res = Math.max(res, t); t = 0; } } return Math.max(res, t); };class Solution {public: int findMaxConsecutiveOnes(vector<int> &nums) { int cnt = 0, ans = 0; for (int v : nums) { if (v == 1) { ++cnt; } else { ans = max(ans, cnt); cnt = 0; } } return max(ans, cnt); }};class Solution: # hehe class Solution : def findMaxConsecutiveOnes ( self , nums : List [ int ]) -> int : return max ( len ( s ) for s in '' . join ( str ( x ) for x in nums ). split ( '0' ) ) def findMaxConsecutiveOnes(self, nums: List[int]) -> int: cnt = ans = 0 for v in nums: if v == 1: cnt += 1 ans = max(ans, cnt) else: cnt = 0 return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.