485. Max Consecutive Ones
Model: qwen2.5-coder:14b
Topics: Array
FAANG asked: 1
Acceptance rate: 52.6%
Problem Breakdown
The problem requires finding the maximum number of consecutive 1s in a given binary array. The input is a list of integers where each integer is either 0 or 1. The output should be an integer representing the length of the longest sequence of consecutive 1s.
Inputs:
- A binary array (list of integers) containing only 0s and 1s.
Outputs:
- An integer representing the maximum number of consecutive 1s in the array.
Implicit Constraints/Edge Cases:
- The input array will always contain at least one element.
- The array can be very large, up to 10,000 elements, so an efficient solution is necessary.
- Edge cases include arrays with all 0s, all 1s, or a mix of both.
Intuition
A brute-force approach would involve checking every possible subarray and counting the number of consecutive 1s. This method would have a time complexity of O(n^2), which is inefficient given the constraints.
The key insight to improve this is to use a single pass through the array while keeping track of the current streak of consecutive 1s and updating the maximum streak found so far. This approach leverages a linear scan, reducing the time complexity to O(n).
Approach
To solve this problem efficiently, we can iterate through the array once, maintaining two variables:
current_count: To keep track of the current number of consecutive 1s.max_count: To store the maximum number of consecutive 1s found so far.
As we iterate through the array:
- If the current element is 1, increment
current_count. - If the current element is 0, reset
current_countto 0. - After updating
current_count, check if it’s greater thanmax_count. If so, updatemax_count.
At the end of the iteration, max_count will contain the length of the longest sequence of consecutive 1s.
Complexity Analysis
- Time Complexity: O(n), where n is the length of the input array. We make a single pass through the array.
- Space Complexity: O(1). We use only a constant amount of extra space for variables
current_countandmax_count.
Solution
def findMaxConsecutiveOnes(nums):
current_count = 0
max_count = 0
for num in nums:
if num == 1:
current_count += 1
max_count = max(max_count, current_count)
else:
current_count = 0
return max_count
Edge Cases Handled
- All 0s: The function returns 0 as there are no consecutive 1s.
- All 1s: The function returns the length of the array since all elements are 1s and thus form a single streak.
- Mixed 0s and 1s: The function correctly identifies the longest sequence of consecutive 1s, even if they are interrupted by 0s.