Topics › Arrays › Easy

Maximum Consecutive Ones

Easy TUF ID 42 A2ZSDE

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given a binary array nums, meaning every element is either 0 or 1. Return the length of the longest run of consecutive 1s. A run is a block of adjacent positions that all hold 1; a single 0 anywhere breaks it. If the array contains no 1 at all, the answer is 0.

Constraints: 0 ≤ n ≤ 10^5, nums[i] is 0 or 1.

Example 1

nums = [1, 1, 0, 1, 1, 1]
answer = 3          // the run at indices 3..5

Example 2

nums = [1, 0, 1, 1, 0, 1]
answer = 2          // the run at indices 2..3; the other runs have length 1

Example 3

nums = [0, 0, 0]
answer = 0          // there is no 1

Approach 1: Brute force

Intuition. A run of ones is fully described by where it starts. So try every index as a potential start, walk right while you keep seeing 1, and measure how far you got. The longest walk is the answer. Starting from a 0 gives a walk of length 0, which is harmless.

Algorithm.

1. For every index i from 0 to n - 1:
2. Set j = i and advance j while j < n and nums[j] == 1.
3. The run starting at i has length j - i; keep the maximum.
4. Return the maximum.

static int bruteForce(int[] nums) {
    int n = nums.length, best = 0;
    for (int i = 0; i < n; i++) {
        int j = i;
        while (j < n && nums[j] == 1) j++;
        best = Math.max(best, j - i);
    }
    return best;
}

Complexity. Time O(n^2) in the worst case: on an all-ones array, the walk from index i visits n - i elements, which sums to about n^2 / 2. Space O(1): two counters.

The waste is obvious once you see it: when the walk from index 0 has already visited indices 1, 2, 3, the walks that start at those indices repeat the same work and can only find shorter runs (they are suffixes of the run we just measured). One pass should be enough.

Approach 2: Optimal, a running counter

Intuition. Scan once from left to right carrying a single number: the length of the run that ends at the current position. A 1 extends that run by one; a 0 ends it, so the counter drops back to zero. The answer is the largest value the counter ever reached. Nothing about an earlier run matters once it is broken, which is exactly why one integer of state is enough.

Algorithm.

1. Set best = 0 and run = 0.
2. For every element x:
   • if x == 1, increment run and update best if run is larger;
   • otherwise set run = 0.
3. Return best.

static int optimal(int[] nums) {
    int best = 0, run = 0;
    for (int x : nums) {
        if (x == 1) {
            run++;
            if (run > best) best = run;
        } else {
            run = 0;
        }
    }
    return best;
}

Dry run on nums = [1, 1, 0, 1, 1, 1]:

Complexity. Time O(n): each element is looked at exactly once. Space O(1): two integers.

Why is updating best inside the x == 1 branch sufficient? best can only grow when run grows, and run only grows on a 1. Updating it after the loop as well, as some people do “to catch a run that ends at the last element”, is unnecessary: that run was already counted when its last 1 was processed.

Approach 3: Optimal, distance from the last zero

Intuition. The same sweep can be phrased without a counter. The run that ends at index i extends back to just after the most recent 0. If you remember the index of that 0 (call it lastZero, initialised to -1 as if there were a zero just before the array), the length of the run ending at i is simply i - lastZero. This formulation is handy in follow-up problems that ask “longest run of ones if you may flip at most k zeros”, where tracking positions of zeros rather than a counter becomes the natural tool.

Algorithm.

1. Set best = 0 and lastZero = -1.
2. For every index i: if nums[i] == 0, set lastZero = i; otherwise update best with i - lastZero.
3. Return best.

static int optimalLastZero(int[] nums) {
    int best = 0, lastZero = -1;
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == 0) lastZero = i;
        else best = Math.max(best, i - lastZero);
    }
    return best;
}

Complexity. Time O(n), space O(1), for the same reasons as Approach 2.

Check it on example 2, [1, 0, 1, 1, 0, 1]: at i = 0 we get 0 - (-1) = 1; i = 1 sets lastZero = 1; i = 2 gives 1, i = 3 gives 3 - 1 = 2; i = 4 sets lastZero = 4; i = 5 gives 1. Maximum 2.

Edge cases and pitfalls

• Empty array. All three methods return 0 because the loops never run and best starts at 0.
• No ones at all ([0, 0, 0]). The counter never leaves 0; the answer is 0, not -1 or n.
• The whole array is ones ([1, 1, 1, 1]). The run is never broken, so the answer is n. This is also the worst case for the brute force.
• A run that ends at the last element. Make sure the maximum is updated inside the loop whenever the counter grows, otherwise a trailing run is missed. The code above does this.
• Initialising lastZero to -1. If you initialise it to 0, a run that starts at index 0 is undercounted by one. The sentinel -1 models an imaginary zero just before the array.
• Non-binary input. The counter version treats anything that is not 1 as a run breaker, which matches the problem; if the input could contain other values and you only want to break on 0, write the condition as nums[i] != 0 instead.

Related problems

• Max Consecutive Ones III allows flipping up to k zeros and turns this scan into a sliding window.
• Longest subarray with given sum K(positives) uses the same “extend while valid, shrink when not” sweep on sums instead of a bit flag.
• Kadane’s Algorithm is the same one-pass “carry the current run, drop it when it stops helping” idea applied to sums.