1420. Build Array Where You Can Find The Maximum Exactly K Comparisons LeetCode Solution

In this guide, you will get 1420. Build Array Where You Can Find The Maximum Exactly K Comparisons LeetCode Solution with the best time and space complexity. The solution to Build Array Where You Can Find The Maximum Exactly K Comparisons problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Build Array Where You Can Find The Maximum Exactly K Comparisons solution in C++
4. Build Array Where You Can Find The Maximum Exactly K Comparisons solution in Java
5. Build Array Where You Can Find The Maximum Exactly K Comparisons solution in Python
6. Additional Resources

Problem Statement of Build Array Where You Can Find The Maximum Exactly K Comparisons

You are given three integers n, m and k. Consider the following algorithm to find the maximum element of an array of positive integers:

You should build the array arr which has the following properties:

arr has exactly n integers.
1 <= arr[i] <= m where (0 <= i < n).
After applying the mentioned algorithm to arr, the value search_cost is equal to k.

Return the number of ways to build the array arr under the mentioned conditions. As the answer may grow large, the answer must be computed modulo 109 + 7.

Example 1:

Input: n = 2, m = 3, k = 1
Output: 6
Explanation: The possible arrays are [1, 1], [2, 1], [2, 2], [3, 1], [3, 2] [3, 3]

Example 2:

Input: n = 5, m = 2, k = 3
Output: 0
Explanation: There are no possible arrays that satisfy the mentioned conditions.

Example 3:

Input: n = 9, m = 1, k = 1
Output: 1
Explanation: The only possible array is [1, 1, 1, 1, 1, 1, 1, 1, 1]

Constraints:

1 <= n <= 50
1 <= m <= 100
0 <= k <= n

Complexity Analysis

• Time Complexity: O(nmk)
• Space Complexity: O(nmk)

1420. Build Array Where You Can Find The Maximum Exactly K Comparisons LeetCode Solution in C++

class Solution {
 public:
  int numOfArrays(int n, int m, int k) {
    constexpr int kMod = 1'000'000'007;
    // dp[i][j][k] := the number of ways to build an array of length i, where j
    // is the maximum number and k is `search_cost`
    vector<vector<vector<int>>> dp(
        n + 1, vector<vector<int>>(m + 1, vector<int>(k + 1)));

    for (int j = 1; j <= m; ++j)
      dp[1][j][1] = 1;

    for (int i = 2; i <= n; ++i)                 // for each length
      for (int j = 1; j <= m; ++j)               // for each max value
        for (int cost = 1; cost <= k; ++cost) {  // for each cost
          // 1. Appending any of [1, j] in the i-th position doesn't change the
          //    maximum and cost.
          dp[i][j][cost] = static_cast<long>(j) * dp[i - 1][j][cost] % kMod;
          // 2. Appending j in the i-th position makes j the new max and cost 1.
          for (int prevMax = 1; prevMax < j; ++prevMax) {
            dp[i][j][cost] += dp[i - 1][prevMax][cost - 1];
            dp[i][j][cost] %= kMod;
          }
        }

    int ans = 0;
    for (int j = 1; j <= m; ++j) {
      ans += dp[n][j][k];
      ans %= kMod;
    }
    return ans;
  }
};
/* code provided by PROGIEZ */

1420. Build Array Where You Can Find The Maximum Exactly K Comparisons LeetCode Solution in Java

class Solution {
  public int numOfArrays(int n, int m, int k) {
    final int kMod = 1_000_000_007;
    // dp[i][j][k] := the number of ways to build an array of length i, where j
    // is the maximum number and k is `search_cost`
    int[][][] dp = new int[n + 1][m + 1][k + 1];

    for (int j = 1; j <= m; ++j)
      dp[1][j][1] = 1;

    for (int i = 2; i <= n; ++i)                // for each length
      for (int j = 1; j <= m; ++j)              // for each max value
        for (int cost = 1; cost <= k; ++cost) { // for each cost
          // 1. Appending any of [1, j] in the i-th position doesn't change the
          //    maximum and cost.
          dp[i][j][cost] = (int) ((long) j * dp[i - 1][j][cost] % kMod);
          // 2. Appending j in the i-th position makes j the new max and cost 1.
          for (int prevMax = 1; prevMax < j; ++prevMax) {
            dp[i][j][cost] += dp[i - 1][prevMax][cost - 1];
            dp[i][j][cost] %= kMod;
          }
        }

    int ans = 0;
    for (int j = 1; j <= m; ++j) {
      ans += dp[n][j][k];
      ans %= kMod;
    }
    return ans;
  }
}
// code provided by PROGIEZ

1420. Build Array Where You Can Find The Maximum Exactly K Comparisons LeetCode Solution in Python

class Solution:
  def numOfArrays(self, n: int, m: int, k: int) -> int:
    kMod = 1_000_000_007
    # dp[i][j][k] := the number of ways to build an array of length i, where j
    # is the maximum number and k is `search_cost`
    dp = [[[0] * (k + 1) for j in range(m + 1)] for _ in range(n + 1)]

    for j in range(1, m + 1):
      dp[1][j][1] = 1

    for i in range(2, n + 1):  # for each length
      for j in range(1, m + 1):  # for each max value
        for cost in range(1, k + 1):  # for each cost
          # 1. Appending any of [1, j] in the i-th position doesn't change the
          #    maximum and cost.
          dp[i][j][cost] = j * dp[i - 1][j][cost] % kMod
          # 2. Appending j in the i-th position makes j the new max and cost 1.
          for prevMax in range(1, j):
            dp[i][j][cost] += dp[i - 1][prevMax][cost - 1]
            dp[i][j][cost] %= kMod

    return sum(dp[n][j][k] for j in range(1, m + 1)) % kMod
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.