#3129

Find All Possible Stable Binary Arrays I

medium · 27.2% accepted · 135 likes · top 5%

dynamic programming · prefix sum

⊣ practice⊣ open on leetcode ↗

Description

You are given 3 positive integers zero, one, and limit.

A binary array arr is called stable if:

- The number of occurrences of 0 in arr is exactly zero.

- The number of occurrences of 1 in arr is exactly one.

- Each subarray of arr with a size greater than limit must contain both 0 and 1.

Return the total number of stable binary arrays.

Since the answer may be very large, return it modulo 109 + 7.

Solution