Prerequisites
Before attempting this problem, you should be comfortable with:
- Arrays - Understanding how to traverse and access array elements sequentially
- Basic Iteration - Using loops to scan through elements and track state with counters
1. Brute Force
Intuition
For each position in the array, we count how many consecutive 1s start from that position. We scan forward until we hit a 0 or the end of the array, then track the maximum count seen. This straightforward approach checks every possible starting position.
Algorithm
- Initialize
resto0to track the maximum consecutive ones. - For each starting index
i:- Initialize a counter
cntto0. - Scan forward from
iwhile the current element is1, incrementing the counter. - Stop when encountering a
0or reaching the end. - Update
reswith the maximum ofresandcnt.
- Initialize a counter
- Return
res.
Time & Space Complexity
- Time complexity:
- Space complexity:
2. Iteration - I
Intuition
We only need one pass through the array. Maintain a running count of consecutive 1s. When we see a 1, increment the count. When we see a 0, compare the current count with the maximum, then reset the count to 0. After the loop, we do one final comparison since the longest sequence might end at the last element.
Algorithm
- Initialize
resandcntto0. - Iterate through each element in the array:
- If the element is
0, updatereswith the maximum ofresandcnt, then resetcntto0. - If the element is
1, incrementcnt.
- If the element is
- Return the maximum of
resandcnt(to handle sequences ending at the array's end).
Time & Space Complexity
- Time complexity:
- Space complexity:
3. Iteration - II
Intuition
We can simplify the logic by updating the maximum inside the loop at every step. If we see a 1, we increment the count; otherwise, we reset it to 0. After each element, we update the result. This eliminates the need for a final comparison after the loop.
Algorithm
- Initialize
resandcntto0. - For each element in the array:
- If the element is
1, incrementcnt. - Otherwise, set
cntto0. - Update
resto be the maximum ofresandcnt.
- If the element is
- Return
res.
Time & Space Complexity
- Time complexity:
- Space complexity:
Common Pitfalls
Forgetting the Final Comparison
When tracking consecutive ones by resetting the counter on encountering a zero, the longest sequence might end at the last element of the array. If you only update the maximum inside the loop when hitting a zero, you will miss this case. Always compare the final count with the result after the loop ends, or update the maximum on every iteration.
Resetting the Counter Incorrectly
A subtle bug is resetting the counter to 1 instead of 0 when encountering a zero, or incrementing before checking the current element. The counter should be reset to 0 when a zero is found, then the next 1 will increment it to 1. Mixing up this logic leads to off-by-one errors in the count.