Count The Number Of Arrays With K Matching Adjacent Elements · Interview Problem

Back to problems

Leetcode

Medium

Arrays

Math

Combinatorics

Dynamic Programming

Count The Number Of Arrays With K Matching Adjacent Elements

Count how many arrays of length $n$ over values in $[1, m]$ have exactly $k$ adjacent equal pairs.

Acceptance 50%

Start Practice

Problem Statement

You are given three integers $n$ , $m$ , and $k$ .

Count the number of arrays of length $n$ such that:

Each element is an integer from $1 $to$ m$ inclusive.
Exactly $k$ indices $i$ satisfy $1 \le i < n$ and $a_i = a_{i+1}$ .

Return the number of such arrays modulo $10^9 + 7$ .

This is a counting problem: you do not need to construct the arrays, only count how many satisfy the condition.

Input Format

A single test instance is given as three integers:

$n$ — length of the array
$m$ — number of possible values
$k$ — required number of adjacent equal pairs

Output Format

Return one integer: the number of arrays of length $n$ with exactly $k$ matching adjacent pairs, modulo $10^9 + 7$ .

Constraints

$1 \le n, m \le 10^5$
$0 \le k < n$
Answers are taken modulo $10^9 + 7$

Note: the exact official limits may vary by platform, but the problem is typically solved under modular arithmetic with combinatorial DP.

Examples

Sample cases returned by the problem API.

Example 1

Input

n = 3, m = 2, k = 1

Output

Explanation

Arrays of length 3 over {1, 2} with exactly one equal adjacent pair are:

[1, 1, 2]
[1, 2, 2]
[2, 2, 1]
[2, 1, 1]

So the answer is 4.

Example 2

Input

n = 2, m = 3, k = 0

Output

Explanation

We need arrays of length 2 with no equal adjacent pair. The first element can be any of 3 values, and the second must be different, giving $3 \times 2 = 6$ arrays.

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress