Show problems as
Classic problem #525MediumArrayHash TablePrefix Sum

Contiguous Array

Real-world version: Balanced Shift Stretch
Tracked in this browser only
Read Contiguous Array on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A press logs one entry per hour for a whole run: states[i] is 1 when the press was cutting during hour i and 0 when it sat idle.

Maintenance wants the longest block of consecutive hours in which the press spent exactly as many hours cutting as it spent idle. Return the number of hours in that block.

Return 0 when no such block exists. The log can hold up to 10^5 hours, so checking every block separately is too slow.

Examples

Example 1

Input
states = [1, 1, 0, 1, 0]
Output
4

Hours 1 through 4 hold two cutting hours and two idle hours. Adding hour 0 would tip the count to three cutting hours, so 4 is the longest.

Example 2

Input
states = [1, 1, 1, 1]
Output
0

The press never idled, so no block can be balanced and the answer is the sentinel 0.

Example 3

Input
states = [0, 1, 0, 0, 1, 1]
Output
6

Across the whole log there are three idle hours and three cutting hours, so the entire run is balanced.

Constraints

  • 1 <= states.length <= 10^5
  • states[i] is either 0 or 1

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def longest_balanced_stretch(states: list[int]) -> int:
Java
public int longestBalancedStretch(int[] states)

More on the same topics