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.
1#include <iostream>
2#include <vector>
3
4int findMaxConsecutiveOnes(std::vector<int>& nums) {
5 int maxCount = 0, currentCount = 0;
6 for(int num : nums) {
7 if(num == 1) {
8 currentCount++;
9 maxCount = std::max(maxCount, currentCount);
10 } else {
11 currentCount = 0;
12 }
13 }
14 return maxCount;
15}
16
17int main() {
18 std::vector<int> nums = {1, 1, 0, 1, 1, 1};
19 std::cout << "The maximum number of consecutive 1s is: " << findMaxConsecutiveOnes(nums) << std::endl;
20 return 0;
21}This C++ solution uses a for-each loop for cleanly iterating over each element in the vector. The logic remains similar: incrementing the count for each 1 and resetting on encountering a 0.
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.
Here, Java implements the sliding window by smoothly sliding the left after encountering zeros and considering the right index for effective window measurement.