O(n) time complexity and O(1) space complexity solution


  • 0
    S
    public class Solution {
    public int rob(int[] nums) {
        if(nums == null || nums.length < 1)
            return 0;
        if(nums.length == 1)
            return nums[0];
        if(nums.length == 2)
            return max(nums[nums.length-1], nums[nums.length-2]);
        
        nums[2] = nums[2]+nums[0];
        
        for(int i =3; i < nums.length; i++)
            nums[i] = max(nums[i] + nums[i-2], nums[i]+ nums[i-3]);
            
        return max(nums[nums.length-1], nums[nums.length-2]);
    }
    
    private int max(int a, int b)
    {
        return a>b?a:b;
    }
    
    }
    

    The solution has 3 base cases to compensate for nums.length ==3. Otherwise it just traverse the array and update the current position from the maximum of current + 2 spaces behind and current + 3 spaces behind.


Log in to reply
 

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