Count the Number of Arrays with K Matching Adjacent Elements

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

Understanding the Visualization

Input

Array length n=4, values 1 to m=2, need k=1 matches

Process

Choose positions for matches, then fill systematically

Output

Count of valid arrays = 8

Key Takeaway

🎯 Key Insight: Use combinatorics to choose match positions, then fill systematically

Asked in

G Google 15 M Microsoft 8

The key insight is to use combinatorics to choose k positions for matching pairs, then systematically fill the array. The optimal approach uses the formula: C(n-1,k) × m × (m-1)^(n-1-k). Time: O(k), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Mathematical Combinatorics	O(k)	O(1)	Use combinatorics to directly calculate the count without generating arrays
Dynamic Programming with Memoization	O(n × m × k)	O(n × m × k)	Use 3D DP to store results for (position, previous_value, matches_so_far)
Brute Force Recursion	O(m^n)	O(n)	Generate all possible arrays and count those with exactly k matching pairs

Mathematical Combinatorics — Algorithm Steps

Choose k positions from n-1 possible adjacent pairs using C(n-1,k)
First element has m choices
Each non-matching transition has (m-1) choices
Multiply all possibilities together

Visualization

Tap to expand

Step-by-Step Walkthrough

Choose Positions

Select k positions from n-1 adjacent pairs for matches

Fill Array

First element: m choices, non-matching transitions: (m-1) each

Multiply

Total = C(n-1,k) × m × (m-1)^(n-1-k)

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>

#define MOD 1000000007

long long powMod(long long base, int exp, int mod) {
    long long result = 1;
    base = base % mod;
    while (exp > 0) {
        if (exp % 2 == 1) {
            result = (result * base) % mod;
        }
        exp = exp >> 1;
        base = (base * base) % mod;
    }
    return result;
}

long long modInverse(long long a, int mod) {
    return powMod(a, mod - 2, mod);
}

long long combination(int n, int k, int mod) {
    if (k > n || k < 0) return 0;
    if (k == 0 || k == n) return 1;
    
    long long numerator = 1;
    long long denominator = 1;
    
    for (int i = 0; i < k; i++) {
        numerator = (numerator * (n - i)) % mod;
        denominator = (denominator * (i + 1)) % mod;
    }
    
    return (numerator * modInverse(denominator, mod)) % mod;
}

int solution(int n, int m, int k) {
    if (k > n - 1) {
        return 0;
    }
    
    long long waysToChoose = combination(n - 1, k, MOD);
    int nonMatchingPositions = n - 1 - k;
    long long waysToFill = ((long long) m * powMod(m - 1, nonMatchingPositions, MOD)) % MOD;
    
    return (waysToChoose * waysToFill) % MOD;
}

int main() {
    int n, m, k;
    scanf("%d", &n);
    scanf("%d", &m);
    scanf("%d", &k);
    printf("%d\n", solution(n, m, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(k)

Computing binomial coefficient C(n-1,k) and power calculations

✓ Linear Growth

Space Complexity

O(1)

Only using variables for computation, no extra data structures

✓ Linear 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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Mathematical Combinatorics — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler