Introduction

In this blog post, we will explore how to solve the LeetCode problem "3405" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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

Explanation

Here's an efficient solution to the problem, along with explanations:

• High-Level Approach:

  • Dynamic Programming: Use a DP table to store the number of good arrays with a specific number of adjacent equal elements. dp[i][j] stores the number of arrays of length i+1 with j adjacent equal elements.
  • Base Case: Initialize the DP table for arrays of length 1.
  • Transitions: Calculate the DP values based on whether the current element is equal to the previous element or not.

• Complexity:

  • Runtime: O(n*k)
  • Storage: O(n*k)

Code

    def good_arrays(n: int, m: int, k: int) -> int:
    """
    Calculates the number of good arrays that can be formed.

    Args:
        n: The size of the array.
        m: The range of values for each element in the array (1 to m).
        k: The number of adjacent equal elements required.

    Returns:
        The number of good arrays modulo 10^9 + 7.
    """

    MOD = 10**9 + 7
    dp = [[0] * (k + 1) for _ in range(n)]

    # Base case: array of size 1
    dp[0][0] = m

    # Iterate through array lengths from 2 to n
    for i in range(1, n):
        # Iterate through the possible number of adjacent equal elements
        for j in range(k + 1):
            # If the current element is different from the previous one
            if j == 0:
                dp[i][j] = (dp[i - 1][j] * (m - 1)) % MOD
            else:
                dp[i][j] = (dp[i - 1][j] * (m - 1) + dp[i - 1][j - 1]) % MOD

    return dp[n - 1][k]