Created
March 10, 2026 21:46
-
-
Save tatsuyax25/10c6a5878eee6e63ee6dc8875998d84e to your computer and use it in GitHub Desktop.
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 th
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * @param {number} zero | |
| * @param {number} one | |
| * @param {number} limit | |
| * @return {number} | |
| */ | |
| var numberOfStableArrays = function(zero, one, limit) { | |
| const MOD = 1_000_000_007; | |
| // dp0[x][y] = ways using x zeros, y ones, ending with 0 | |
| // dp1[x][y] = ways using x zeros, y ones, ending with 1 | |
| const dp0 = Array.from({ length: zero + 1 }, () => | |
| Array(one + 1).fill(0) | |
| ); | |
| const dp1 = Array.from({ length: zero + 1 }, () => | |
| Array(one + 1).fill(0) | |
| ); | |
| // Prefix sums: | |
| // pref1[x][y] = sum_{i=0..x} dp1[i][y] (prefix over x) | |
| // pref0[x][y] = sum_{j=0..y} dp0[x][j] (prefix over y) | |
| const pref1 = Array.from({ length: zero + 1 }, () => | |
| Array(one + 1).fill(0) | |
| ); | |
| const pref0 = Array.from({ length: zero + 1 }, () => | |
| Array(one + 1).fill(0) | |
| ); | |
| // ------------------------- | |
| // Base cases: pure runs of only zeros or only ones | |
| // ------------------------- | |
| // Only zeros: [0,0,...,0] of length x is valid iff x <= limit | |
| for (let x = 1; x <= zero; x++) { | |
| if (x <= limit) dp0[x][0] = 1; | |
| else dp0[x][0] = 0; | |
| } | |
| // Only ones: [1,1,...,1] of length y is valid iff y <= limit | |
| for (let y = 1; y <= one; y++) { | |
| if (y <= limit) dp1[0][y] = 1; | |
| else dp1[0][y] = 0; | |
| } | |
| // Initialize prefix sums for row/column where one of the counts is zero | |
| for (let x = 0; x <= zero; x++) { | |
| for (let y = 0; y <= one; y++) { | |
| // pref1: prefix over x for dp1 | |
| pref1[x][y] = dp1[x][y]; | |
| if (x > 0) { | |
| pref1[x][y] = (pref1[x][y] + pref1[x - 1][y]) % MOD; | |
| } | |
| // pref0: prefix over y for dp0 | |
| pref0[x][y] = dp0[x][y]; | |
| if (y > 0) { | |
| pref0[x][y] = (pref0[x][y] + pref0[x][y - 1]) % MOD; | |
| } | |
| } | |
| } | |
| // ------------------------- | |
| // Main DP: build for x >= 1 and y >= 1 | |
| // We iterate x outer, y inner: | |
| // - dp0[x][y] uses dp1[<x][y] (same y, smaller x) | |
| // - dp1[x][y] uses dp0[x][<y] (same x, smaller y) | |
| // ------------------------- | |
| for (let x = 1; x <= zero; x++) { | |
| for (let y = 1; y <= one; y++) { | |
| // Skip pure-zero and pure-one base cases we already handled | |
| // (they are when y == 0 or x == 0, so here we are safe) | |
| // ---- dp0[x][y]: end with 0 ---- | |
| // sum dp1[x-k][y] for k = 1..limit, i.e. x-limit .. x-1 | |
| { | |
| const left = x - 1; | |
| const right = x - limit - 1; // inclusive | |
| let sum = pref1[left][y]; // sum dp1[0..left][y] | |
| if (right >= 0) { | |
| // subtract dp1[0..right][y] to keep only (right+1..left) | |
| sum = (sum - pref1[right][y] + MOD) % MOD; | |
| } | |
| dp0[x][y] = (dp0[x][y] + sum) % MOD; | |
| } | |
| // ---- dp1[x][y]: end with 1 ---- | |
| // sum dp0[x][y-k] for k = 1..limit, i.e. y-limit .. y-1 | |
| { | |
| const left = y - 1; | |
| const right = y - limit - 1; // inclusive | |
| let sum = pref0[x][left]; // sum dp0[x][0..left] | |
| if (right >= 0) { | |
| // subtract dp0[x][0..right] to keep only (right+1..left) | |
| sum = (sum - pref0[x][right] + MOD) % MOD; | |
| } | |
| dp1[x][y] = (dp1[x][y] + sum) % MOD; | |
| } | |
| // Update prefix sums at (x, y) after dp0[x][y], dp1[x][y] are final | |
| pref1[x][y] = dp1[x][y]; | |
| if (x > 0) { | |
| pref1[x][y] = (pref1[x][y] + pref1[x - 1][y]) % MOD; | |
| } | |
| pref0[x][y] = dp0[x][y]; | |
| if (y > 0) { | |
| pref0[x][y] = (pref0[x][y] + pref0[x][y - 1]) % MOD; | |
| } | |
| } | |
| } | |
| // Final answer: arrays ending with 0 or 1 | |
| return (dp0[zero][one] + dp1[zero][one]) % MOD; | |
| }; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment