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

Difficulty:
Related Topics:
Similar Questions:

    Problem

    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:

    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 satisify 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:

    Solution

    /**
     * @param {number} n
     * @param {number} m
     * @param {number} k
     * @return {number}
     */
    var numOfArrays = function(n, m, k) {
        return helper(n, m, k, 0, {});
    };
    
    var helper = function (n, m, k, maxSoFar, dp) {
        if (n === 0 && k === 0) return 1;
        if (n === 0) return 0;
        if (maxSoFar === m && k > 0) return 0;
        var key = `${n}-${k}-${maxSoFar}`;
        if (dp[key] !== undefined) {
            return dp[key];
        }
        var mod = Math.pow(10, 9) + 7;
        var ans = 0;
        // choose num less than the current max value
        for (var i = 1; i <= maxSoFar; i++) {
            ans = (ans + helper(n - 1, m, k, maxSoFar, dp)) % mod;
        }
        // choose num bigger than the current max value
        for (var j = maxSoFar + 1; j <= m; j++) {
            ans = (ans + helper(n - 1, m, k - 1, j, dp)) % mod;
        }
        dp[key] = ans;
        return dp[key];
    };
    

    Explain:

    nope.

    Complexity: