Find All Possible Stable Binary Arrays II Solution in Python


class Solution:
    def numberOfStableArrays(self, zero: int, one: int, limit: int) -> int:
        kMod = 1_000_000_007
        dp = [[[0] * 2 for _ in range(one + 1)] for _ in range(zero + 1)]

        for i in range(min(zero, limit) + 1):
            dp[i][0][0] = 1

        for j in range(min(one, limit) + 1):
            dp[0][j][1] = 1

        for i in range(1, zero + 1):
            for j in range(1, one + 1):
                dp[i][j][0] = (
                    dp[i - 1][j][0] + dp[i - 1][j][1] -
                    (dp[i - limit - 1][j][1] if i - limit >= 1 else 0) + kMod) % kMod
                dp[i][j][1] = (
                    dp[i][j - 1][0] + dp[i][j - 1][1] -
                    (dp[i][j - limit - 1][0] if j - limit >= 1 else 0) + kMod) % kMod

        return (dp[zero][one][0] + dp[zero][one][1]) % kMod

Problem Description

Welcome to the whimsical world of binary arrays, where 0s and 1s frolic together in a dance of stability! The problem at hand, “Find All Possible Stable Binary Arrays II,” is like trying to organize a party where no two guests (0s and 1s) can be too close to each other. Imagine you have a limited number of 0s and 1s, and you want to arrange them in such a way that no two 1s are within a certain distance of each other. Sounds like a fun party, right?

In real life, this is akin to trying to arrange chairs in a way that no two people who can’t stand each other sit next to each other. You have to be strategic about your placements, or you might end up with a chaotic gathering!

Approach Explanation

The code employs a dynamic programming approach to count the number of stable binary arrays. It uses a 3D list dp where dp[i][j][k] represents the number of stable arrays with i occurrences of 0, j occurrences of 1, and the last number being k (either 0 or 1). The algorithm initializes the base cases and iteratively fills the dp table based on the constraints of the problem, ensuring that the stability condition is met.

Time and Space Complexity

Time Complexity

O(zero * one), where zero is the number of 0s and one is the number of 1s. This is because we iterate through all combinations of 0s and 1s.

Space Complexity

O(zero * one), as we store the results in a 3D list.

Real-World Example

Imagine you’re organizing a seating arrangement for a wedding where you have a limited number of tables (0s) and guests (1s). You want to ensure that no two guests who can’t stand each other sit too close. This problem is akin to finding the right arrangement of guests at the tables while adhering to the distance rule. The solution helps you calculate the number of valid arrangements, ensuring a peaceful celebration!

Explore More Solutions

C++ Solution

Java Solution