21.01.2024
198. House Robber medium
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/479
Problem TLDR
Max sum to rob non adjacent items in array.
Intuition
Let’s inspect how robber acts by scanning array home by home:
// 2 7 9 3 1
// 2 max(2) = 2
// 7 max(7, 2) = 7
// b a 9 max(9 + b, a) = 11
// b a 3 max(3 + b, a) = 11
// b a 1 max(1 + b, a) = 12
We see that he can choose to take the current home and drop the previous, or keep the previous. Only the two last sums matter.
Approach
save some lines of code by using
fold
Complexity
Time complexity:
O(n)Space complexity:
O(1)
Code
fun rob(nums: IntArray): Int {
var b = 0
return nums.fold(0) { a, x ->
max(x + b, a).also { b = a }
}
}
pub fn rob(nums: Vec<i32>) -> i32 {
nums.iter().fold((0, 0), |(a, b), &x| (b, b.max(a + x))).1
}