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 either 0 or 1.The key idea in #485 Max Consecutive Ones is to scan the array and track the length of consecutive 1s. Since the array contains only binary values (0 and 1), each 0 breaks the current streak of ones. The goal is to maintain the maximum streak encountered during the traversal.
A common approach is to iterate through the array once while keeping two variables: one for the current consecutive count and another for the maximum count found so far. When a 1 appears, increment the current counter. When a 0 appears, update the maximum if needed and reset the counter. This ensures the longest sequence of ones is recorded efficiently.
This strategy works well because it processes each element only once. The algorithm runs in O(n) time with O(1) extra space, making it optimal for large arrays.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Single Pass Linear Scan | O(n) | O(1) |
take U forward
Use these hints if you're stuck. Try solving on your own first.
You need to think about two things as far as any window is concerned. One is the starting point for the window. How do you detect that a new window of 1s has started? The next part is detecting the ending point for this window. How do you detect the ending point for an existing window? If you figure these two things out, you will be able to detect the windows of consecutive ones. All that remains afterward is to find the longest such window and return the size.
This approach involves iterating through the array and counting sequences of 1s. If a 0 is encountered, the count is reset to 0. We keep track of the maximum count during the iteration.
Time Complexity: O(n), where n is the number of elements in the array, as we make a single pass.
Space Complexity: O(1) since no extra space proportional to input size is used.
1def findMaxConsecutiveOnes(nums):
2 maxCount = 0
3 currentCount = 0
4 for num in nums:
5 if num == 1:
This Python code iterates through the list nums, updating counts similarly to previous implementations. It's straightforward with the use of Python's built-in max function.
This approach uses a variation of the sliding window technique. The idea is to maintain a window of the current sequence of 1s and adjust the window whenever a 0 is encountered.
Time Complexity: O(n)
Space Complexity: O(1)
1function findMaxConsecutiveOnes
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of this problem appear in coding interviews at companies like Amazon, Google, and Meta. Interviewers often use it to test array traversal, counting techniques, and understanding of linear-time solutions.
No special data structure is required for this problem. A simple array traversal with a few integer variables to track the current and maximum streak is sufficient.
The optimal approach is a single-pass traversal of the array while counting consecutive 1s. Each time a 0 is encountered, the current count resets and the maximum count is updated if needed. This method achieves O(n) time and O(1) space complexity.
While a sliding window idea can conceptually apply to tracking segments, it is unnecessary here. A straightforward linear scan with counters is simpler and already achieves optimal performance.
This JavaScript implementation uses the sliding window algorithm, emphasizing managing indices to measure and optimize the sequence of 1s.