Count the Number of Arrays with K Matching Adjacent Elements

Hard Dynamic Programming Combinatorics Original on LeetCode

Reported atPhonePe

Count the Number of Arrays with K Matching Adjacent Elements is a hard dynamic programming problem solved with the combinatorics pattern. The best approach, optimal (combinatorics with factorials), runs in O(n + log MOD) time and O(n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from dp over length and number of matches up.

Problem

Count the arrays arr of length n such that every element is an integer between 1 and m (inclusive), and exactly k indices i (with 1 <= i < n) satisfy arr[i - 1] == arr[i].

Return the count modulo 10^9 + 7.

Examples

Example 1

Input
n = 3, m = 2, k = 1
Output
4
Why
With values 1 and 2 the arrays with exactly one equal neighbour pair are [1, 1, 2], [1, 2, 2], [2, 2, 1] and [2, 1, 1].

Example 2

Input
n = 4, m = 3, k = 0
Output
24
Why
No two neighbours may be equal: 3 choices for the first value and 2 for each of the other three, 3 · 2 · 2 · 2 = 24.

Example 3

Input
n = 2, m = 5, k = 1
Output
5
Why
Both values must be equal: [1, 1] through [5, 5].

Constraints

  • 1 <= n <= 10^5
  • 1 <= m <= 10^5
  • 0 <= k <= n - 1
  • Return the answer modulo 10^9 + 7.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
DP over length and number of matchesO(n · k)O(k)
Optimal (combinatorics with factorials)O(n + log MOD)O(n)

1DP over length and number of matches

TimeO(n · k)n - 1 extensions, each updating k + 1 counters.
SpaceO(k)One row of k + 1 counters, updated in place from high j to low j.

Let ways[j] be the number of arrays of the current length with exactly j matching neighbour pairs. Appending one element either repeats the last value (j grows by one, 1 way) or changes it (j stays, m - 1 ways).

  1. Length 1: ways[0] = m.
  2. For each new position, from j = k down to 0: ways[j] = ways[j] · (m - 1) + ways[j - 1].
  3. Return ways[k].
class Solution {
    public int countGoodArrays(int n, int m, int k) {
        final long MOD = 1_000_000_007L;
        long[] ways = new long[k + 1];
        ways[0] = m % MOD;
        for (int len = 2; len <= n; len++) {
            for (int j = k; j >= 0; j--) {
                long keep = ways[j] * (m - 1) % MOD;
                long fromMatch = j > 0 ? ways[j - 1] : 0;
                ways[j] = (keep + fromMatch) % MOD;
            }
        }
        return (int) ways[k];
    }
}

2Optimal (combinatorics with factorials)

TimeO(n + log MOD)Linear factorial tables plus a couple of fast exponentiations.
SpaceO(n)The factorial and inverse-factorial arrays.

Choose which k of the n - 1 neighbour gaps are matches: C(n - 1, k) ways. The first element has m choices, each of the remaining n - 1 - k gaps is a change with m - 1 choices, and each match is forced. Multiply, all modulo 10^9 + 7, using precomputed factorials and Fermat inverses.

  1. Precompute fact[0..n-1] and the inverse of fact[n-1], then fill inverse factorials downwards.
  2. C = fact[n-1] · invFact[k] · invFact[n-1-k].
  3. Return C · m · (m - 1)^(n - 1 - k) mod 10^9 + 7 (fast power).
class Solution {
    private static final long MOD = 1_000_000_007L;

    private long power(long b, long e) {
        long r = 1;
        b %= MOD;
        while (e > 0) {
            if ((e & 1) == 1) r = r * b % MOD;
            b = b * b % MOD;
            e >>= 1;
        }
        return r;
    }

    public int countGoodArrays(int n, int m, int k) {
        long[] fact = new long[n];
        long[] inv = new long[n];
        fact[0] = 1;
        for (int i = 1; i < n; i++) fact[i] = fact[i - 1] * i % MOD;
        inv[n - 1] = power(fact[n - 1], MOD - 2);
        for (int i = n - 1; i > 0; i--) inv[i - 1] = inv[i] * i % MOD;
        long comb = fact[n - 1] * inv[k] % MOD * inv[n - 1 - k] % MOD;
        return (int) (comb * m % MOD * power(m - 1, n - 1 - k) % MOD);
    }
}

Edge cases to test

  • n = 1: there are no adjacent pairs, so the answer is m
  • m = 1: only the all-ones array exists, which has n - 1 matches
  • k = n - 1: all values equal, answer m
  • k = 0: no equal neighbours

Hints

Hint 1

Look at the n - 1 gaps between neighbours. Each gap is either a match (same value as the left neighbour) or a change.

Hint 2

Pick which k gaps are matches. Once that is fixed, how many ways are there to choose the actual values?

Hint 3

The first element has m options, every change has m - 1 options and every match has 1, so the count is C(n - 1, k) · m · (m - 1)^(n - 1 - k). Precompute factorials and use modular inverses.

FAQ

What is the best time complexity for Count the Number of Arrays with K Matching Adjacent Elements?

Optimal (combinatorics with factorials) runs in O(n + log MOD) time and O(n) extra space. Linear factorial tables plus a couple of fast exponentiations.

Which pattern does Count the Number of Arrays with K Matching Adjacent Elements use?

It is a dynamic programming problem that uses the combinatorics pattern.

Is there a brute force solution for Count the Number of Arrays with K Matching Adjacent Elements?

Yes. DP over length and number of matches takes O(n · k) time and O(k) space. Let ways[j] be the number of arrays of the current length with exactly j matching neighbour pairs.

Which edge cases should I test for Count the Number of Arrays with K Matching Adjacent Elements?

n = 1: there are no adjacent pairs, so the answer is m; m = 1: only the all-ones array exists, which has n - 1 matches; k = n - 1: all values equal, answer m; k = 0: no equal neighbours.