# Build Array Where You Can Find The Maximum Exactly K Comparisons
**Difficulty:** HARD
[External](https://leetcode.com/problems/build-array-where-you-can-find-the-maximum-exactly-k-comparisons)
Canonical: https://scaleengineer.com/dsa/problems/build-array-where-you-can-find-the-maximum-exactly-k-comparisons
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Companies:** [Amdocs](https://scaleengineer.com/companies/amdocs), [Dunzo](https://scaleengineer.com/companies/dunzo)
---
## 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:

![](https://assets.glich.co/dsa/build-array-where-you-can-find-the-maximum-exactly-k-comparisons/image0.png) 

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`

# Approaches
## Top-Down DP with Memoization
This approach uses recursion with memoization to solve the problem. We define a recursive function that represents the state of building the array. The state includes the current index we are filling, the maximum value encountered so far, and the accumulated search cost. Memoization is used to store the results of subproblems to avoid redundant calculations, which is crucial for passing within the time limits for smaller constraints but is not the most optimal solution.
**Time:** O(n * m * k * m). The state space is `n * m * k`. For each state, we might loop up to `m` times to choose the next new maximum. · **Space:** O(n * m * k). This is for the memoization table. The recursion depth is at most `n`.
**Pros:** Relatively intuitive to formulate from the problem description.; Correctly solves the problem by exploring the state space.
**Cons:** The time complexity is high due to the inner loop in the recursive step, which iterates up to `m` times.
### Explanation
We define a function, say `solve(i, current_max, cost)`, which returns the number of ways to build the suffix of the array from index `i` to `n-1`, given that the maximum value in the prefix `arr[0...i-1]` is `current_max` and the search cost so far is `cost`.
The state of our recursion is defined by three parameters:
1. `i`: The current index in the array to be filled (from `0` to `n`).
2. `current_max`: The maximum value found in the array prefix `arr[0...i-1]`.
3. `cost`: The search cost accumulated so far.

**Base Cases:**
- If `cost > k`, it's impossible to achieve a final cost of `k`, so we return 0.
- If `i == n`, we have filled the entire array. If `cost == k`, we have found a valid array, so we return 1. Otherwise, we return 0.

**Recursive Step:**
- At index `i`, we can choose a value for `arr[i]` from `1` to `m`.
- **Option 1:** Choose `arr[i]` such that `1 <= arr[i] <= current_max`. This does not increase the search cost. There are `current_max` such choices. The number of ways for this option is `current_max * solve(i + 1, current_max, cost)`.
- **Option 2:** Choose `arr[i]` such that `current_max < arr[i] <= m`. This increases the search cost by 1. For each choice `j` in this range, the new maximum becomes `j`. The number of ways is the sum of `solve(i + 1, j, cost + 1)` for all `j` from `current_max + 1` to `m`.

We use a 3D array `memo[i][current_max][cost]` to store the results. The modulo operation is applied at each addition to prevent overflow.
The initial call to the function is `solve(0, 0, 0)`.
```java
class Solution {
    private int n;
    private int m;
    private int k;
    private int MOD = 1_000_000_007;
    private Integer[][][] memo;

    public int numOfArrays(int n, int m, int k) {
        this.n = n;
        this.m = m;
        this.k = k;
        this.memo = new Integer[n + 1][m + 1][k + 1];
        return solve(0, 0, 0);
    }

    private int solve(int i, int currentMax, int cost) {
        if (i == n) {
            return (cost == k) ? 1 : 0;
        }
        if (cost > k) {
            return 0;
        }
        if (memo[i][currentMax][cost] != null) {
            return memo[i][currentMax][cost];
        }

        long ans = 0;

        // Option 1: arr[i] <= currentMax
        // The next element is not a new maximum.
        ans = (ans + (long)currentMax * solve(i + 1, currentMax, cost)) % MOD;

        // Option 2: arr[i] > currentMax
        // The next element is a new maximum.
        for (int val = currentMax + 1; val <= m; val++) {
            ans = (ans + solve(i + 1, val, cost + 1)) % MOD;
        }

        return memo[i][currentMax][cost] = (int)ans;
    }
}
```
### Algorithm
- Create a 3D memoization table `memo[n+1][m+1][k+1]` initialized with a value indicating "not computed".
- Define a recursive function `solve(i, current_max, cost)`.
- In `solve`:
    - Check for base cases: if `i == n`, return 1 if `cost == k`, else 0. If `cost > k`, return 0.
    - Check if `memo[i][current_max][cost]` is already computed. If so, return it.
    - Initialize `count = 0`.
    - Calculate ways for `arr[i] <= current_max`: `count += current_max * solve(i + 1, current_max, cost)`.
    - Loop `val` from `current_max + 1` to `m`: `count += solve(i + 1, val, cost + 1)`.
    - Store `count % MOD` in the memo table and return it.
- Start the process by calling `solve(0, 0, 0)`.

## Bottom-Up DP with Prefix Sum Optimization
This approach uses bottom-up dynamic programming. We define a 3D DP state `dp[i][j][l]` representing the number of ways to build an array of length `i` with a maximum value of exactly `j` and a search cost of `l`. The key to improving efficiency over the naive DP is to optimize the transition. The transition requires summing up values from the previous state, which can be done efficiently using a prefix sum technique, reducing the complexity of each state calculation from `O(m)` to `O(1)`.
**Time:** O(n * m * k). We have three nested loops for `i`, `l`, and `j`. The operations inside the innermost loop are `O(1)`. · **Space:** O(n * m * k). For the 3D DP table.
**Pros:** Much more efficient than the unoptimized DP due to the prefix sum calculation.; A systematic, iterative approach that avoids recursion overhead.
**Cons:** Requires a large amount of memory for the 3D DP table.
### Explanation
Let `dp[i][j][l]` be the number of ways to construct an array of length `i` such that its maximum element is `j` and the search cost is `l`.
Our goal is to compute `sum(dp[n][j][k])` for all `j` from `1` to `m`.

**Base Case:** For an array of length 1, `arr = [j]`, the maximum is `j` and the cost is 1. So, `dp[1][j][1] = 1` for `1 <= j <= m`.

**Recurrence Relation:** To compute `dp[i][j][l]`, we consider how the `i`-th element is added to an array of length `i-1`.
- **Case 1:** The `i`-th element is not a new maximum. This means the maximum of the first `i-1` elements was already `j`, and the `i`-th element is chosen from `1, ..., j`. There are `j` choices for the `i`-th element. The number of ways is `dp[i-1][j][l] * j`.
- **Case 2:** The `i`-th element is a new maximum, and its value is `j`. This means the maximum of the first `i-1` elements was some value `p < j`, and the cost for the prefix was `l-1`. The number of ways is the sum of `dp[i-1][p][l-1]` for all `p` from `1` to `j-1`.

The full recurrence is: `dp[i][j][l] = (dp[i-1][j][l] * j) + (sum_{p=1}^{j-1} dp[i-1][p][l-1])`.

**Optimization:** The summation term `sum_{p=1}^{j-1} dp[i-1][p][l-1]` is a prefix sum. As we iterate `j` from `1` to `m` (for fixed `i` and `l`), we can maintain this sum in a variable, updating it in `O(1)` at each step.
```java
class Solution {
    public int numOfArrays(int n, int m, int k) {
        if (k == 0) return 0;
        int MOD = 1_000_000_007;
        long[][][] dp = new long[n + 1][m + 1][k + 1];

        // Base case: for length 1, any max j in [1, m] has cost 1.
        for (int j = 1; j <= m; j++) {
            dp[1][j][1] = 1;
        }

        for (int i = 2; i <= n; i++) {
            for (int l = 1; l <= k; l++) {
                long prefixSum = 0;
                for (int j = 1; j <= m; j++) {
                    // Case 1: The i-th element is not a new maximum.
                    long ways = (dp[i - 1][j][l] * j) % MOD;
                    
                    // Case 2: The i-th element is a new maximum, j.
                    // The prefix sum is sum_{p=1}^{j-1} dp[i-1][p][l-1].
                    ways = (ways + prefixSum) % MOD;
                    
                    dp[i][j][l] = ways;

                    // Update prefix sum for the next iteration of j.
                    prefixSum = (prefixSum + dp[i - 1][j][l - 1]) % MOD;
                }
            }
        }

        long ans = 0;
        for (int j = 1; j <= m; j++) {
            ans = (ans + dp[n][j][k]) % MOD;
        }
        return (int)ans;
    }
}
```
### Algorithm
- Initialize a 3D DP table `dp[n+1][m+1][k+1]`.
- Set base cases: `dp[1][j][1] = 1` for `j` from 1 to `m`.
- Iterate `i` from 2 to `n` (length of array).
- Iterate `l` from 1 to `k` (cost).
- Initialize `prefixSum = 0`.
- Iterate `j` from 1 to `m` (max value).
    - Calculate `dp[i][j][l] = (dp[i-1][j][l] * j + prefixSum) % MOD`.
    - Update `prefixSum = (prefixSum + dp[i-1][j][l-1]) % MOD`.
- Sum up `dp[n][j][k]` for all `j` from 1 to `m` to get the final answer.

## Space-Optimized Bottom-Up DP
This is the most efficient approach. It builds upon the optimized bottom-up DP solution. By observing that the computation of DP states for a given length `i` only depends on the states from the previous length `i-1`, we can optimize the space complexity. Instead of storing the entire 3D DP table, we only need to keep track of the DP values for the current and previous lengths. This reduces the space from `O(n * m * k)` to `O(m * k)`.
**Time:** O(n * m * k). The time complexity remains the same as the non-space-optimized version. · **Space:** O(m * k). We only need to store DP states for two consecutive lengths.
**Pros:** Optimal time complexity for this problem.; Significantly reduced space complexity, making it feasible for larger constraints on `n`.
**Cons:** The logic can be slightly harder to follow compared to the direct recursive approach.
### Explanation
The logic and recurrence relation are identical to the previous bottom-up DP approach. The only difference is in the implementation of the DP table.
We notice that `dp[i][][]` only depends on `dp[i-1][][]`. This means we don't need to store the states for all `i` from 1 to `n`.
We can use two 2D arrays, `dp[m+1][k+1]` and `prev_dp[m+1][k+1]`, to represent the DP states for the current length `i` and the previous length `i-1`, respectively.
In each iteration of the main loop (for `i`), `prev_dp` holds the values for `i-1`, and we compute the new values into `dp`. After the inner loops for `l` and `j` are complete, we set `prev_dp = dp` for the next iteration of `i`.
```java
class Solution {
    public int numOfArrays(int n, int m, int k) {
        if (k == 0) return 0;
        int MOD = 1_000_000_007;
        
        long[][] prev_dp = new long[m + 1][k + 1];

        // Base case for i = 1
        for (int j = 1; j <= m; j++) {
            prev_dp[j][1] = 1;
        }

        for (int i = 2; i <= n; i++) {
            long[][] dp = new long[m + 1][k + 1];
            for (int l = 1; l <= k; l++) {
                long prefixSum = 0;
                for (int j = 1; j <= m; j++) {
                    // Case 1: The i-th element is not a new maximum.
                    long ways = (prev_dp[j][l] * j) % MOD;
                    
                    // Case 2: The i-th element is a new maximum, j.
                    ways = (ways + prefixSum) % MOD;
                    
                    dp[j][l] = ways;

                    // Update prefix sum for the next iteration of j.
                    prefixSum = (prefixSum + prev_dp[j][l - 1]) % MOD;
                }
            }
            prev_dp = dp; // Move to the next length
        }

        long ans = 0;
        for (int j = 1; j <= m; j++) {
            ans = (ans + prev_dp[j][k]) % MOD;
        }
        return (int)ans;
    }
}
```
### Algorithm
- Initialize a 2D array `prev_dp[m+1][k+1]`.
- Set base cases for `i=1`: `prev_dp[j][1] = 1` for `j` from 1 to `m`.
- Iterate `i` from 2 to `n`.
    - Initialize a new 2D array `dp[m+1][k+1]`.
    - Iterate `l` from 1 to `k`.
    - Initialize `prefixSum = 0`.
    - Iterate `j` from 1 to `m`.
        - Calculate `dp[j][l] = (prev_dp[j][l] * j + prefixSum) % MOD`.
        - Update `prefixSum = (prefixSum + prev_dp[j][l-1]) % MOD`.
    - After the inner loops, update `prev_dp = dp`.
- Sum up `prev_dp[j][k]` for all `j` from 1 to `m` to get the final answer.

# Solutions
### Java

```java
class Solution {
private
  static final int MOD = (int)1 e9 + 7;
public
  int numOfArrays(int n, int m, int k) {
    if (k == 0) {
      return 0;
    }
    long[][][] dp = new long[n + 1][k + 1][m + 1];
    for (int i = 1; i <= m; ++i) {
      dp[1][1][i] = 1;
    }
    for (int i = 2; i <= n; ++i) {
      for (int c = 1; c <= Math.min(i, k); ++c) {
        for (int j = 1; j <= m; ++j) {
          dp[i][c][j] = (dp[i - 1][c][j] * j) % MOD;
          for (int j0 = 1; j0 < j; ++j0) {
            dp[i][c][j] = (dp[i][c][j] + dp[i - 1][c - 1][j0]) % MOD;
          }
        }
      }
    }
    long ans = 0;
    for (int i = 1; i <= m; ++i) {
      ans = (ans + dp[n][k][i]) % MOD;
    }
    return (int)ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int numOfArrays(int n, int m, int k) {
    if (k == 0)
      return 0;
    int mod = 1e9 + 7;
    using ll = long long;
    vector<vector<vector<ll>>> dp(n + 1,
                                  vector<vector<ll>>(k + 1, vector<ll>(m + 1)));
    for (int i = 1; i <= m; ++i)
      dp[1][1][i] = 1;
    for (int i = 2; i <= n; ++i) {
      for (int c = 1; c <= min(i, k); ++c) {
        for (int j = 1; j <= m; ++j) {
          dp[i][c][j] = (dp[i - 1][c][j] * j) % mod;
          for (int j0 = 1; j0 < j; ++j0) {
            dp[i][c][j] = (dp[i][c][j] + dp[i - 1][c - 1][j0]) % mod;
          }
        }
      }
    }
    ll ans = 0;
    for (int i = 1; i <= m; ++i)
      ans = (ans + dp[n][k][i]) % mod;
    return (int)ans;
  }
};

```

### Python

```python
class Solution:
    def numOfArrays(self, n: int, m: int, k: int) -> int: if k == 0: return 0 dp = [[[0] * (m + 1) for _ in range(k + 1)] for _ in range(n + 1)] mod = 10 ** 9 + 7 for i in range(1, m + 1): dp[1][1][i] = 1 for i in range(2, n + 1): for c in range(1, min(k + 1, i + 1)): for j in range(1, m + 1): dp[i][c][j] = dp[i - 1][c][j] * j for j0 in range(1, j): dp[i][c][j] += dp[i - 1][c - 1][j0] dp[i][c][j] %= mod ans = 0 for i in range(1, m + 1): ans += dp[n][k][i] ans %= mod return ans

```