LeetCode Entry
1340. Jump Game V
Max visited by jumping down in distance d
1340. Jump Game V hard substack youtube
https://dmitrysamoylenko.com/leetcode/
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/1369
Problem TLDR
Max visited by jumping down in distance d
Intuition
- Top-down DP: dfs from each index to the left and to the right by d distance, memo by i
- Bottom-up DP: iterate in increasing value order to safely use previous results because we only jump down
-
O(N) solution: use decreasing stack, track left peak, pop smaller valleys and update m[left_peak right_peak]=max(m[popped]+1),
Approach
- for monotonic we have to track left peaks becasue of the duplicates
Complexity
-
Time complexity: \(O(nd|n)\)
-
Space complexity: \(O(n)\)
Code
fun maxJumps(a: IntArray, d: Int) = IntArray(a.size).let { m ->
a.indices.sortedBy{a[it]}.maxOf { i ->
m[i] = 1+setOf(i-1 downTo i-d,i+1..i+d).maxOf {
it.takeWhile{a.getOrNull(it)?:a[i]<a[i]}.maxOfOrNull{m[it]}?:0};m[i]}}
pub fn max_jumps(a: Vec<i32>, d: i32) -> i32 {
let(d,n)=(d as usize,a.len());let mut m=vec![1;n];let mut s:Vec<(usize,usize)>=vec![];
for (&v,i) in a.iter().chain([&99999]).zip(0..) {
while let Some(&(j, l)) = s.last() && a[j] < v { s.pop();
if i < n && i - j <= d { m[i] = m[i].max(m[j] + 1) }
if l < n && j - l <= d { m[l] = m[l].max(m[j] + 1) }
}
s.push((i,s.last().map_or(n,|&(k,l)|if a[k]>v {k} else {l})))
} m.into_iter().max().unwrap()
}