Skip to main content
Talentd

Find All Possible Stable Binary Arrays I - Solution & Explanation

MediumDynamic ProgrammingPrefix Sum29 min readAsked at: Amazon, Meta, Google
Practice this problem

Problem Statement

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.

 

Example 1:

Input: zero = 1, one = 1, limit = 2

Output: 2

Explanation:

The two possible stable binary arrays are [1,0] and [0,1], as both arrays have a single 0 and a single 1, and no subarray has a length greater than 2.

Example 2:

Input: zero = 1, one = 2, limit = 1

Output: 1

Explanation:

The only possible stable binary array is [1,0,1].

Note that the binary arrays [1,1,0] and [0,1,1] have subarrays of length 2 with identical elements, hence, they are not stable.

Example 3:

Input: zero = 3, one = 3, limit = 2

Output: 14

Explanation:

All the possible stable binary arrays are [0,0,1,0,1,1], [0,0,1,1,0,1], [0,1,0,0,1,1], [0,1,0,1,0,1], [0,1,0,1,1,0], [0,1,1,0,0,1], [0,1,1,0,1,0], [1,0,0,1,0,1], [1,0,0,1,1,0], [1,0,1,0,0,1], [1,0,1,0,1,0], [1,0,1,1,0,0], [1,1,0,0,1,0], and [1,1,0,1,0,0].

 

Constraints:

  • 1 <= zero, one, limit <= 200

Approach Overview

Problem Overview: You are given the number of 0s and 1s that must appear in a binary array and a limit restricting how many identical values can appear consecutively. The task is to count how many distinct arrays can be formed such that no more than limit consecutive 0s or 1s appear.

Approach 1: Combinatorics with Group Placement (Time: O(zero + one), Space: O(zero + one))

This approach models the array as alternating groups of 0s and 1s. Instead of building the array element by element, you count how many ways the required zeros and ones can be split into valid groups where each group length is ≤ limit. Using combinatorics (stars and bars with upper bounds), you compute the number of ways to distribute elements across groups while respecting the maximum run constraint. Inclusion–exclusion removes arrangements where a group exceeds the limit. This method works well when you precompute factorials and combinations modulo a constant. See related ideas in combinatorics.

Approach 2: Dynamic Programming with Prefix Sum Optimization (Time: O(zero × one), Space: O(zero × one))

The more direct method uses dynamic programming. Let dp0[i][j] be the number of valid arrays using i zeros and j ones that end with 0. Similarly, dp1[i][j] ends with 1. When placing a 0, the previous run must end with 1, and you can append between 1 and limit zeros as long as enough zeros remain. The same idea applies symmetrically for ones. Direct transitions would require iterating over all run lengths, which is expensive. Using prefix sums, you compute the sum of valid previous states in constant time, reducing the transition cost significantly.

The DP table iterates over all pairs (i, j). For each state, prefix sums allow you to subtract invalid ranges where the run length exceeds limit. This guarantees that no segment of identical values becomes longer than allowed while still counting every valid construction.

Recommended for interviews: The dynamic programming approach with prefix sums is the expected solution. It clearly models the constraint on consecutive elements and runs in O(zero × one) time, which fits typical constraints. The combinatorics approach is elegant and faster asymptotically but requires deeper mathematical reasoning and careful implementation of bounded distributions.

Approach 1: Using Combinatorics

This approach leverages combinatorial methods to generate all possible binary arrays and filters them based on the conditions using permutations.

  • First, consider the total length of the binary array as `zero + one`.
  • Next, generate all permutations of these positions and count only those satisfying the stability condition.
  • For handling larger arrays, remember to use modular arithmetic when calculating combinations or factorials.

The function calculates all possible permutations using the nCr method (which calculates combinations). We iterate over possible starting positions for either 0 or 1, ensuring we maintain stability in subarrays of size greater than limit. The permutations are then summed to get the result.

Code

PythonC

Python

C

Complexity

Time Complexity: O(n!) due to the permutations, where n = zero + one.
Space Complexity: O(1) for the constant space used by the calculation (since we're not storing arrays).

Try this approach in the editor →

Approach 2: Dynamic Programming Approach

This method employs dynamic programming to solve the problem by building a solution that considers smaller subproblems of the main problem.

  • Define a DP table where dp[i][j] represents the number of ways to construct a stable array with `i` zeros and `j` ones.
  • Iterate over the table while respecting the stability condition for subarrays.
  • Base cases are initialized to reflect the constraints, and we return the final value from the DP table.

Utilizing dynamic programming here allows us to solve the problem efficiently by building up from smaller cases. Each case in the DP table dp[i][j] is built using the previous results while ensuring subarray constraints are respected by subtracting overlapping cases.

Code

JavaJavaScript

Java

JavaScript

Complexity

Time Complexity: O(zero * one) due to filling the DP table.
Space Complexity: O(zero * one) for storing the intermediate results in the DP table.

Try this approach in the editor →

Approach 3: Memoized Search

We define a function dfs(i, j, k) to represent the number of stable binary arrays that satisfy the problem conditions when there are i zeros and j ones remaining to place, and the next digit to fill is k. Then the answer is dfs(zero, one, 0) + dfs(zero, one, 1).

The computation process of dfs(i, j, k) is as follows:

  • If i \lt 0 or j \lt 0, return 0.
  • If i = 0, then return 1 when k = 1 and j leq limit; otherwise return 0.
  • If j = 0, then return 1 when k = 0 and i leq limit; otherwise return 0.
  • If k = 0, we consider the case where the previous digit is 0, i.e., dfs(i - 1, j, 0), and the case where the previous digit is 1, i.e., dfs(i - 1, j, 1). If the previous digit is 0, there may be more than limit zeros in a subarray, which means the case where the (limit + 1)-th digit from the end is 1 is invalid, so we subtract this case: dfs(i - limit - 1, j, 1).
  • If k = 1, we consider the case where the previous digit is 0, i.e., dfs(i, j - 1, 0), and the case where the previous digit is 1, i.e., dfs(i, j - 1, 1). If the previous digit is 1, there may be more than limit ones in a subarray, which means the case where the (limit + 1)-th digit from the end is 0 is invalid, so we subtract this case: dfs(i, j - limit - 1, 0).

To avoid repeated computation, we use memoized search.

The time complexity is O(zero times one), and the space complexity is O(zero times one).

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Approach 4: Dynamic Programming

We can also convert the memoized search in Solution 1 into dynamic programming.

We define f[i][j][k] as the number of stable binary arrays that use i zeros and j ones, with the last digit being k. Then the answer is f[zero][one][0] + f[zero][one][1].

Initially, we have f[i][0][0] = 1, where 1 leq i leq min(limit, zero); and f[0][j][1] = 1, where 1 leq j leq min(limit, one).

The state transition equations are as follows:

  • f[i][j][0] = f[i - 1][j][0] + f[i - 1][j][1] - f[i - limit - 1][j][1].
  • f[i][j][1] = f[i][j - 1][0] + f[i][j - 1][1] - f[i][j - limit - 1][0].

The time complexity is O(zero times one), and the space complexity is O(zero times one).

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Using Combinatorics

Time Complexity: O(n!) due to the permutations, where n = zero + one.
Space Complexity: O(1) for the constant space used by the calculation (since we're not storing arrays).

Dynamic Programming Approach

Time Complexity: O(zero * one) due to filling the DP table.
Space Complexity: O(zero * one) for storing the intermediate results in the DP table.

Memoized Search—
Dynamic Programming—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Combinatorics with Group PlacementO(zero + one)O(zero + one)When you want a math-driven counting approach and have combination precomputation available
Dynamic Programming with Prefix SumsO(zero × one)O(zero × one)General case and most common interview solution

Video Solution

Find All Possible Stable Binary Arrays I | 2 Approaches | Detailed Intuition | Leetcode 3129 | MIK • codestorywithMIK • 18,214 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Find All Possible Stable Binary Arrays I easy or hard?
Find All Possible Stable Binary Arrays I is rated Medium difficulty. The challenge comes from designing the correct DP state and efficiently enforcing the limit on consecutive elements. Once the prefix sum optimization is understood, the implementation becomes straightforward.
Find All Possible Stable Binary Arrays I Python/Java solution
Python implementations usually use dynamic programming with prefix sums and modular arithmetic for counting. Java versions follow the same DP structure with two tables tracking arrays ending in 0 or 1. Both implementations achieve O(zero × one) time complexity.
How to solve Find All Possible Stable Binary Arrays I in O(n)?
A near-linear approach can be derived using combinatorics by counting valid ways to split zeros and ones into groups whose lengths do not exceed the limit. Using combinations with inclusion–exclusion removes configurations where a group exceeds the maximum size. With precomputed factorials, the counting can be done in roughly O(zero + one).
What is the best approach for Find All Possible Stable Binary Arrays I?
Dynamic programming with prefix sum optimization is the most practical approach. It tracks arrays ending in 0 or 1 using states like dp0[i][j] and dp1[i][j], ensuring no more than limit consecutive elements are added. The method runs in O(zero × one) time and cleanly handles the consecutive constraint.
Is Find All Possible Stable Binary Arrays I asked at Google/Amazon/Meta?
Problems involving constrained binary sequences and dynamic programming patterns frequently appear in interviews at companies like Amazon, Google, and Meta. The key skills tested are DP state design, prefix sum optimization, and counting valid configurations under constraints.
What data structure is used in Find All Possible Stable Binary Arrays I?
The main structure is a 2D dynamic programming table that tracks counts of arrays ending with 0 or 1. Prefix sum arrays are used to speed up range-sum transitions when adding multiple consecutive elements. This combination keeps the algorithm efficient.
What is the time complexity of Find All Possible Stable Binary Arrays I?
The standard dynamic programming solution runs in O(zero × one) time because every pair of zero and one counts is processed once. Prefix sums allow each transition to be computed in constant time. Space complexity is also O(zero × one) for the DP table.

Ready to solve this problem?

Practice Find All Possible Stable Binary Arrays I with our built-in code editor and test cases.

Practice on FleetCode
Previous

Binary Subarrays With Sum

Next

Contiguous Array