Count the Number of Arrays with K Matching Adjacent Elements - Solution & Explanation
Problem Statement
You are given three integers n, m, k. A good array arr of size n is defined as follows:
- Each element in
arris in the inclusive range[1, m]. - Exactly
kindicesi(where1 <= i < n) satisfy the conditionarr[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 <= 1051 <= m <= 1050 <= k <= n - 1
Approach Overview
Problem 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.
Solution
For an array of length n, there are n - 1 pairs of adjacent elements. We need to select k of these n - 1 adjacent pairs such that the two elements in each of these k pairs are equal, and the remaining n - 1 - k adjacent pairs have different elements.
This is equivalent to splitting the array n - 1 - k times, resulting in n - k segments, where all elements in each segment are equal. The number of ways to split is C_{n - 1}^{n - 1 - k} = C_{n - 1}^{k}.
For the first segment, we can choose any element from [1, m]. For the remaining n - k - 1 segments, we just need to ensure that the element in each segment is different from the previous segment, so each of these segments has m - 1 choices. In total, there are m times (m - 1)^{n - k - 1} ways to choose.
Combining the two parts above, we get the answer:
$
C_{n - 1}^{k} times m times (m - 1)^{n - k - 1} bmod (10^9 + 7)
In the code implementation, we can precompute factorials and inverses, and use fast power to calculate combinations.
Ignoring the preprocessing time and space, the time complexity is O(log (n - k)), and the space complexity is O(1)$.
Detailed Complexity Analysis
| 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 |
Video Solution
Count the Number of Arrays with K Matching Adjacent Elements | Detailed Approach | Leetcode 3405 • codestorywithMIK • 8,684 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Count the Number of Arrays with K Matching Adjacent Elements easy or hard?
Count the Number of Arrays with K Matching Adjacent Elements Python/Java solution
How to solve Count the Number of Arrays with K Matching Adjacent Elements in O(log n)?
What is the best approach for Count the Number of Arrays with K Matching Adjacent Elements?
Is Count the Number of Arrays with K Matching Adjacent Elements asked at Google/Amazon/Meta?
What data structure is used in Count the Number of Arrays with K Matching Adjacent Elements?
What is the time complexity of Count the Number of Arrays with K Matching Adjacent Elements?
Ready to solve this problem?
Practice Count the Number of Arrays with K Matching Adjacent Elements with our built-in code editor and test cases.
Practice on FleetCode