#3405

Hard

LeetCode Problem Workspace

Count the Number of Arrays with K Matching Adjacent Elements

Count the number of valid arrays with exactly k adjacent elements that are equal, using math and combinatorics techniques.

math combinatorics

Problem Statement

You are given three integers n, m, and k. Your task is to find how many arrays of size n can be formed, where the array has exactly k adjacent elements that are the same. The first position arr[0] has m possible values to choose from, and the rest of the array is built based on this condition.

The answer should be returned modulo 10^9 + 7 as the result can be quite large. Constraints are 1 <= n <= 10^5, 1 <= m <= 10^5, and 0 <= k <= n - 1.

Examples

Example 1

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

Output: 4

Example 2

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

Output: 6

Example 3

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

Output: 2

Constraints

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

Solution Approach

Dynamic Programming

Use dynamic programming to calculate the number of ways to form the array while ensuring k adjacent elements match. Track the count of arrays based on previous computations.

Modular Arithmetic

Since the number of valid arrays can be large, use modular arithmetic to calculate the result modulo 10^9 + 7 at every step to avoid overflow and ensure efficiency.

Combinatorics for Adjacent Matches

Apply combinatorics principles to calculate how to distribute the k matching adjacent elements in the array while considering the constraints on the values of the array positions.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n)

The time complexity is O(n), since each element of the array needs to be processed in constant time, while the space complexity is O(n) due to the storage required for dynamic programming calculations.

What Interviewers Usually Probe

Understanding of dynamic programming for counting combinations.
Ability to handle large numbers and modular arithmetic.
Insight into combinatorics and how it applies to adjacent element conditions.

Common Pitfalls or Variants

Common pitfalls

Not correctly handling the modulo operation, leading to overflow errors.
Incorrectly calculating the number of adjacent matching elements.
Failing to consider the edge cases, like k being 0 or n being very large.

Follow-up variants

Consider variations where the number of matching adjacent elements is greater than k.
Explore edge cases where n or m reaches their maximum values.
Alter the number of possible values for each position in the array.

FAQ

How can I solve the problem of counting arrays with exactly k matching adjacent elements?

Use dynamic programming and combinatorics to calculate the number of valid arrays, applying modular arithmetic to avoid overflow.

What is the time complexity of this problem?

The time complexity is O(n), as each array element is processed individually in constant time.

How does modular arithmetic come into play in this problem?

Since the result can be large, modular arithmetic ensures the final answer is within the range of 10^9 + 7, preventing overflow.

What are the common pitfalls in solving this problem?

Failing to handle modular arithmetic, incorrectly calculating adjacent matches, and not addressing edge cases are common pitfalls.

What approach should I take for problems with a similar pattern?

For similar combinatorial counting problems, apply dynamic programming to store intermediate results and use combinatorics for element distribution.

terminal

Solution

Solution 1: Combinatorics + Fast Power

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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

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

Continue Practicing

#3395 subsequences with a unique middle mode i #3426 manhattan distances of all arrangements of pieces #3428 maximum and minimum sums of at most size k subsequences