Scale Engineer

Count the Number of Arrays with K Matching Adjacent Elements

Hard
#3025Time: O(n * k). The outer loop runs `n-1` times, and the inner loop runs `k+1` times.Space: O(k). We use a 1D DP array of size `k+1` and update it in each iteration. Without this space optimization, the complexity would be `O(n * k)`.1 company
Patterns
MathCombinatorics
Companies
PhonePe

Prompt

You are given three integers n, m, 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 109 + 7.

 

Example 1:

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

Output: 4

Explanation:

  • There are 4 good arrays. They are [1, 1, 2], [1, 2, 2], [2, 1, 1] and [2, 2, 1].
  • Hence, the answer is 4.

Example 2:

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

Output: 6

Explanation:

  • The good arrays are [1, 1, 1, 2], [1, 1, 2, 2], [1, 2, 2, 2], [2, 1, 1, 1], [2, 2, 1, 1] and [2, 2, 2, 1].
  • Hence, the answer is 6.

Example 3:

Input: n = 5, m = 2, k = 0

Output: 2

Explanation:

  • The good arrays are [1, 2, 1, 2, 1] and [2, 1, 2, 1, 2]. Hence, the answer is 2.

 

Constraints:

  • 1 <= n <= 105
  • 1 <= m <= 105
  • 0 <= k <= n - 1

Approaches

2 approaches with complexity analysis and trade-offs.

This approach builds the solution iteratively using dynamic programming. We define a state dp[i][j] as the number of ways to form an array of length i with exactly j adjacent matches. We then derive a recurrence relation to compute dp[i][j] based on smaller subproblems.

Algorithm

  • Define a 2D DP array dp[i][j] to store the number of arrays of length i with j adjacent matches.
  • The base case is for an array of length 1. There are m possible arrays (e.g., [1], [2], ..., [m]), and all have 0 matches. So, dp[1][0] = m.
  • To build an array of length i with j matches, we can extend an array of length i-1.
  • Consider an array of length i-1. We add the i-th element.
    • Case 1: The new element creates a match. This means we must have had j-1 matches in the first i-1 elements. There is only 1 choice for the new element to match the previous one. So, we add dp[i-1][j-1] to dp[i][j].
    • Case 2: The new element does not create a match. This means we must have had j matches in the first i-1 elements. There are m-1 choices for the new element to not match the previous one. So, we add dp[i-1][j] * (m-1) to dp[i][j].
  • The recurrence relation is dp[i][j] = (dp[i-1][j-1] + dp[i-1][j] * (m-1)) % MOD.
  • The final answer is dp[n][k].
  • Space can be optimized to O(k) by using only two 1D arrays for the DP states.

Walkthrough

Let dp[i][j] be the number of arrays of length i with exactly j adjacent matching elements. Our goal is to find dp[n][k].

Base Case: For an array of length i=1, there are m possibilities (any number from 1 to m). There are 0 adjacent pairs, so 0 matches. Thus, dp[1][0] = m.

Recurrence Relation: To compute dp[i][j], we consider adding the i-th element to a valid array of length i-1.

  • To get j matches in an array of length i, the (i-1)-th pair (arr[i-2], arr[i-1]) can either be a match or not.
  • Case 1: arr[i-2] == arr[i-1] (a new match is formed). This requires that the prefix of length i-1 had j-1 matches. For any such array, the value of arr[i-2] is some number. To create a match, arr[i-1] must be the same number. There is only 1 choice for arr[i-1]. The number of ways for this case is dp[i-1][j-1].
  • Case 2: arr[i-2] != arr[i-1] (no new match is formed). This requires that the prefix of length i-1 already had j matches. For any such array, the value of arr[i-2] is some number. To avoid a match, arr[i-1] can be any of the other m-1 numbers. The number of ways for this case is dp[i-1][j] * (m-1).

Combining these cases, the recurrence is: dp[i][j] = (dp[i-1][j-1] + dp[i-1][j] * (m-1)) % MOD.

We can build a DP table of size (n+1) x (k+1) to store these values. Since dp[i] only depends on dp[i-1], we can optimize space to O(k) by using only two rows (or one, with careful updates).

class Solution {    public int countGoodArrays(int n, int m, int k) {        long MOD = 1_000_000_007;        if (k >= n) {            return 0;        }         // dp[j] will store the number of arrays of current length with j matches        long[] dp = new long[k + 1];                // Base case: length 1        dp[0] = m;         for (int i = 2; i <= n; i++) {            long[] next_dp = new long[k + 1];            for (int j = 0; j <= k; j++) {                // Case 1: arr[i-1] != arr[i-2]                // We extend an array of length i-1 with j matches                next_dp[j] = (dp[j] * (m - 1)) % MOD;                                // Case 2: arr[i-1] == arr[i-2]                // We extend an array of length i-1 with j-1 matches                if (j > 0) {                    next_dp[j] = (next_dp[j] + dp[j - 1]) % MOD;                }            }            dp = next_dp;        }         return (int) dp[k];    }}

Complexity

Time

O(n * k). The outer loop runs `n-1` times, and the inner loop runs `k+1` times.

Space

O(k). We use a 1D DP array of size `k+1` and update it in each iteration. Without this space optimization, the complexity would be `O(n * k)`.

Trade-offs

Pros

  • Relatively straightforward to come up with from first principles.

  • Correct for smaller constraints.

Cons

  • The time complexity of O(n * k) is too slow for the given constraints, where n and k can be up to 10^5. This will lead to a Time Limit Exceeded error.

Solutions

class Solution {private  static final int N = (int)1 e5 + 10;private  static final int MOD = (int)1 e9 + 7;private  static final long[] f = new long[N];private  static final long[] g = new long[N];  static {    f[0] = 1;    g[0] = 1;    for (int i = 1; i < N; ++i) {      f[i] = f[i - 1] * i % MOD;      g[i] = qpow(f[i], MOD - 2);    }  }public  static long qpow(long a, int k) {    long res = 1;    while (k != 0) {      if ((k & 1) == 1) {        res = res * a % MOD;      }      k >>= 1;      a = a * a % MOD;    }    return res;  }public  static long comb(int m, int n) {    return (int)f[m] * g[n] % MOD * g[m - n] % MOD;  }public  int countGoodArrays(int n, int m, int k) {    return (int)(comb(n - 1, k) * m % MOD * qpow(m - 1, n - k - 1) % MOD);  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem