Single Pass O(n) based off House Robber


  • 0
    M

    Basically this problem is the same as the 1st House Robber, except we cannot pick the first if we pick the last and vice versa. Thus, let F(i, j) denote the solution for House Robber 1 for houses in range [i, j), House Robber II is defined as:

    max(F(0, n-1), F(1, n))

    This can be done in a single pass if you compute both function values at the same time. Explanation to my solution is here: https://discuss.leetcode.com/topic/106114/two-dp-o-n-solutions-c; a in the code is previous 2 states and b is previous state.

    Edge case occurs when size of input is 1 element.

    int rob(vector<int>& nums) {
            if(nums.size() == 1) return nums[0];
            
            int a1 = 0;
            int b1 = 0;
            
            int a2 = 0;
            int b2 = 0;
            
            for(int i = 0; i < nums.size(); ++i)
            {
                if(i > 0)
                {
                    int curr = max(b2, nums[i] + a2);
                    a2 = b2;
                    b2 = curr;   
                }
                
                if(i < nums.size() - 1)
                {
                    int curr = max(b1, nums[i] + a1);
                    a1 = b1;
                    b1 = curr;   
                }
            }
            
            return max(b1, b2);
        }
    

Log in to reply
 

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