1420. Build Array Where You Can Find The Maximum Exactly K Comparisons

Problem Description

You are tasked with constructing an array arr of exactly n positive integers where each element is less than or equal to m. The goal is to have a search_cost equal to k when applying a specific algorithm. This algorithm finds the maximum element of the array by comparing each element with the current maximum. If an element is greater than the current maximum, it becomes the new maximum, and the search_cost increases by 1. The search_cost essentially counts the number of times an element has become the new maximum during the array traversal. Your objective is to count all the different ways you can build such an array under the given conditions.

To add some constraints and make the problem computationally interesting:

• The array arr has to have exactly n integers.
• Every integer arr[i] must satisfy the condition 1 <= arr[i] <= m, where (0 <= i < n).
• The algorithm applied to arr should result in a search_cost of exactly k.
• Since the number of ways can be very large, the answer should be returned modulo 10^9 + 7.

The challenge is to calculate the total number of different arrays that meet all these criteria.

Intuition

At first glance, the problem may seem daunting because of its combinatorial nature. However, dynamic programming (DP) is a powerful technique often used to tackle such problems.

The intuition for using DP in this scenario is to break down the problem into smaller subproblems and build up an answer based on the results of these subproblems. Specifically, we want to keep track of the number of valid arrays we can form for different array lengths, cost of searches, and maximum elements encountered so far. This is because at each step of building our array, we are either increasing the length of the array without changing the current maximum (so the cost remains the same), or we are inserting a new higher maximum, which increases the cost by one.

Here are the key insights:

1. We need to track the state as we add more elements. Our state includes the current length of the array, the number of times we have updated the maximum (cost), and the current maximum value.

2. We can use a three-dimensional DP table where:

   • dp[i][c][j] represents the number of valid arrays of length i, with a search_cost of c, and j as the maximum value in the array.

3. The base case of this DP table is that there's exactly one way to have an array of length 1 with a search_cost of 1 for each possible maximum value.

4. From there, we build up the solution iteratively, for each possible length of array, for each possible cost, and for each potential new maximum value.

5. Transition function:

   • If we keep the same maximum, we multiply the number of arrays of the previous length with the current maximum (dp[i - 1][c][j] * j), since all those arrays can be extended by any number not exceeding the current maximum.
   • If we are to increase the current maximum, we would iterate through all the possible previous maximums and add the arrays that end with that previous maximums to the current state (dp[i - 1][c - 1][j0]).

6. Finally, we sum up all the arrays of length n with a cost of k over all possible maximum values.

The implementation encapsulates this intuition and carefully calculates the sum modulo 10^9 + 7 to prevent integer overflow, which is a common issue with combinatorial numbers.

Learn more about Dynamic Programming and Prefix Sum patterns.

Solution Approach

The solution provided above utilizes dynamic programming (DP) to efficiently compute the number of valid arrays that can be built with the given constraints. The implementation follows a methodical progression that builds upon smaller subproblems to arrive at the final answer. Let's break down the steps involved in the implementation:

1. Initialization: A three-dimensional DP array dp is created to store the number of ways to construct arrays of various lengths, costs, and maximum values:

   • dp[i][c][j] is the number of arrangements of length i, with a search_cost of c, and j as the current highest number in the array.

2. Modulo Constant: The solution calculates answers modulo 10^9 + 7 (mod) to handle large numbers and avoid integer overflow issues.

3. Base Case: The base cases of the DP are set up, where we know that for an array of length 1 and a search_cost of 1, there's exactly one way to set each number as the maximum; this is represented by setting dp[1][1][i] = 1 for all i in 1 <= i <= m.

4. Iterative Computation: The solution iteratively calculates the number of ways we can add an element to an existing array based on the previous states. This uses two key sub-transitions:

   • If the new element added to the array is less than or equal to the current maximum (no cost increase), then the current DP value is incremented by the product of the number of ways to form an array of the previous length with the current maximum and the value of the current maximum (dp[i - 1][c][j] * j). This reflects all the ways an array can extend by adding any number up to the current maximum.
   • If the new element is greater than the current maximum (cost increases by 1), the solution iterates over all smaller maximums (j0), summing up the results from the corresponding DP values (dp[i - 1][c - 1][j0]). The new array is now longer by one, the cost has increased by 1 because a new maximum has been set, and all arrays with a maximum of j0 can be extended by adding j.

5. Applying Modulo Operation: After each addition in the iterative computation step, the solution takes the modulo of the result to ensure the values stay within the integer range and adhere to the constraints of the problem.

6. Answer Aggregation: Once all possible arrays with lengths up to n, costs up to k, and maximum values up to m have been considered, the solution sums up all the DP values for arrays of length n with a cost of k to get the total number of valid arrays. Again, the modulo operation is applied to obtain the answer under the aforementioned constraints.

7. Return Final Answer: The aggregated sum represents the total number of valid ways to build the array with the given constraints, and it is returned as the final answer to the problem.

The solution capitalizes on the principles of dynamic programming to explore the entire solution space by reusing previously computed states and building on them. This avoids the computational inefficiency of recalculating subproblems, which is evident in naive recursive solutions.

Example Walkthrough

Let us consider an example where n=3, m=3, and k=2. This means we want to form arrays of length 3 from numbers 1 to 3 inclusive, and we want our search_cost to be exactly 2.

Let's follow the steps of the DP solution approach for this scenario:

Step 1: Initialization We initialize a 3D DP array, denoted by dp[i][c][j].

Step 2: Base Case For the base case, we set dp[1][1][j] = 1 for every j in 1 <= j <= m, since there's one way to form a length 1 array with a search_cost of 1.

For our case, m=3, so we have: dp[1][1][1] = 1 dp[1][1][2] = 1 dp[1][1][3] = 1

Step 3: Iterative Computation We iterate through lengths i, costs c, and possible maximums j starting from these base cases.

Since we have our base cases for length 1, we start building on that for length 2. We are looking for arrays with a cost of 2, which means the maximum must be updated exactly once.

No cost increase: If we are at dp[2][1][j], the second element can be any number from 1 to j without increasing the cost.

Cost increase: If we are at dp[2][2][j], it means we need to update our maximum. Hence, we must add 1 to the number of ways we could form a sequence of length 1 with a cost of 1 for all numbers less than j.

Example:

• For j=2, dp[2][2][2] includes counts from dp[1][1][1] because it means we have a sequence with one 1 and we're adding a 2, updating our maximum.
• Similarly, for j=3, dp[2][2][3] includes counts from dp[1][1][1] and dp[1][1][2].

Moving to i=3, the final length, we keep calculating similarly, where:

• For no cost increase, we continue with the possible maximums we added last time, which would keep the last maximum we had.
• For cost increase, we look back at the previous smaller maximums and consider ways to form an array of length 2 with these maximums.

Step 4: Applying Modulo Operation Through every addition, we take care of the modulo operation to avoid overflow issues.

Step 5: Answer Aggregation We sum up all dp[n][k][j] for all j=1 to m to get the total counts, where n=3 and k=2.

For our example, we aggregate counts from: dp[3][2][1], dp[3][2][2], and dp[3][2][3]

Step 6: Return Final Answer The sum of these values gives us the number of arrays of length 3, with numbers from 1 to 3, and a search cost of 2.

Through the process, this example provides a clear illustration of the solution approach utilizing dynamic programming to count the number of ways arrays can be created under the given constraints.

Solution Implementation

Time and Space Complexity

Time Complexity

The given code consists of nested loops which directly affect the time complexity. Here's how each contributes:

• The first for loop initializes dp[1][1][i] for i in range 1 to m + 1, which runs m times.

• There are two more nested loops wherein:

  • The outermost loop runs n - 1 times (2 to n).
  • The second loop runs at most k times because c ranges from 1 to min(k + 1, i + 1).
  • The innermost loop runs m times, ranging from 1 to m + 1.

  The innermost part of these loops contains computations that occur in constant time and another loop over j0 which runs at most m - 1 times. Therefore, the time complexity of this section is O(n * k * m^2).

• The last for loop sums up dp[n][k][i] for 1 to m + 1, which adds another O(m) to the computation.

Combining these, the dominating factor in the time complexity is O(n * k * m^2), as it would be the most significant for large inputs.

Space Complexity

The space complexity is determined by the size of the dynamic programming table dp which has dimensions (n + 1) * (k + 1) * (m + 1). Thus, the space complexity is O(n * k * m).

In summary:

• Time Complexity: O(n * k * m^2)
• Space Complexity: O(n * k * m)

Learn more about how to find time and space complexity quickly using problem constraints.