Watch 10 video solutions for Count the Number of Arrays with K Matching Adjacent Elements, a hard level problem involving Math, Combinatorics. This walkthrough by codestorywithMIK has 8,542 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given three integers n, m, k. A good array arr of size n is defined as follows:
arr is in the inclusive range [1, m].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:
[1, 1, 2], [1, 2, 2], [2, 1, 1] and [2, 2, 1].Example 2:
Input: n = 4, m = 2, k = 2
Output: 6
Explanation:
[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].Example 3:
Input: n = 5, m = 2, k = 0
Output: 2
Explanation:
[1, 2, 1, 2, 1] and [2, 1, 2, 1, 2]. Hence, the answer is 2.
Constraints:
1 <= n <= 1051 <= m <= 1050 <= k <= n - 1Problem Overview: You need to count how many arrays of length n using values 1..m contain exactly k adjacent positions where a[i] == a[i+1]. The challenge is counting valid configurations without enumerating all m^n possibilities.
Approach 1: Dynamic Programming on Adjacent Matches (O(n * k) time, O(k) space)
A direct way is to build the array position by position while tracking how many matching adjacent pairs have been formed. Let dp[i][j] represent the number of ways to construct the first i elements with exactly j matching adjacent pairs. When adding element a[i], you have two choices: match the previous element (a[i] = a[i-1]) which increases the match count, or choose a different value (m-1 options) which does not. Transition through these two cases while ensuring the match count never exceeds k. This approach demonstrates the structure of the problem clearly but becomes less attractive when n is large.
Approach 2: Combinatorics + Fast Power (O(log n) time, O(1) space)
The optimal solution comes from observing that only the n-1 adjacent gaps determine whether a pair matches. Choose exactly k of these gaps where a[i] = a[i+1]. The number of ways to choose these positions is C(n-1, k). Once the matching gaps are fixed, the array effectively splits into n-k segments where the value must change between segments.
The first element has m choices. For every non-matching boundary (n-1-k of them), the next element must differ from the previous value, giving m-1 choices each time. The total number of valid arrays becomes:
C(n-1, k) * m * (m-1)^(n-1-k)
Because results are typically required modulo a large prime, compute the power using fast exponentiation. This reduces the exponentiation cost to O(log n). Combination values can be computed using factorials or an iterative formula depending on constraints.
This approach relies on counting configurations instead of constructing arrays. It converts the problem into pure combinatorics and modular arithmetic from math, which is why it scales easily even when n is very large.
Recommended for interviews: The combinatorics formula with fast exponentiation is the expected solution. Explaining the DP idea first shows you understand the state transitions, but recognizing the combinatorial structure and deriving C(n-1, k) * m * (m-1)^(n-1-k) demonstrates stronger problem-solving and mathematical insight.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming on Adjacent Matches | O(n * k) | O(k) | Useful for understanding transitions and when constraints are small |
| Combinatorics + Fast Power | O(log n) | O(1) | Optimal solution for large n; converts the problem to counting choices of matching gaps |