Hard

Quiz

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

APPROACH

Given integers n, m, and k, count arrays arr of length n with each element in [1, m] such that when you scan arr left to right looking for the running maximum, the number of times you see a new maximum (i.e., search_cost) is exactly k. Return the count modulo 10⁹ + 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]

1 of 4

1:00

What is the optimal approach for this problem?