198.House Robber

Posted on | In

Test cases

1
2
3
4
5
6
7
8
9
[]
[1,2]
[2,1]
[1,3,2]
[1,2,3]
[1,2,3,4,5,6,7]
[7,6,5,4,3,2,1]
[1,0,3,5,6,4,1,4,2,9,5,8]
[1,0,3,5,6,4,1,4,2,9,5,8,6]

Solution 1: accepted 0ms

DP: To calculate the total gain after robbing house number N, we need to consider the accumulated stash of house N-2 or N-3. N-1 is not available as it will trigger the alarm.
Time: O(n)

1
2
3
4
5
6
7
8
9
10
11
public int rob(int[] nums) {
        int len = nums.length;
        if (len == 0) return 0;
        if (len == 1) return nums[0];
        if (len > 2)
            nums[2] = Math.max(nums[0] + nums[2], nums[1]);
        for(int i = 3; i < len; i++) {
            nums[i] = Math.max(nums[i] + nums[i-2], nums[i] + nums[i-3]);
        }
        return Math.max(nums[len-1], nums[len-2]);
    }

Or convert to Space O(1) by storing two previous stashes in two int variables.

Solution 2: accepted 0ms

More elegant code.

1
2
3
4
5
6
7
8
9
10
11
12
public class Solution {
    public int rob(int[] nums) {
        int doit = 0; // total stash if we do rob the current house
        int dont = 0; // total stash if don't rob the current house
        for(int i = 0; i < nums.length; i++) {
            int current = dont + nums[i];
            dont = Math.max(doit, dont);
            doit = current;
        }
        return Math.max(dont, doit);
    }
}