🔢 Count the Number of Arrays with K Matching Adjacent Elements LeetCode 3405 (C++ | Python | JavaScript)

#programming #cpp #javascript #python

LeetCode 3405 | Hard | Combinatorics

🧠 Problem Summary

You are given three integers:

n: length of the array
m: range of values [1, m]
k: number of adjacent equal pairs

You must find the total number of "good arrays", where:

Every element lies in the range [1, m]
Exactly k indices i (where 1 ≤ i < n) satisfy arr[i - 1] == arr[i]

Since the result may be large, return the count modulo 10⁹ + 7.

🧩 Intuition

To construct a valid array:

Pick k positions (from the n - 1 possible adjacent pairs) to be equal.
The first element can be any value from 1 to m.
For each of the n - 1 - k remaining positions (which must differ from the previous element), there are m - 1 options.

So, the total number of such arrays is:

C(n - 1, k) × m × (m - 1)^(n - 1 - k)

Where:

C(n - 1, k) is the number of ways to choose k adjacent positions to be equal.
The rest of the positions must be different, hence m - 1 choices per differing element.
Modular inverse and exponentiation are required for large constraints.

🧮 C++ Code (with explanation)

const int MOD = 1e9 + 7;
const int MX = 1e5 + 1;

long long fact[MX], inv_fact[MX];

class Solution {
    long long qpow(long long x, int n) {
        long long res = 1;
        while (n) {
            if (n & 1) res = res * x % MOD;
            x = x * x % MOD;
            n >>= 1;
        }
        return res;
    }

    long long comb(int n, int r) {
        return fact[n] * inv_fact[r] % MOD * inv_fact[n - r] % MOD;
    }

    void init() {
        if (fact[0]) return;  // Already initialized
        fact[0] = 1;
        for (int i = 1; i < MX; ++i)
            fact[i] = fact[i - 1] * i % MOD;
        inv_fact[MX - 1] = qpow(fact[MX - 1], MOD - 2);
        for (int i = MX - 1; i > 0; --i)
            inv_fact[i - 1] = inv_fact[i] * i % MOD;
    }

public:
    int countGoodArrays(int n, int m, int k) {
        init();
        return comb(n - 1, k) * m % MOD * qpow(m - 1, n - 1 - k) % MOD;
    }
};

📝 Key Notes:

init() precomputes factorials and inverse factorials.
qpow() handles fast exponentiation under modulo.
Time complexity: O(n) for precomputation, O(1) per query.

💻 JavaScript Code

const MOD = 1e9 + 7;
const MAX = 1e5 + 1;

const fact = new Array(MAX).fill(1);
const invFact = new Array(MAX).fill(1);

function modPow(x, n) {
    let res = 1;
    while (n) {
        if (n & 1) res = res * x % MOD;
        x = x * x % MOD;
        n >>= 1;
    }
    return res;
}

function init() {
    for (let i = 1; i < MAX; ++i)
        fact[i] = fact[i - 1] * i % MOD;
    invFact[MAX - 1] = modPow(fact[MAX - 1], MOD - 2);
    for (let i = MAX - 2; i >= 0; --i)
        invFact[i] = invFact[i + 1] * (i + 1) % MOD;
}

function comb(n, k) {
    return fact[n] * invFact[k] % MOD * invFact[n - k] % MOD;
}

var countGoodArrays = function(n, m, k) {
    init();
    return comb(n - 1, k) * m % MOD * modPow(m - 1, n - 1 - k) % MOD;
};

🐍 Python Code

MOD = 10**9 + 7
MAX = 10**5 + 1

fact = [1] * MAX
inv_fact = [1] * MAX

def modinv(x):
    return pow(x, MOD - 2, MOD)

def init():
    for i in range(1, MAX):
        fact[i] = fact[i - 1] * i % MOD
    inv_fact[MAX - 1] = modinv(fact[MAX - 1])
    for i in range(MAX - 2, -1, -1):
        inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD

def comb(n, k):
    if k < 0 or k > n:
        return 0
    return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD

class Solution:
    def countGoodArrays(self, n: int, m: int, k: int) -> int:
        init()
        return comb(n - 1, k) * m % MOD * pow(m - 1, n - 1 - k, MOD) % MOD

🧠 Final Thoughts

This problem is a clean example of applying:

Modular combinatorics
Fast exponentiation
Factorial precomputation with inverse modulo

Once broken down properly, the problem becomes more about mathematical insight than raw implementation. It’s an excellent template for any combinatorics-based question with constraints up to 10⁵.

Drop a ❤️ if this helped, and stay tuned for more bitesize breakdowns!

Happy coding, folks! 🚀