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

LeetCode Problem 1420

Difficulty: 🔴 Hard
Topics: Dynamic Programming, Prefix Sum

Solution

Problem Understanding

This problem asks us to count the number of arrays of length n where each element is between 1 and m inclusive, and the "search cost" for finding the maximum element is exactly k. The search cost is defined as the number of times a new maximum is found when iterating through the array from left to right.

In other words, we are asked to generate arrays and track the number of times the current maximum increases. The input consists of three integers: n is the array length, m is the maximum value an element can take, and k is the exact number of times the maximum should increase. The output is the count of arrays satisfying these conditions, modulo 10^9 + 7.

Constraints indicate that n is up to 50 and m is up to 100. This suggests that brute-force generation of all possible arrays is infeasible because the total number of arrays is m^n, which can be astronomically large. Edge cases include k = 0 (impossible if n > 0), m = 1 (all elements must be 1), and k > n (impossible).

Approaches

A brute-force approach would attempt to generate all possible arrays of length n with values 1 to m, compute the search cost for each, and count the ones where the search cost equals k. While this approach is straightforward, it is too slow: generating m^n arrays is not feasible for the upper bounds of n and m.

The key insight for an optimal approach is to recognize that this problem can be solved using dynamic programming. The state can be defined as dp[i][j][c] representing the number of arrays of length i with maximum value j and search cost c. For each array position, we can either pick a value less than or equal to the current maximum (which does not increase the search cost) or pick a value greater than the current maximum (which increases the search cost by 1). Using this DP formulation, we can efficiently count all valid arrays without generating them explicitly.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(m^n)	O(1)	Generate all arrays, check search cost, infeasible for large n and m
Optimal (DP)	O(n * m * k)	O(n * m * k)	Dynamic programming over array length, max value, and cost; feasible given constraints

Algorithm Walkthrough

1. Define a 3D DP array dp[i][j][c] representing the number of arrays of length i, maximum value j, and search cost c.

2. Initialize the base case: for arrays of length 1, dp[1][j][1] = 1 for all 1 <= j <= m because a single element array has a search cost of 1.

3. Iterate over lengths i from 2 to n.

4. For each length i, iterate over all possible maximum values j from 1 to m.

5. For each search cost c from 1 to k:

6. Add contributions from arrays where the next element is less than or equal to the current maximum j. In this case, the search cost does not increase. This adds dp[i-1][j][c] * j because there are j choices for the new element.

7. Add contributions from arrays where the next element is greater than the current maximum. In this case, the search cost increases by 1. For each p less than j, add dp[i-1][p][c-1].

8. After filling the DP table, sum dp[n][j][k] over all 1 <= j <= m to get the total number of valid arrays.

9. Return the result modulo 10^9 + 7.

Why it works: The DP correctly counts arrays by building them one element at a time, maintaining the current maximum and search cost as state. Each transition either increases the search cost or keeps it the same, ensuring all valid arrays are counted exactly once.

Python Solution

class Solution:
    def numOfArrays(self, n: int, m: int, k: int) -> int:
        MOD = 10**9 + 7
        
        dp = [[[0] * (k+1) for _ in range(m+1)] for _ in range(n+1)]
        
        for j in range(1, m+1):
            dp[1][j][1] = 1
        
        for i in range(2, n+1):
            for j in range(1, m+1):
                for c in range(1, k+1):
                    # Case 1: adding element <= current max j
                    dp[i][j][c] += dp[i-1][j][c] * j
                    dp[i][j][c] %= MOD
                    # Case 2: adding element > current max
                    for p in range(1, j):
                        dp[i][j][c] += dp[i-1][p][c-1]
                        dp[i][j][c] %= MOD
        
        result = sum(dp[n][j][k] for j in range(1, m+1)) % MOD
        return result

The code initializes a 3D DP array and fills it according to the rules outlined above. For each length, maximum, and cost, it counts arrays that either maintain the current maximum or increase it. Modular arithmetic ensures values do not overflow.

Go Solution

func numOfArrays(n int, m int, k int) int {
    const MOD int = 1e9 + 7
    dp := make([][][]int, n+1)
    for i := range dp {
        dp[i] = make([][]int, m+1)
        for j := range dp[i] {
            dp[i][j] = make([]int, k+1)
        }
    }
    
    for j := 1; j <= m; j++ {
        dp[1][j][1] = 1
    }
    
    for i := 2; i <= n; i++ {
        for j := 1; j <= m; j++ {
            for c := 1; c <= k; c++ {
                dp[i][j][c] = (dp[i-1][j][c] * j) % MOD
                for p := 1; p < j; p++ {
                    dp[i][j][c] = (dp[i][j][c] + dp[i-1][p][c-1]) % MOD
                }
            }
        }
    }
    
    result := 0
    for j := 1; j <= m; j++ {
        result = (result + dp[n][j][k]) % MOD
    }
    return result
}

Go handles slices explicitly, so the 3D DP array is built with nested slices. Modular arithmetic ensures the result does not overflow 32-bit integers.

Worked Examples

Example 1: n = 2, m = 3, k = 1

Initialize dp[1][j][1] = 1 for j=1,2,3.

Length 2, cost 1:

• j=1: can add 1 (<=1), dp[2][1][1] = dp[1][1][1] * 1 = 1
• j=2: add <=2 → 1,2; add > previous max 1 → dp[2][2][1] = 1*2 + dp[1][1][0] = 2
• j=3: similar logic

Sum over dp[2][1][1] + dp[2][2][1] + dp[2][3][1] = 6

Example 2: n=5, m=2, k=3 → DP will never reach cost 3, result 0.

Example 3: n=9, m=1, k=1 → Only array is all ones, result 1.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n * m * m * k)	For each length, max, and cost, we loop over previous max values < j
Space	O(n * m * k)	3D DP array storing counts for all lengths, max values, and costs

Optimization is possible by precomputing prefix sums to reduce the inner loop over p from O(m) to O(1), making time O(n * m * k).

Test Cases

# Example cases
assert Solution().numOfArrays(2, 3, 1) == 6  # basic case
assert Solution().numOfArrays(5, 2, 3) == 0  # impossible cost
assert Solution().numOfArrays(9, 1, 1) == 1  # single value array

# Edge cases
assert Solution().numOfArrays(1, 1, 1) == 1  # smallest array
assert Solution().numOfArrays(50, 100, 50) >=