Easy to Understand Solution in Java - O(n) time and O(1) space - 1ms

  • 1

    The solution is almost the same as the House Robber I solution, except this:

    1. If the first house is robbed, the max at the end (at n=nums.length) has to be the same as it was at n-1.
    2. If the first house is not robbed, the max at n=1 is 0 and we calculate everything else normally.
    3. We return the biggest of the two values.
     public int rob(int[] nums) {
            if(nums == null || nums.length == 0){
                return 0;
             int prevFirstSum=0;
             int prevLastSum=0;
             int currFirstSum=nums[0];
             int currLastSum=0;
             for(int i=1; i<nums.length-1; i++){
                 int newFirstSum = Math.max(currFirstSum, prevFirstSum+nums[i]);
                 int newLastSum=Math.max(currLastSum, prevLastSum+nums[i]);
                 prevFirstSum = currFirstSum;
                 prevLastSum= currLastSum;
                 currFirstSum = newFirstSum;
             currLastSum=Math.max(currLastSum, prevLastSum+nums[nums.length-1]);
             return (currFirstSum>currLastSum)? currFirstSum:currLastSum;

  • 0

    O(n) Space I think.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.