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).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 <= 501 <= m <= 1000 <= k <= nThe key idea in #1420 Build Array Where You Can Find The Maximum Exactly K Comparisons is to simulate the process of building an array while tracking how many times the maximum value changes. Each time a new element becomes the largest seen so far, it counts as a comparison that increases the search cost.
A common approach uses dynamic programming. Let dp[i][j][c] represent the number of arrays of length i where the current maximum is j and the search cost is c. When adding a new element, there are two choices: choose a value ≤ current maximum (which keeps the cost unchanged) or choose a larger value (which increases the cost by one and updates the maximum).
To efficiently compute transitions for larger maximum values, prefix sums are used to aggregate previous states. This reduces repeated summations and keeps the solution efficient for the given constraints. The final answer is obtained by summing valid states for arrays of length n with exactly k comparisons.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming with Prefix Sum Optimization | O(n × m × k) | O(n × m × k) |
codestorywithMIK
Use these hints if you're stuck. Try solving on your own first.
Use dynamic programming approach. Build dp table where dp[a][b][c] is the number of ways you can start building the array starting from index a where the search_cost = c and the maximum used integer was b.
Recursively, solve the small sub-problems first. Optimize your answer by stopping the search if you exceeded k changes.
We can use dynamic programming to solve this problem by maintaining a 3D array where dp[i][j][k] represents the number of ways to construct an array of length i, with values up to j and exactly k comparisons.
Recurrence relations can be defined by considering whether you want to extend the array by a value that does or doesn't increase the number of comparisons. Use modulo operations to manage large numbers.
Time Complexity: O(n * m^2 * k). Space Complexity: O(n * m * k).
1#include <vector>
2using namespace std;
3
4const int MOD = 1000000007;
5
6int numOfArrays(int n, int m, int k) {
7 vector<vector<vector<int>>> dp(n+1, vector<vector<int>>(m+1, vector<int>(k+1, 0)));
8 for (int j = 1; j <= m; ++j) dp[1][j][1] = 1;
9 for (int i = 2; i <= n; ++i) {
10 for (int j = 1; j <= m; ++j) {
11 for (int z = 1; z <= k; ++z) {
12 dp[i][j][z] = ((long long)j * dp[i-1][j][z]) % MOD;
13 for (int p = 1; p < j; ++p) {
14 dp[i][j][z] = (dp[i][j][z] + dp[i-1][p][z-1]) % MOD;
15 }
16 }
17 }
18 }
19 int totalWays = 0;
20 for (int j = 1; j <= m; ++j) {
21 totalWays = (totalWays + dp[n][j][k]) % MOD;
22 }
23 return totalWays;
24}
25Following a similar pattern, the C++ solution uses nested loops to iterate over the dimensions of the problem. The outer loop iterates over the number of elements, the second outer loop iterates over the possible maximum value, and the innermost loop iterates over the number of comparisons. At each step, it calculates solutions based on whether the current number extends the max for the count of comparisons or fits in the current max formed so far.
This approach uses recursion with memoization to avoid recomputing the solutions for subproblems. The recursive function attempts to build the array incrementally by deciding, step by step, which value to add, and whether it will increase the maximum so far. By caching previously computed results, it reduces repeated calculations.
Time Complexity: O(n * m * k). Space Complexity: O(n * m * k) due to recursion stack and memoization storage.
1import java.util.*;
2
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Prefix sums are commonly used to optimize transitions between DP states. They allow quick aggregation of previous maximum states, reducing repeated summations and improving performance.
Yes, variations of this problem appear in high-level coding interviews because it combines dynamic programming, state transitions, and optimization techniques like prefix sums.
The optimal approach uses dynamic programming to track array length, current maximum value, and the number of comparisons made so far. Prefix sums are applied to efficiently compute transitions when introducing new maximum values.
Dynamic programming helps model how arrays grow step by step while keeping track of the current maximum and comparison count. It avoids recomputation by storing intermediate states for all valid combinations.
The Java solution initializes a 3D memoization table filled with -1 (uncomputed states) and recursively defines valid states for the dynamic structure of the array. It traverses through not only possible values to append but also considers whether adding the value modifies the comparison metric used (k comparisons).