Count the Number of Arrays with K Matching Adjacent Elements

Count the Number of Arrays with K Matching Adjacent Elements

What is this problem about?

The Count the Number of Arrays with K Matching Adjacent Elements interview question is a combinatorial challenge. You are asked to count how many arrays of length $n$ can be formed using elements from the range $[1, m]$ such that there are exactly $k$ indices where arr[i] == arr[i+1].

The result can be very large, so you must provide the answer modulo $10^9 + 7$.

Why is this asked in interviews?

This "Hard" problem is used by Google and Bloomberg to test a candidate's mastery of combinatorics interview pattern logic and modular arithmetic. It requires breaking down a complex counting problem into two independent parts: picking the positions where the matches occur and picking the values for those positions. It tests the ability to apply the stars and bars principle or basic combination formulas in a programming context.

Algorithmic pattern used

This problem is solved using Combinatorics.

1. Choose the matching pairs: There are $n-1$ possible adjacent pairs. You need to choose exactly $k$ of them to be matches. This is $\binom{n-1}{k}$ ways.
2. Assign values:
   • Think of the $n$ elements as $n-k$ "blocks" of identical adjacent elements.
   • For the first block, you have $m$ choices.
   • For each of the remaining $(n-k-1)$ blocks, you have $m-1$ choices (since it cannot match the value of the block immediately to its left).
3. Combine: Total ways = $\binom{n-1}{k} imes m imes (m-1)^{n-k-1}$.

Example explanation

$n = 3, m = 2, k = 1$

1. Choose which pair matches: $\binom{2}{1} = 2$ ways. Either arr[0]==arr[1] or arr[1]==arr[2].
2. Case 1 (arr[0]==arr[1]):
   • Choose value for block 1: 2 choices (1 or 2).
   • Choose value for block 2 (arr[2]): $2-1 = 1$ choice (must differ from block 1).
   • Pairs: [1,1,2], [2,2,1]. (2 ways)
3. Case 2 (arr[1]==arr[2]):
   • Pairs: [2,1,1], [1,2,2]. (2 ways) Total = 4.

Common mistakes candidates make

• Failing to use Modular Inverse: When calculating combinations $\binom{n}{k}$ with a large modulo, you must use Fermat's Little Theorem or the Extended Euclidean Algorithm for division.
• Overcounting: Misunderstanding how the non-matching blocks interact.
• Incorrect Power calculation: Not using binary exponentiation (Modular Power) for $(m-1)^{n-k-1}$, leading to slow solutions.

Interview preparation tip

Brush up on "Combinatorics for Programmers." Know how to implement nCr with modulo and how to handle power(a, b, mod) efficiently. These are fundamental building blocks for many Hard-level counting problems.