Problem Description

Given three integers n, m, and k, you are asked to count the number of arrays arr of length n such that:

• Each element of arr is an integer in the range [1, m].
• The process of finding the maximum in arr by scanning from left to right takes exactly k comparisons to update the current maximum.
• Return the answer modulo 10^9 + 7.

Note: A "comparison" is counted every time we encounter a new maximum when scanning left-to-right. The first element always counts as the first maximum. For example, for arr = [2, 3, 1, 5, 4], the maximum updates at 2, 3, and 5, so there are 3 comparisons.

Thought Process

At first, it may seem that we need to generate all possible arrays of length n with elements in [1, m] and count those with exactly k maximum updates. However, this brute-force approach is not feasible for large n and m, as the number of possible arrays grows exponentially.

The key insight is to recognize this as a dynamic programming problem. We can break the problem into subproblems: for each position in the array, keep track of how many ways there are to build an array of a certain length, with a certain maximum so far, and a certain number of maximum updates left.

Instead of generating all arrays, we count the number of ways to reach each state, building up to the full solution.

Solution Approach

We use dynamic programming with memoization to efficiently compute the answer. The idea is to define a DP state dp[pos][max_so_far][search_cost] as the number of ways to build an array of length pos, where the current maximum is max_so_far, and exactly search_cost maximum updates remain.

1. State Definition:
   • pos: Current length of the array we've built so far (from 0 to n).
   • max_so_far: The current maximum value in the array so far (from 0 to m).
   • search_cost: Number of maximum updates left to perform (from 0 to k).
2. Recursion:
   • At each step, for each possible next value (num from 1 to m), we decide:
     • If num > max_so_far, it's a new maximum. We increment the maximum update count.
     • If num ≤ max_so_far, the maximum stays the same. The maximum update count does not change.
3. Base Case:
   • If pos == n (array is complete): If search_cost == 0, return 1 (valid array); else, return 0.
4. Transition:
   • For each possible num:
     • If num > max_so_far: dp[pos+1][num][search_cost-1]
     • If num ≤ max_so_far: dp[pos+1][max_so_far][search_cost]
5. Optimization:
   • For efficiency, instead of looping through all num from 1 to m at every step, we can:
     • For num ≤ max_so_far, there are max_so_far choices.
     • For num > max_so_far, loop num from max_so_far+1 to m.
6. Initialization:
   • We start with pos = 0, max_so_far = 0, and search_cost = k.
7. Modulo:
   • All computations are done modulo 10^9 + 7.

Example Walkthrough

Let's take n = 3, m = 3, k = 2 as an example.

• We want arrays of length 3 with elements in [1, 3], such that the maximum is updated exactly 2 times when scanning from left to right.
• Let's enumerate all arrays and count those with exactly 2 maximum updates:
  • [1,2,3]: 1→2→3 (updates at 1,2,3) → 3 updates (not valid)
  • [1,3,2]: 1→3 (updates at 1,3) → 2 updates (valid)
  • [2,1,3]: 2→3 (updates at 2,3) → 2 updates (valid)
  • [2,3,1]: 2→3 (updates at 2,3) → 2 updates (valid)
  • [3,1,2]: 3 (update at 3) → 1 update (not valid)
  • [3,2,1]: 3 (update at 3) → 1 update (not valid)
• There are 3 valid arrays: [1,3,2], [2,1,3], [2,3,1].
• Our DP approach will count these efficiently for any n, m, k.

Time and Space Complexity

• Brute-force:
  • Time: O(mⁿ) — generating all arrays is infeasible for large n and m.
  • Space: O(1) if just counting, but can be O(mⁿ) if storing arrays.
• Dynamic Programming:
  • Time: O(n * m * k) — because for each position (n), for each possible maximum (m), and for each search cost (k), we compute the result. Each DP state can be filled in O(m) time, but with optimizations, this is manageable.
  • Space: O(n * m * k) — for memoization.

Summary

The problem asks for the number of arrays with a specific number of maximum updates (comparisons) during a left-to-right scan. Instead of brute-force enumeration, we use dynamic programming to count the number of ways to build such arrays, tracking the current position, the maximum so far, and the number of updates left. This approach is efficient and scalable, allowing us to solve for large values of n, m, and k.

Code Implementation

MOD = 10 ** 9 + 7

def numOfArrays(n, m, k):
    from functools import lru_cache

    @lru_cache(maxsize=None)
    def dp(pos, max_so_far, remain):
        if pos == n:
            return 1 if remain == 0 else 0
        res = 0
        for num in range(1, m + 1):
            if num > max_so_far:
                if remain > 0:
                    res = (res + dp(pos + 1, num, remain - 1)) % MOD
            else:
                res = (res + dp(pos + 1, max_so_far, remain)) % MOD
        return res

    return dp(0, 0, k)
      

#include <vector>
using namespace std;

class Solution {
public:
    int numOfArrays(int n, int m, int k) {
        const int MOD = 1e9 + 7;
        vector<vector<vector<int>>> dp(n+1, vector<vector<int>>(m+2, vector<int>(k+2, -1)));

        function<int(int,int,int)> solve = [&](int pos, int max_so_far, int remain) {
            if (pos == n) return remain == 0 ? 1 : 0;
            if (dp[pos][max_so_far][remain] != -1) return dp[pos][max_so_far][remain];
            long long res = 0;
            for (int num = 1; num <= m; ++num) {
                if (num > max_so_far) {
                    if (remain > 0)
                        res = (res + solve(pos+1, num, remain-1)) % MOD;
                } else {
                    res = (res + solve(pos+1, max_so_far, remain)) % MOD;
                }
            }
            return dp[pos][max_so_far][remain] = res;
        };

        return solve(0, 0, k);
    }
};
      

class Solution {
    static final int MOD = 1_000_000_007;
    int[][][] memo;

    public int numOfArrays(int n, int m, int k) {
        memo = new int[n+1][m+2][k+2];
        for (int[][] arr2d : memo)
            for (int[] arr1d : arr2d)
                java.util.Arrays.fill(arr1d, -1);
        return dp(0, 0, k, n, m);
    }

    private int dp(int pos, int max_so_far, int remain, int n, int m) {
        if (pos == n) return remain == 0 ? 1 : 0;
        if (memo[pos][max_so_far][remain] != -1) return memo[pos][max_so_far][remain];
        long res = 0;
        for (int num = 1; num <= m; ++num) {
            if (num > max_so_far) {
                if (remain > 0)
                    res = (res + dp(pos+1, num, remain-1, n, m)) % MOD;
            } else {
                res = (res + dp(pos+1, max_so_far, remain, n, m)) % MOD;
            }
        }
        return memo[pos][max_so_far][remain] = (int)res;
    }
}
      

var numOfArrays = function(n, m, k) {
    const MOD = 1e9 + 7;
    const memo = {};
    function dp(pos, max_so_far, remain) {
        if (pos === n) return remain === 0 ? 1 : 0;
        const key = pos + ',' + max_so_far + ',' + remain;
        if (memo.hasOwnProperty(key)) return memo[key];
        let res = 0;
        for (let num = 1; num <= m; ++num) {
            if (num > max_so_far) {
                if (remain > 0)
                    res = (res + dp(pos+1, num, remain-1)) % MOD;
            } else {
                res = (res + dp(pos+1, max_so_far, remain)) % MOD;
            }
        }
        memo[key] = res;
        return res;
    }
    return dp(0, 0, k);
};