JuniorDebuggingCommonNot answered yet
Fix the longest-run-of-ones counter that drops the final run
This function should return the length of the longest run of consecutive 1s, but it reports the wrong answer for arrays ending in 1s, e.g. {0,1,1,1} returns 0.
Find and fix the bug.
int maxConsecutiveOnes(const std::vector<int>& nums) {
int cur = 0, best = 0;
for (int n : nums) {
if (n == 1) {
cur++;
} else {
best = std::max(best, cur); // max only taken on a zero
cur = 0;
}
}
return best;
}Find and fix the bug.
best is updated only in the else (zero) branch, so a trailing run of 1s that never hits a zero is never compared. Fix it by updating best = max(best, cur) on every 1 (inside the if), or once more after the loop. O(n).
- ✗Believing the counter is correct because it works for arrays ending in 0
- ✗Updating max only at run boundaries marked by a zero
- ✗Adding a post-loop check but forgetting the empty-array case
- →How would the fix change if you also had to return the run's start index?
- →What is the analogous bug for the longest run of any fixed value?
Contents
Task
The longest-run-of-ones counter loses a run the array ends with. Find and fix the bug.
Solution
int maxConsecutiveOnes(const std::vector<int>& nums) {
int cur = 0, best = 0;
for (int n : nums) {
if (n == 1) {
cur++;
best = std::max(best, cur); // update on every 1
} else {
cur = 0;
}
}
return best;
}Key points
- Bug: the maximum was taken only in the
elsebranch, on a zero. - A trailing run of ones is therefore never compared.
- Fix by updating the maximum on every
1(or once after the loop).
Contents
