1420. Build Array Where You Can Find The Maximum Exactly K Comparisons
On This Page
In this problem, we have three integers,
k. We need to construct an array
arr having the following properties:
- It consists of exactly
- Each integer in the array is between
- After executing a certain algorithm on
arr, we get a value known as
search_cost. Our goal is to ensure
search_costis equal to
The main challenge is determining how many ways we can construct such an array
A naive approach might involve generating all possible array combinations, then determining which ones fulfill our criteria. This method, however, would be inefficient due to its exponential time complexity. Given the constraints, this naive method won’t be feasible.
Hints & Tips
- Utilize dynamic programming to avoid recalculating overlapping subproblems.
- Keeping track of the maximum value encountered so far can help narrow down the possible outcomes.
Approach / Idea
To tackle this problem efficiently, we use dynamic programming. The main idea is to maintain a three-dimensional
dp array, which keeps track of:
- Current length of the array we’re constructing (
- The maximum value used so far (
- Remaining comparisons (
With this DP table, we can progressively compute how many ways we can construct an array of length
i while meeting our conditions.
Steps / High-Level Algorithm
Initialize the DP Array: Create a three-dimensional
dparray filled with zeros.
Base Case: When the array length equals
n, the possible values for
max_so_farare already decided, hence set
Fill the DP Table:
- Iterate backwards, starting from the end towards the beginning.
- For each
i, determine the number of ways we can construct an array of that length based on
Note: This is where the majority of the dynamic programming logic comes into play.
Calculate the Result: Once the DP table is complete,
dp[k]contains the number of ways we can construct the array.
Here’s the python code:
class Solution: def numOfArrays(self, n: int, m: int, k: int) -> int: dp = [[ * (k + 1) for _ in range(m + 1)] for __ in range(n + 1)] MOD = 10 ** 9 + 7 for num in range(len(dp)): dp[n][num] = 1 for i in range(n - 1, -1, -1): for max_so_far in range(m, -1, -1): for remain in range(k + 1): ans = (max_so_far * dp[i + 1][max_so_far][remain]) % MOD if remain > 0: for num in range(max_so_far + 1, m + 1): ans = (ans + dp[i + 1][num][remain - 1]) % MOD dp[i][max_so_far][remain] = ans return dp[k]