# 7.10.2023 [1420. Build Array Where You Can Find The Maximum Exactly K Comparisons]
Count possible arrays of n `1..m` values increasing `k` times
7.10.2023
1420. Build Array Where You Can Find The Maximum Exactly K Comparisons hard
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/362
Problem TLDR
Count possible arrays of n 1..m
values increasing k
times
Intuition
First, try to write down some examples of arrays. There are some laws of how the number of arrays grows.
Next, use hint :)
Then just write Depth First Search of all possible numbers for each position and count how many times numbers grows. Stop search when it is bigger than k
times. The result can be cached.
Approach
use Long to avoid overflows
Complexity
Time complexity:
O(nkm2), nkm - is a search depth, and another m for internal loopSpace complexity:
O(nkm)
Code
fun numOfArrays(n: Int, m: Int, k: Int): Int {
val mod = 1_000_000_007L
val dp = Array(n) { Array(m + 1) { Array(k + 1) { -1L } } }
fun dfs(i: Int, max: Int, c: Int): Long =
if (c > k) 0L
else if (i == n) { if (c == k) 1L else 0L }
else dp[i][max][c].takeIf { it >= 0 } ?: {
var sum = (max * dfs(i + 1, max, c)) % mod
for (x in (max + 1)..m)
sum = (sum + dfs(i + 1, x, c + 1)) % mod
sum
}().also { dp[i][max][c] = it }
return dfs(0, 0, 0).toInt()
}