Build Array Where You Can Find The Maximum Exactly K Comparisons
HardPrompt
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:
arrhas exactlynintegers.1 <= arr[i] <= mwhere(0 <= i < n).- After applying the mentioned algorithm to
arr, the valuesearch_costis equal tok.
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 <= 501 <= m <= 1000 <= k <= n
Approaches
3 approaches with complexity analysis and trade-offs.
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).
Algorithm
- Initialize a 3D DP table
dp[n+1][m+1][k+1]. - Set base cases:
dp[1][j][1] = 1forjfrom 1 tom. - Iterate
ifrom 2 ton(length of array). - Iterate
lfrom 1 tok(cost). - Initialize
prefixSum = 0. - Iterate
jfrom 1 tom(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.
- Calculate
- Sum up
dp[n][j][k]for alljfrom 1 tomto get the final answer.
Walkthrough
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 firsti-1elements was alreadyj, and thei-th element is chosen from1, ..., j. There arejchoices for thei-th element. The number of ways isdp[i-1][j][l] * j. - Case 2: The
i-th element is a new maximum, and its value isj. This means the maximum of the firsti-1elements was some valuep < j, and the cost for the prefix wasl-1. The number of ways is the sum ofdp[i-1][p][l-1]for allpfrom1toj-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.
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; }}Complexity
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.
Trade-offs
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.
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).
Algorithm
- Initialize a 2D array
prev_dp[m+1][k+1]. - Set base cases for
i=1:prev_dp[j][1] = 1forjfrom 1 tom. - Iterate
ifrom 2 ton.- Initialize a new 2D array
dp[m+1][k+1]. - Iterate
lfrom 1 tok. - Initialize
prefixSum = 0. - Iterate
jfrom 1 tom.- Calculate
dp[j][l] = (prev_dp[j][l] * j + prefixSum) % MOD. - Update
prefixSum = (prefixSum + prev_dp[j][l-1]) % MOD.
- Calculate
- After the inner loops, update
prev_dp = dp.
- Initialize a new 2D array
- Sum up
prev_dp[j][k]for alljfrom 1 tomto get the final answer.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
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.
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 ifcost == k, else 0. Ifcost > 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
valfromcurrent_max + 1tom:count += solve(i + 1, val, cost + 1). - Store
count % MODin the memo table and return it.
- Check for base cases: if
- Start the process by calling
solve(0, 0, 0).
Walkthrough
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:
i: The current index in the array to be filled (from0ton).current_max: The maximum value found in the array prefixarr[0...i-1].cost: The search cost accumulated so far.
Base Cases:
- If
cost > k, it's impossible to achieve a final cost ofk, so we return 0. - If
i == n, we have filled the entire array. Ifcost == 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 forarr[i]from1tom. - Option 1: Choose
arr[i]such that1 <= arr[i] <= current_max. This does not increase the search cost. There arecurrent_maxsuch choices. The number of ways for this option iscurrent_max * solve(i + 1, current_max, cost). - Option 2: Choose
arr[i]such thatcurrent_max < arr[i] <= m. This increases the search cost by 1. For each choicejin this range, the new maximum becomesj. The number of ways is the sum ofsolve(i + 1, j, cost + 1)for alljfromcurrent_max + 1tom.
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).
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; }}Complexity
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`.
Trade-offs
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
mtimes.
Solutions
Solution
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; }}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; }};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 ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.