# Count the Number of Arrays with K Matching Adjacent Elements
**Difficulty:** HARD
[External](https://leetcode.com/problems/count-the-number-of-arrays-with-k-matching-adjacent-elements)
Canonical: https://scaleengineer.com/dsa/problems/count-the-number-of-arrays-with-k-matching-adjacent-elements
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Combinatorics](https://scaleengineer.com/dsa/patterns/combinatorics)
**Companies:** [PhonePe](https://scaleengineer.com/companies/phonepe)
---
## Problem
You are given three integers `n`, `m`, `k`. A **good array** `arr` of size `n` is defined as follows:

* Each element in `arr` is in the **inclusive** range `[1, m]`.
* _Exactly_ `k` indices `i` (where `1 <= i < n`) satisfy the condition `arr[i - 1] == arr[i]`.

Return the number of **good arrays** that can be formed.

Since the answer may be very large, return it **modulo** `109 + 7`.

**Example 1:**

**Input:** n = 3, m = 2, k = 1

**Output:** 4

**Explanation:**

* There are 4 good arrays. They are `[1, 1, 2]`, `[1, 2, 2]`, `[2, 1, 1]` and `[2, 2, 1]`.
* Hence, the answer is 4.

**Example 2:**

**Input:** n = 4, m = 2, k = 2

**Output:** 6

**Explanation:**

* The good arrays are `[1, 1, 1, 2]`, `[1, 1, 2, 2]`, `[1, 2, 2, 2]`, `[2, 1, 1, 1]`, `[2, 2, 1, 1]` and `[2, 2, 2, 1]`.
* Hence, the answer is 6.

**Example 3:**

**Input:** n = 5, m = 2, k = 0

**Output:** 2

**Explanation:**

* The good arrays are `[1, 2, 1, 2, 1]` and `[2, 1, 2, 1, 2]`. Hence, the answer is 2.

**Constraints:**

* `1 <= n <= 105`
* `1 <= m <= 105`
* `0 <= k <= n - 1`

# Approaches
## Dynamic Programming
This approach builds the solution iteratively using dynamic programming. We define a state `dp[i][j]` as the number of ways to form an array of length `i` with exactly `j` adjacent matches. We then derive a recurrence relation to compute `dp[i][j]` based on smaller subproblems.
**Time:** O(n * k). The outer loop runs `n-1` times, and the inner loop runs `k+1` times. · **Space:** O(k). We use a 1D DP array of size `k+1` and update it in each iteration. Without this space optimization, the complexity would be `O(n * k)`.
**Pros:** Relatively straightforward to come up with from first principles.; Correct for smaller constraints.
**Cons:** The time complexity of `O(n * k)` is too slow for the given constraints, where `n` and `k` can be up to `10^5`. This will lead to a Time Limit Exceeded error.
### Explanation
Let `dp[i][j]` be the number of arrays of length `i` with exactly `j` adjacent matching elements. Our goal is to find `dp[n][k]`.

**Base Case:** For an array of length `i=1`, there are `m` possibilities (any number from 1 to `m`). There are 0 adjacent pairs, so 0 matches. Thus, `dp[1][0] = m`.

**Recurrence Relation:** To compute `dp[i][j]`, we consider adding the `i`-th element to a valid array of length `i-1`.
- To get `j` matches in an array of length `i`, the `(i-1)`-th pair `(arr[i-2], arr[i-1])` can either be a match or not.
- **Case 1: `arr[i-2] == arr[i-1]` (a new match is formed).** This requires that the prefix of length `i-1` had `j-1` matches. For any such array, the value of `arr[i-2]` is some number. To create a match, `arr[i-1]` must be the same number. There is only 1 choice for `arr[i-1]`. The number of ways for this case is `dp[i-1][j-1]`.
- **Case 2: `arr[i-2] != arr[i-1]` (no new match is formed).** This requires that the prefix of length `i-1` already had `j` matches. For any such array, the value of `arr[i-2]` is some number. To avoid a match, `arr[i-1]` can be any of the other `m-1` numbers. The number of ways for this case is `dp[i-1][j] * (m-1)`.

Combining these cases, the recurrence is: `dp[i][j] = (dp[i-1][j-1] + dp[i-1][j] * (m-1)) % MOD`.

We can build a DP table of size `(n+1) x (k+1)` to store these values. Since `dp[i]` only depends on `dp[i-1]`, we can optimize space to `O(k)` by using only two rows (or one, with careful updates).

```java
class Solution {
    public int countGoodArrays(int n, int m, int k) {
        long MOD = 1_000_000_007;
        if (k >= n) {
            return 0;
        }

        // dp[j] will store the number of arrays of current length with j matches
        long[] dp = new long[k + 1];
        
        // Base case: length 1
        dp[0] = m;

        for (int i = 2; i <= n; i++) {
            long[] next_dp = new long[k + 1];
            for (int j = 0; j <= k; j++) {
                // Case 1: arr[i-1] != arr[i-2]
                // We extend an array of length i-1 with j matches
                next_dp[j] = (dp[j] * (m - 1)) % MOD;
                
                // Case 2: arr[i-1] == arr[i-2]
                // We extend an array of length i-1 with j-1 matches
                if (j > 0) {
                    next_dp[j] = (next_dp[j] + dp[j - 1]) % MOD;
                }
            }
            dp = next_dp;
        }

        return (int) dp[k];
    }
}
```
### Algorithm
- Define a 2D DP array `dp[i][j]` to store the number of arrays of length `i` with `j` adjacent matches.
- The base case is for an array of length 1. There are `m` possible arrays (e.g., `[1]`, `[2]`, ..., `[m]`), and all have 0 matches. So, `dp[1][0] = m`.
- To build an array of length `i` with `j` matches, we can extend an array of length `i-1`.
- Consider an array of length `i-1`. We add the `i`-th element.
    - **Case 1: The new element creates a match.** This means we must have had `j-1` matches in the first `i-1` elements. There is only 1 choice for the new element to match the previous one. So, we add `dp[i-1][j-1]` to `dp[i][j]`.
    - **Case 2: The new element does not create a match.** This means we must have had `j` matches in the first `i-1` elements. There are `m-1` choices for the new element to not match the previous one. So, we add `dp[i-1][j] * (m-1)` to `dp[i][j]`.
- The recurrence relation is `dp[i][j] = (dp[i-1][j-1] + dp[i-1][j] * (m-1)) % MOD`.
- The final answer is `dp[n][k]`.
- Space can be optimized to `O(k)` by using only two 1D arrays for the DP states.

## Combinatorial Approach
This problem can be solved more efficiently using a combinatorial argument. The core idea is to count the number of ways to choose positions for matches and then count the number of ways to assign values to the resulting structure of the array.
**Time:** O(n + log(n)). `O(n)` is for precomputing factorials. The rest of the calculations (combinations, power) take logarithmic time with respect to their inputs. The dominant part is the precomputation. · **Space:** O(n). We need to store precomputed factorials and their inverses up to `n`.
**Pros:** Highly efficient and passes for the given large constraints.; Mathematically elegant and concise solution.
**Cons:** Requires knowledge of combinatorics, modular arithmetic (including modular inverse and exponentiation).; The logic might be less intuitive than the DP approach for those not familiar with these mathematical concepts.
### Explanation
An array of length `n` has `n-1` adjacent pairs. We need to choose exactly `k` of these pairs to be equal (`arr[i-1] == arr[i]`) and the other `(n-1) - k` pairs to be different.

The `(n-1) - k` positions where `arr[i-1] != arr[i]` act as separators, dividing the array into blocks of identical elements. The number of such blocks will be `(n-1) - k + 1 = n - k`.
For example, if `n=8, k=4`, and matches are at indices 1, 2, 4, 7, the array structure is `[a, a, a, b, b, c, d, d]`. The non-matches are at indices 3, 5, 6. These 3 non-matches create 4 blocks: `[aaa]`, `[bb]`, `[c]`, `[dd]`.

The problem is now transformed into two parts:
1.  **Choose the positions of the `k` matches:** There are `n-1` possible positions for a match. We need to choose `k` of them. The number of ways to do this is given by the binomial coefficient "n-1 choose k", or `C(n-1, k)`.
2.  **Assign values to the `n-k` blocks:** We have `n-k` blocks, and the values of adjacent blocks must be different.
    - The first block can be assigned any of the `m` values.
    - The second block must have a value different from the first, so it has `m-1` choices.
    - This continues for all `n-k` blocks. The number of ways to assign values is `m * (m-1)^(n-k-1)`.

The total number of good arrays is the product of these two parts: `C(n-1, k) * m * (m-1)^(n-k-1)`.

To compute this value modulo `10^9 + 7` (a prime number), we need:
- A function for modular exponentiation to calculate `(m-1)^(n-k-1)`.
- A way to calculate `C(N, K) % MOD`. This is `N! / (K! * (N-K)!)`. We can precompute factorials up to `n-1` and use modular inverse for division. The modular inverse of `a` is `a^(MOD-2) % MOD` by Fermat's Little Theorem.

```java
class Solution {
    long MOD = 1_000_000_007;
    long[] fact;
    long[] invFact;

    public int countGoodArrays(int n, int m, int k) {
        if (k >= n) {
            return 0;
        }
        
        // Precompute factorials and their modular inverses
        precomputeFactorials(n);

        // Calculate C(n-1, k)
        long combinations = nCr_precomputed(n - 1, k);

        // Calculate m * (m-1)^(n-k-1)
        long valAssignments = (m * power(m - 1, n - k - 1)) % MOD;

        // Final result
        long ans = (combinations * valAssignments) % MOD;
        return (int) ans;
    }

    private long power(long base, long exp) {
        long res = 1;
        base %= MOD;
        while (exp > 0) {
            if (exp % 2 == 1) res = (res * base) % MOD;
            base = (base * base) % MOD;
            exp /= 2;
        }
        return res;
    }

    private long modInverse(long n) {
        return power(n, MOD - 2);
    }

    private void precomputeFactorials(int maxN) {
        fact = new long[maxN + 1];
        invFact = new long[maxN + 1];
        fact[0] = 1;
        invFact[0] = 1;
        for (int i = 1; i <= maxN; i++) {
            fact[i] = (fact[i - 1] * i) % MOD;
            invFact[i] = modInverse(fact[i]);
        }
    }

    private long nCr_precomputed(int n, int r) {
        if (r < 0 || r > n) {
            return 0;
        }
        return (((fact[n] * invFact[r]) % MOD) * invFact[n - r]) % MOD;
    }
}
```
### Algorithm
- Re-frame the problem combinatorially. An array of length `n` has `n-1` adjacent pairs.
- We need to choose `k` positions for matches (`arr[i-1] == arr[i]`) and `(n-1)-k` for non-matches (`arr[i-1] != arr[i]`).
- The `(n-1)-k` non-matches act as separators, dividing the array into `(n-1)-k+1 = n-k` blocks of identical elements.
- The problem breaks down into two independent subproblems:
  1. **Choose positions for matches:** The number of ways to choose `k` match positions out of `n-1` is `C(n-1, k)`.
  2. **Assign values to blocks:** We have `n-k` blocks. Adjacent blocks must have different values. The first block has `m` choices, and each subsequent block has `m-1` choices. This gives `m * (m-1)^(n-k-1)` ways.
- The total number of good arrays is the product: `C(n-1, k) * m * (m-1)^(n-k-1)`.
- To compute this modulo `10^9 + 7`, we need modular exponentiation for powers and modular inverse for combinations.
- Precompute factorials up to `n-1` to calculate `C(n-1, k)` efficiently.

# Solutions
### Java

```java
class Solution {
private
  static final int N = (int)1 e5 + 10;
private
  static final int MOD = (int)1 e9 + 7;
private
  static final long[] f = new long[N];
private
  static final long[] g = new long[N];
  static {
    f[0] = 1;
    g[0] = 1;
    for (int i = 1; i < N; ++i) {
      f[i] = f[i - 1] * i % MOD;
      g[i] = qpow(f[i], MOD - 2);
    }
  }
public
  static long qpow(long a, int k) {
    long res = 1;
    while (k != 0) {
      if ((k & 1) == 1) {
        res = res * a % MOD;
      }
      k >>= 1;
      a = a * a % MOD;
    }
    return res;
  }
public
  static long comb(int m, int n) {
    return (int)f[m] * g[n] % MOD * g[m - n] % MOD;
  }
public
  int countGoodArrays(int n, int m, int k) {
    return (int)(comb(n - 1, k) * m % MOD * qpow(m - 1, n - k - 1) % MOD);
  }
}

```

### CPP

```cpp
const int MX = 1e5 + 10 ; const int MOD = 1e9 + 7 ; long long f [ MX ]; long long g [ MX ]; long long qpow ( long a , int k ) { long res = 1 ; while ( k != 0 ) { if (( k & 1 ) == 1 ) { res = res * a % MOD ; } k >>= 1 ; a = a * a % MOD ; } return res ; } int init = []() { f [ 0 ] = g [ 0 ] = 1 ; for ( int i = 1 ; i < MX ; ++ i ) { f [ i ] = f [ i - 1 ] * i % MOD ; g [ i ] = qpow ( f [ i ], MOD - 2 ); } return 0 ; }(); long long comb ( int m , int n ) { return f [ m ] * g [ n ] % MOD * g [ m - n ] % MOD ; } class Solution { public: int countGoodArrays ( int n , int m , int k ) { return comb ( n - 1 , k ) * m % MOD * qpow ( m - 1 , n - k - 1 ) % MOD ; } };
```

### Python

```python
mx = 10 ** 5 + 10 mod = 10 ** 9 + 7 f = [ 1 ] + [ 0 ] * mx g = [ 1 ] + [ 0 ] * mx for i in range ( 1 , mx ): f [ i ] = f [ i - 1 ] * i % mod g [ i ] = pow ( f [ i ], mod - 2 , mod ) def comb ( m : int , n : int ) -> int : return f [ m ] * g [ n ] * g [ m - n ] % mod class Solution : def countGoodArrays ( self , n : int , m : int , k : int ) -> int : return comb ( n - 1 , k ) * m * pow ( m - 1 , n - k - 1 , mod ) % mod
```