Scale Engineer

Build Array Where You Can Find The Maximum Exactly K Comparisons

Hard
#1314Time: 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.2 companies
Patterns
Dynamic ProgrammingPrefix Sum
Companies
AmdocsDunzo

Prompt

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).
  • 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

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] = 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.

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 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.

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.

Solutions

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;  }}

Video 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.

← Previous

Previous problem

Next →

Next problem