MediumDpAI interview only
Find All Possible Stable Binary Arrays I
Asked atgoogleamazon
01 · Problem
You are given three positive integers zero, one, and limit. A binary array arr is stable when:
arrcontains exactlyzerooccurrences of0.arrcontains exactlyoneoccurrences of1.- No block of consecutive equal values in
arris longer thanlimit(equivalently, every subarray longer thanlimitcontains both a0and a1).
Return the number of stable binary arrays. Since the count can be large, return it modulo 10^9 + 7.
02 · Examples
Example 01
Input
zero = 1, one = 1, limit = 2
Output
2
The only arrays with one 0 and one 1 are [0,1] and [1,0]; both have runs of length 1, so both are stable.
Example 02
Input
zero = 2, one = 2, limit = 1
Output
2
No two equal values may be adjacent, so only the alternating arrays [0,1,0,1] and [1,0,1,0] qualify.
Example 03
Input
zero = 3, one = 2, limit = 2
Output
7
There are 10 arrays with three 0s and two 1s. The three that contain a run of three 0s ([0,0,0,1,1], [1,0,0,0,1], [1,1,0,0,0]) are not stable, leaving 7.
03 · Constraints
- 011 <= zero <= 200
- 021 <= one <= 200
- 031 <= limit <= 200
- 04Return the answer modulo 109 + 7
04 · Optimal complexity
- Time
- O(zero * one)
- Space
- O(zero * one)
05 · Two ways to work on it
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.