Katkat
Back

Find the Longest Consecutive Run of Ones

MolocoadsMachine Learning Engineer · Onsite
MediumMachine Learning EngineerOnsiteCoding & Algorithms

Last updated

Implement an algorithm to find the maximum length of contiguous ones in a binary array without any bit flips, returning 0 for an empty input.

Problem Statement

Given an array nums consisting only of binary integers (0 and 1), find the length of the longest contiguous sequence of 1s.

No bit flips are permitted. If the array is empty or contains no 1s, the function must return 0.

Function Signature

def find_longest_run_of_ones(nums: list[int]) -> int:
    pass

Input and Output Format

  • Input: A list of integers nums, where each element is either 0 or 1.
  • Output: An integer representing the length of the longest consecutive sequence of 1s.

Constraints

  • 0 <= len(nums) <= 10^7
  • nums[i] in {0, 1} for all 0 <= i < len(nums)
  • Expected time complexity: O(n)
  • Expected auxiliary space complexity: O(1)

Examples

Example 1

Input: nums = [1, 1, 0, 1, 1, 1]
Output: 3
Explanation: The first run of ones has length 2. The second run of ones has length 3. The maximum length is 3.

Example 2

Input: nums = [0, 0, 0]
Output: 0
Explanation: There are no ones in the array, so the result is 0.

Example 3

Input: nums = []
Output: 0
Explanation: The input is empty, returning 0.

Edge Cases to Consider

  • Empty list ([] should return 0).
  • Arrays containing only 0s or only 1s.
  • Runs of 1s located at the very start or the very end of the array.

Hints

Hint 1

Iterate through the array while maintaining two scalar variables: one for the current consecutive run of ones and one for the global maximum found so far.

Hint 2

Reset your current count whenever you encounter a 0, but make sure to update the global maximum whenever the current count exceeds it.

Hint 3

Ensure that an array ending in a run of ones correctly updates the global maximum without needing an extra branch after the loop.

Follow-up questions

  • If the array is distributed across multiple machines in contiguous chunks (e.g., in a MapReduce or Spark framework), what intermediate tuple should each worker emit to compute the global maximum run?
  • How would you adapt the solution for a continuous streaming input where bits arrive one at a time and you need to query the all-time maximum or the maximum in a sliding window?
  • How does the time and space complexity change if you are allowed to flip at most `k` zeros into ones?