LeetCode Entry
198. House Robber
Max sum to rob non adjacent items in array.
198. House Robber medium
blog post
substack
youtube
https://youtu.be/UeejjxR-skM
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) =
nums.fold(0 to 0) { (a, b), x -> max(x + b, a) to a }.first
pub fn rob(nums: Vec<i32>) -> i32 {
nums.iter().fold((0, 0), |(a, b), &x| (b, b.max(a + x))).1
}