FastPrep
Problem · Array

Longest Prefix-Valid Binary Subarray

Learn this problem
● MediumHackerRank logoHackerRankFULLTIMEOA

Problem statement

You are given a binary array arr containing only 0s and 1s.

A contiguous subarray is prefix-valid when every non-empty prefix of that subarray contains at least as many 1s as 0s.

Return the length of the longest prefix-valid contiguous subarray. If no non-empty prefix-valid subarray exists, return 0.

Function

longestPrefixValidBinarySubarray(arr: int[]) → int

Examples

Example 1

arr = [1,0,1,0,0]return = 4

The subarray [1,0,1,0] is prefix-valid: its prefix balances of 1s minus 0s are 1, 0, 1, 0. Extending it by the final 0 makes the balance negative.

Example 2

arr = [0,1,1,0]return = 3

The longest valid choice starts at index 1: [1,1,0] has prefix balances 1, 2, 1.

Example 3

arr = [0,0,0]return = 0

Every non-empty subarray starts with 0, so its first prefix already has more 0s than 1s.

Constraints

  • 1 <= arr.length <= 100000
  • arr[i] is either 0 or 1

More HackerRank problems

drafts saved locally
public int longestPrefixValidBinarySubarray(int[] arr) {
  // write your code here
}
arr[1,0,1,0,0]
expected4
checking account