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

Math Combinatorics Hard

You are given three integers n, m, and 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 10^9 + 7.

Input & Output

Example 1 — Basic Case

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

› Output: 8

💡 Note: Arrays of length 4 using values [1,2] with exactly 1 matching adjacent pair. Examples: [1,1,2,1], [1,2,2,1], [2,1,1,2], etc. Total count is 8.

Example 2 — No Matches Required

$ Input: n = 2, m = 3, k = 0

› Output: 6

💡 Note: Arrays of length 2 using values [1,2,3] with no matching pairs. All adjacent elements must be different: [1,2], [1,3], [2,1], [2,3], [3,1], [3,2].

Example 3 — All Matches

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

› Output: 2

💡 Note: Arrays of length 3 with 2 matching pairs means all elements are the same. Only [1,1,1] and [2,2,2] satisfy this condition.

Constraints

1 ≤ n ≤ 1000
1 ≤ m ≤ 1000
0 ≤ k ≤ n-1

Visualization

Tap to expand

Asked in

G Google 15 M Microsoft 8

This problem can be solved using combinatorics. The key insight is that we need to choose k positions out of n-1 possible adjacent pairs for matches, then calculate the number of ways to fill the array. The optimal solution uses the formula C(n-1,k) × m × (m-1)^(n-1-k), achieving O(k) time complexity compared to the exponential brute force approach.

Common Approaches

✓ Brute Force Recursion

⏱️ Time: O(m^n) Space: O(n)

Generate all possible arrays by trying each value at each position recursively. Keep track of matching adjacent pairs and count valid arrays. This explores all possible combinations exhaustively.

Dynamic Programming with Memoization

⏱️ Time: O(n²m) Space: O(n²m)

Optimize the recursive approach by caching results for each unique state defined by current position, previous value, and current match count. This eliminates redundant calculations.

Optimized Mathematical Approach

⏱️ Time: O(k) Space: O(1)

Transform the problem into a combinatorial one. Choose k positions for matches, then calculate arrangements. Uses mathematical insight to avoid recursion entirely.

Algorithm Steps — Algorithm Steps

Code -

solution.c — C

Time & Space Complexity

Time Complexity

⏱️

⚠ Quadratic Growth

Space Complexity

⚠ Quadratic Space

12.0K Views

Medium Frequency

~35 min Avg. Time

450 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen