[Leetcode] 3405. Count the Number of Arrays with K Matching Adjacent Elements

https://leetcode.com/problems/count-the-number-of-arrays-with-k-matching-adjacent-elements/?envType=daily-question&envId=2025-06-17

initial

wow i didnt even get a clue how to start. We can do it comb maths way

So k= number of matches within a [] of size n. We have n-1 possible transitions (i.e. from arr[0] vs arr[1] up to arr[n-2] vs arr[n-1]). We need to have k matching transitions so the non-matchign transitions are n-1-k.

1) number of ways to choose these k positions out of n-1 transitions are (n-1)Ck.
2) If you choose k positions to be matches, it automatically implies that the remaining (n-1) - k positions will be non-matches.

Then we assign the values. arr[0] has m choices.
For the k positions that need to match with arr[0]'s value, each of them just has 1 choice which is that arr[0]'s value so 1^k.

But for the n-1-k positions, the values have to be different from arr[0]'s value. So they have m-1 choices so (m-1)^(n-1-k) ways to arrange them.

So finally
Total number of good arrays = (Ways to choose match positions) × (Choices for first element) × (Choices for matches) × (Choices for non-matches)

ans = (n-1)Ck m 1^k * (m-1)^(n-1-k)

Example (n=4, m=3, k=1):

C(3, 1) = 3
m = 3
(m-1)^((n-1)-k) = (3-1)^((4-1)-1) = 2^(3-1) = 2^2 = 4
Total = 3 (ways to pick pattern) 3 (choices for arr[0]) 4 (choices for rest given pattern and arr[0])
Total = 3 3 4 = 36

sol

class Solution:
    def countGoodArrays(self, n: int, m: int, k: int) -> int:
        mod = 10**9+7
        return comb(n-1,k)*m*pow(m-1,n-k-1,mod)

        

complexity

the time complexity calculation is hard

so if we recall math comb, it is basically doing constant time maths operations like 7x6x5/3x2x1 like this just multiplying and not calculating actual factorials like 5!. This way, the formula of nCk is n!/k! x (n-k)!.

We know that C(n,k)=C(n,n−k).
So, C(7,3) is the same as C(7,7−3)=C(7,4).

If k is small, say k=3, the loop runs 3 times. O(3)
If k is large, say k=4, the loop would run 4 times. O(4)

math.comb (and good implementations) will automatically choose the smaller of k and n-k to minimize the number of iterations.
For C(7,4), it would internally calculate it as C(7,3) because 3<4. So it effectively runs 3 iterations, not 4.

Therefore, the number of operations is proportional to the smaller of k and n-k.

Time Complexity of math.comb(n, k): O(min(k,n−k))

then we have this power. pow(m - 1, n - k - 1, mod):
This is modular exponentiation (also known as binary exponentiation).
It calculates base^exponent % modulus very efficiently.
The time complexity is O(log(exponent)). Here, the exponent is n - k - 1.
So, this part is O(log(n−k−1)), which is roughly O(logn).

space is 1