Scale Engineer

Max Consecutive Ones

Easy
#0472Time: O(n^2), where n is the length of the input array. In the worst-case scenario, such as an array filled with all ones, the inner loop runs up to n times for each of the n elements, resulting in quadratic time complexity.Space: O(1), as we only use a constant amount of extra space for counter variables, regardless of the input array size.3 companies
Data structures
Array
Companies
AccentureDeloitteYandex

Prompt

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 <= 105
  • nums[i] is either 0 or 1.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses nested loops to check for consecutive ones starting from every possible position in the array. It is straightforward but inefficient.

Algorithm

  • Initialize maxCount = 0.
  • Iterate through the array with an outer loop using index i from 0 to n-1.
  • For each i, initialize a currentCount = 0.
  • Start a nested loop with index j from i to n-1.
  • If nums[j] is 1, increment currentCount.
  • If nums[j] is 0, break the inner loop because the sequence of ones is broken.
  • After the inner loop completes, update maxCount = Math.max(maxCount, currentCount).
  • After the outer loop finishes, maxCount holds the maximum length found.

Walkthrough

The brute-force method involves iterating through each element of the array with an outer loop. For each element, we consider it as a potential starting point of a sequence of ones. Then, a nested inner loop starts from this point and counts how many consecutive ones follow until a zero or the end of the array is encountered.

A variable maxCount keeps track of the maximum length found so far. After each inner loop finishes counting a sequence, the count is compared with maxCount, and maxCount is updated if the new count is larger. This process is repeated for all possible starting positions.

Here is the Java implementation:

class Solution {    public int findMaxConsecutiveOnes(int[] nums) {        int maxCount = 0;        for (int i = 0; i < nums.length; i++) {            int currentCount = 0;            for (int j = i; j < nums.length; j++) {                if (nums[j] == 1) {                    currentCount++;                } else {                    // End of the current sequence of ones                    break;                }            }            if (currentCount > maxCount) {                maxCount = currentCount;            }        }        return maxCount;    }}

Complexity

Time

O(n^2), where n is the length of the input array. In the worst-case scenario, such as an array filled with all ones, the inner loop runs up to n times for each of the n elements, resulting in quadratic time complexity.

Space

O(1), as we only use a constant amount of extra space for counter variables, regardless of the input array size.

Trade-offs

Pros

  • Simple logic that is easy to understand and implement.

Cons

  • Highly inefficient for large inputs due to the O(n^2) time complexity.

  • Performs redundant work by re-scanning parts of the array multiple times.

Solutions

class Solution {public  int findMaxConsecutiveOnes(int[] nums) {    int cnt = 0, ans = 0;    for (int v : nums) {      if (v == 1) {        ++cnt;      } else {        ans = Math.max(ans, cnt);        cnt = 0;      }    }    return Math.max(cnt, ans);  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem