3405. Count the Number of Arrays with K Matching Adjacent Elements LeetCode Solution

In this guide, you will get 3405. Count the Number of Arrays with K Matching Adjacent Elements LeetCode Solution with the best time and space complexity. The solution to Count the Number of Arrays with K Matching Adjacent Elements problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Count the Number of Arrays with K Matching Adjacent Elements solution in C++
4. Count the Number of Arrays with K Matching Adjacent Elements solution in Java
5. Count the Number of Arrays with K Matching Adjacent Elements solution in Python
6. Additional Resources

Problem Statement of Count the Number of Arrays with K Matching Adjacent Elements

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

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(n)

3405. Count the Number of Arrays with K Matching Adjacent Elements LeetCode Solution in C++

class Solution {
 public:
  int countGoodArrays(int n, int m, int k) {
    const auto [fact, invFact] = getFactAndInvFact(n);
    return m * modPow(m - 1, n - k - 1) % kMod * nCk(n - 1, k, fact, invFact) %
           kMod;
  }

 private:
  static constexpr int kMod = 1'000'000'007;

  long modPow(long x, long n) {
    if (n == 0)
      return 1;
    if (n % 2 == 1)
      return x * modPow(x % kMod, (n - 1)) % kMod;
    return modPow(x * x % kMod, (n / 2)) % kMod;
  }

  pair<vector<long>, vector<long>> getFactAndInvFact(int n) {
    vector<long> fact(n + 1);
    vector<long> invFact(n + 1);
    vector<long> inv(n + 1);
    fact[0] = invFact[0] = 1;
    inv[0] = inv[1] = 1;
    for (int i = 1; i <= n; ++i) {
      if (i >= 2)
        inv[i] = kMod - kMod / i * inv[kMod % i] % kMod;
      fact[i] = fact[i - 1] * i % kMod;
      invFact[i] = invFact[i - 1] * inv[i] % kMod;
    }
    return {fact, invFact};
  }

  int nCk(int n, int k, const vector<long>& fact, const vector<long>& invFact) {
    return fact[n] * invFact[k] % kMod * invFact[n - k] % kMod;
  }
};
/* code provided by PROGIEZ */

3405. Count the Number of Arrays with K Matching Adjacent Elements LeetCode Solution in Java

class Solution {
  public int countGoodArrays(int n, int m, int k) {
    final long[][] factAndInvFact = getFactAndInvFact(n);
    final long[] fact = factAndInvFact[0];
    final long[] invFact = factAndInvFact[1];
    return (int) (m * modPow(m - 1, n - k - 1) % kMod * nCk(n - 1, k, fact, invFact) % kMod);
  }

  private static final int kMod = 1_000_000_007;

  private long modPow(long x, long n) {
    if (n == 0)
      return 1;
    if (n % 2 == 1)
      return x * modPow(x, n - 1) % kMod;
    return modPow(x * x % kMod, n / 2);
  }

  private long[][] getFactAndInvFact(int n) {
    long[] fact = new long[n + 1];
    long[] invFact = new long[n + 1];
    long[] inv = new long[n + 1];
    fact[0] = invFact[0] = 1;
    inv[0] = inv[1] = 1;
    for (int i = 1; i <= n; ++i) {
      if (i >= 2)
        inv[i] = kMod - kMod / i * inv[kMod % i] % kMod;
      fact[i] = fact[i - 1] * i % kMod;
      invFact[i] = invFact[i - 1] * inv[i] % kMod;
    }
    return new long[][] {fact, invFact};
  }

  private int nCk(int n, int k, long[] fact, long[] invFact) {
    return (int) (fact[n] * invFact[k] % kMod * invFact[n - k] % kMod);
  }
}
// code provided by PROGIEZ

3405. Count the Number of Arrays with K Matching Adjacent Elements LeetCode Solution in Python

class Solution:
  def countGoodArrays(self, n: int, m: int, k: int) -> int:
    kMod = 1_000_000_007
    return m * pow(m - 1, n - k - 1, kMod) * math.comb(n - 1, k) % kMod
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.