#1420

Build Array Where You Can Find The Maximum Exactly K Comparisons

expert · 1065 · lc hard +32 · verified · 65.9% accepted · 1,461 likes · top 71%

Description

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]

Code

1

2

3

class Solution:
    def numOfArrays(self, n: int, m: int, k: int) -> int:

class Solution:
    def numOfArrays(self, n: int, m: int, k: int) -> int: