</>EmbeddedInterview

How do you find the maximum number of consecutive 1s in a binary array?

EasyArrays & Strings (Coding Round)

Short answer: Keep a running count of 1s, reset it to 0 on every 0, and remember the largest count seen. One pass, O(n) time, O(1) space.

#include <stddef.h>

size_t max_consecutive_ones(const int *arr, size_t n)
{
    size_t count = 0, best = 0;
    for (size_t i = 0; i < n; i++) {
        if (arr[i] == 1) {
            count++;
            if (count > best) best = count;
        } else {
            count = 0;
        }
    }
    return best;
}
/* {0,1,1,1,1,0,1,1,1,1,1,1,0,0,1,0} -> 6 */

Why update best inside the 1 branch: if the array ends with a run of 1s, there is no 0 afterwards to trigger a final comparison. Updating as you go avoids a separate check after the loop.

Bit-level version (popular in firmware interviews: longest run of 1s in a 32-bit register):

unsigned longest_run_of_ones(uint32_t x)
{
    unsigned n = 0;
    while (x) {
        x &= x << 1;      /* each step shortens every run by one */
        n++;
    }
    return n;
}
/* 0b0111_1011 -> 4 */

Each x &= x << 1 removes the lowest 1 of every run, so the number of iterations equals the length of the longest run.

Follow-ups

  • Flip at most one 0 to maximise the run: sliding window that allows at most one 0 inside; when a second 0 enters, move the left edge past the first 0.
  • At most k zeros: the same window with a zero counter.
  • Real use: finding the longest free block in an allocation bitmap.