LeetCode Entry
3363. Find the Maximum Number of Fruits Collected
Max 3 paths from corners to bottom end
3363. Find the Maximum Number of Fruits Collected hard
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/1073
Problem TLDR
Max 3 paths from corners to bottom end #hard
Intuition
Used the hints.
Two insights:
- middle only goes diagonal
- two other guys are the two separate searches
// dfs or bfs?
// greedy? - i think can be non-optimal
// either full search with bfs or dp with dfs+cache
// 3x3x3 = 27 steps by each bfs layer
// exactly n-1 steps AND reach n,n cell - no non-optimal steps
// i am writing the dfs+dp, the growth factor is n^27
// let's use hints
// nice, child 0 can only move diagonal (as by rules)
// child 1&2 can't cross diagonal
// my solution TLE
// look for other hints, no new information
// are we expected use raw arrays? bottom up?
// expected bottom up
// children b and c can go separate
Approach
Complexity
-
Time complexity: \(O(n^2)\)
-
Space complexity: \(O(n^2)\)
Code
// 697ms
fun maxCollectedFruits(f: Array<IntArray>, n: Int = f.lastIndex): Int {
data class P(val x: Int, val y: Int) { val i = x < 0 || y < 0 || x > n || y > n }
fun dfs(p: P, d: List<Int>, dp: HashMap<P, Int> = HashMap()): Int = dp.getOrPut(p) {
f[p.y][p.x] + (0..2).maxOf {
val b = P(p.x + d[it*2], p.y + d[it*2 + 1])
if (!b.i && (b.y - b.x).sign == d[2].sign) dfs(b, d, dp) else 0
}}
val b = listOf(1, 1, -1, 1, 0, 1); val c = listOf(1, 0, 1, 1, 1, -1)
return dfs(P(n, 0), b) + dfs(P(0, n), c) + (0..n).sumOf { f[it][it] }
}