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.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

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

1class Solution:
2    def numOfArrays(self, array_length: int, max_value: int, search_cost: int) -> int:
3        # If search_cost is zero, it's not possible to create an array as we can't have any search costs.
4        if search_cost == 0:
5            return 0
6      
7        # Initialize a 3D dynamic programming array to store subproblem solutions
8        # dp[length][cost][value] gives number of ways to create an array of `length` where `cost` is the cost incurred and `value` is max value in the array        
9        dp = [[[0] * (max_value + 1) for _ in range(search_cost + 1)] for _ in range(array_length + 1)]
10      
11        # Define the modulus value for large numbers to prevent integer overflow
12        mod = 10**9 + 7
13      
14        # Base case initialization: An array of length 1 with cost 1 and varying max value
15        for value in range(1, max_value + 1):
16            dp[1][1][value] = 1
17      
18        # Iterate over array lengths
19        for length in range(2, array_length + 1):
20            # Iterate over costs; the cost cannot exceed the length of the array
21            for cost in range(1, min(search_cost + 1, length + 1)):
22                # Iterate over possible max values
23                for value in range(1, max_value + 1):
24                    # Ways to create an array of current length by appending a number not greater than current value
25                    dp[length][cost][value] = dp[length - 1][cost][value] * value
26                  
27                    # Add ways to create an array where current number is the new max value, which increases cost by 1
28                    for prev_value in range(1, value):
29                        dp[length][cost][value] += dp[length - 1][cost - 1][prev_value]
30                        # Apply modulus to keep the number within the bounds
31                        dp[length][cost][value] %= mod
32      
33        # Calculate the final answer by summing over all the ways to make arrays of `array_length` with max values ranging from 1 to `max_value`
34        ans = 0
35        for value in range(1, max_value + 1):
36            ans += dp[array_length][search_cost][value]
37            # Apply modulus to keep the number within the bounds
38            ans %= mod
39      
40        # Return the total number of ways to create the array as per the given conditions
41        return ans
42
1class Solution {
2    // Define a constant for the modulo operation.
3    private static final int MOD = (int) 1e9 + 7;
4
5    public int numOfArrays(int n, int m, int k) {
6        // If k is 0, there are no valid arrays.
7        if (k == 0) {
8            return 0;
9        }
10
11        // Create a 3D dynamic programming array.
12        // dp[length][searchCost][maxValue] holds the number of arrays of that configuration.
13        long[][][] dp = new long[n + 1][k + 1][m + 1];
14      
15        // Base case: For any maxValue, there is one array of length 1 with searchCost 1.
16        for (int maxValue = 1; maxValue <= m; ++maxValue) {
17            dp[1][1][maxValue] = 1;
18        }
19      
20        // Iterate over the length of the arrays.
21        for (int length = 2; length <= n; ++length) {
22            for (int searchCost = 1; searchCost <= Math.min(length, k); ++searchCost) {
23                // Iterate over all possible maxValues.
24                for (int maxValue = 1; maxValue <= m; ++maxValue) {
25                    // For the same maxValue, we can append elements from 1 to maxValue and stay within the searchCost.
26                    dp[length][searchCost][maxValue] = (dp[length - 1][searchCost][maxValue] * maxValue) % MOD;
27
28                    // We need to check all previous maxValues that are less than the current one
29                    // since appending the current maxValue will increase the searchCost by 1.
30                    for (int prevMaxValue = 1; prevMaxValue < maxValue; ++prevMaxValue) {
31                        dp[length][searchCost][maxValue] = (dp[length][searchCost][maxValue] + dp[length - 1][searchCost - 1][prevMaxValue]) % MOD;
32                    }
33                }
34            }
35        }
36      
37        // Calculate the final answer as the sum of all configurations with the full length, highest searchCost, and all maxValues.
38        long ans = 0;
39        for (int maxValue = 1; maxValue <= m; ++maxValue) {
40            ans = (ans + dp[n][k][maxValue]) % MOD;
41        }
42      
43        // Cast the long result to int before returning.
44        return (int) ans;
45    }
46}
47
1class Solution {
2public:
3    int numOfArrays(int n, int m, int k) {
4        const int MOD = 1e9 + 7; // Using a constant for the modulo value
5
6        // If the search cost is zero, it's impossible to construct the array
7        if (k == 0) return 0;
8
9        // Using long long for large calculations to avoid overflow
10        using ll = long long;
11
12        // Declaring a dynamic programming table that will store the count of arrays
13        // dp[i][c][j] represents the number of ways to construct an array of length i,
14        // with search cost c and maximum element j
15        vector<vector<vector<ll>>> dp(n + 1, vector<vector<ll>>(k + 1, vector<ll>(m + 1)));
16
17        // Base case initialization: if there's only 1 element, that's the maximum and search cost is 1
18        for (int maxVal = 1; maxVal <= m; ++maxVal) {
19            dp[1][1][maxVal] = 1;
20        }
21
22        // Fill in the dynamic programming table
23        for (int length = 2; length <= n; ++length) {
24            for (int searchCost = 1; searchCost <= min(length, k); ++searchCost) {
25                for (int maxVal = 1; maxVal <= m; ++maxVal) {
26                    // If we're not increasing the max value, multiply the number of ways
27                    dp[length][searchCost][maxVal] = (dp[length - 1][searchCost][maxVal] * maxVal) % MOD;
28
29                    // Iterate over all smaller max values from previous length to increase the max value,
30                    // effectively increasing the search cost by 1
31                    for (int prevMaxVal = 1; prevMaxVal < maxVal; ++prevMaxVal) {
32                        dp[length][searchCost][maxVal] = (dp[length][searchCost][maxVal] + dp[length - 1][searchCost - 1][prevMaxVal]) % MOD;
33                    }
34                }
35            }
36        }
37
38        // Calculate the final result by summing up all the ways to form the array
39        // with the full length n, search cost k, and any max value
40        ll result = 0;
41        for (int maxVal = 1; maxVal <= m; ++maxVal) {
42            result = (result + dp[n][k][maxVal]) % MOD;
43        }
44
45        // Return the result casted to integer
46        return static_cast<int>(result);
47    }
48};
49
1const MOD: number = 1e9 + 7; // Using a constant for the modulo value
2
3function numOfArrays(n: number, m: number, k: number): number {
4    if (k === 0) return 0; // If search cost is zero, it's impossible to construct the array
5
6    // Declare a 3D array that will store the count of arrays
7    // dp[i][c][j] represents the number of ways to construct an array of length i,
8    // with search cost c and maximum element j
9    let dp: number[][][] = Array.from({ length: n + 1 }, () =>
10        Array.from({ length: k + 1 }, () => Array(m + 1).fill(0))
11    );
12
13    // Base case: if there's only 1 element, that element is the maximum, search cost is 1
14    for (let maxVal = 1; maxVal <= m; ++maxVal) {
15        dp[1][1][maxVal] = 1;
16    }
17
18    // Fill in the dp table
19    for (let length = 2; length <= n; ++length) {
20        for (let searchCost = 1; searchCost <= Math.min(length, k); ++searchCost) {
21            for (let maxVal = 1; maxVal <= m; ++maxVal) {
22                // If we're not increasing the max value, multiply the number of ways
23                dp[length][searchCost][maxVal] = (dp[length - 1][searchCost][maxVal] * maxVal) % MOD;
24
25                // Iterate over all smaller max values from the previous length to increase the max value,
26                // effectively increasing the search cost by 1
27                for (let prevMaxVal = 1; prevMaxVal < maxVal; ++prevMaxVal) {
28                    dp[length][searchCost][maxVal] += dp[length - 1][searchCost - 1][prevMaxVal];
29                    dp[length][searchCost][maxVal] %= MOD;
30                }
31            }
32        }
33    }
34
35    // Calculate the final result by summing up all the ways to form the array
36    // with full length n, search cost k, and any max value
37    let result: number = 0;
38    for (let maxVal = 1; maxVal <= m; ++maxVal) {
39        result = (result + dp[n][k][maxVal]) % MOD;
40    }
41
42    return result;
43}
44

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.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?


Recommended Readings

Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.