Simple AC solution in Java in O(n) with explanation


  • 213
    L

    Since this question is a follow-up to House Robber, we can assume we already have a way to solve the simpler question, i.e. given a 1 row of house, we know how to rob them. So we already have such a helper function. We modify it a bit to rob a given range of houses.

    private int rob(int[] num, int lo, int hi) {
        int include = 0, exclude = 0;
        for (int j = lo; j <= hi; j++) {
            int i = include, e = exclude;
            include = e + num[j];
            exclude = Math.max(e, i);
        }
        return Math.max(include, exclude);
    }
    

    Now the question is how to rob a circular row of houses. It is a bit complicated to solve like the simpler question. It is because in the simpler question whether to rob num[lo] is entirely our choice. But, it is now constrained by whether num[hi] is robbed.

    However, since we already have a nice solution to the simpler problem. We do not want to throw it away. Then, it becomes how can we reduce this problem to the simpler one. Actually, extending from the logic that if house i is not robbed, then you are free to choose whether to rob house i + 1, you can break the circle by assuming a house is not robbed.

    For example, 1 -> 2 -> 3 -> 1 becomes 2 -> 3 if 1 is not robbed.

    Since every house is either robbed or not robbed and at least half of the houses are not robbed, the solution is simply the larger of two cases with consecutive houses, i.e. house i not robbed, break the circle, solve it, or house i + 1 not robbed. Hence, the following solution. I chose i = n and i + 1 = 0 for simpler coding. But, you can choose whichever two consecutive ones.

    public int rob(int[] nums) {
        if (nums.length == 1) return nums[0];
        return Math.max(rob(nums, 0, nums.length - 2), rob(nums, 1, nums.length - 1));
    }

  • 0
    J
    This post is deleted!

  • 1

    nice way to break up this into small problems, thanks :)


  • 0
    L
    This post is deleted!

  • 0
    J

    very brilliant solution!
    thanks for your sharing


  • 36
    S

    I went over the hot solutions with most votes. Almost all people use the same idea like this one:

    (1) i not robbed

    (2) i+1 not robbed

    Though it looks correct at the first sight, I still don't hundred percent understand why it is correct. Can anyone explain (or prove) in detail???


    And my solution also pass to the original rob method twice, but my idea is a little different:

    (1) i not robbed

    (2) i robbed

    Same as the solution above, if i is not robbed, it will break the circle, we can just pass the rest n-1 elements. But if i is robbed, then i-1 and i+1 can not be robbed, it also will break the circle. We can just pass the rest n-3 elements and plus nums[i]. This idea is easy to understand to me because ith house should be either robbed or not robbed. Here I pick i = 0.

    public class Solution {
        public int rob(int[] nums) {
            if (nums.length == 0) return 0;
            if (nums.length == 1) return nums[0];
            if (nums.length == 2) return Math.max(nums[0], nums[1]);
            if (nums.length == 3) return Math.max(Math.max(nums[0], nums[1]), nums[2]);
            return Math.max(rob1(Arrays.copyOfRange(nums, 1, nums.length)), nums[0] + rob1(Arrays.copyOfRange(nums, 2, nums.length-1)));
        }
        
        public int rob1(int[] nums) {
            int preno = 0;
            int preyes = nums[0];
            for (int i = 1; i < nums.length; i++)
            {
                int tmp = preyes;
                preyes = preno + nums[i];
                preno = Math.max(preno, tmp);
            }
            return Math.max(preyes, preno);
        }
    }
    

  • 0
    H

    You solution is amazing and actually easier to understand. But by comparing your code with the first solution, you will find that the underlying ideas are of the same. Your solution separates the nums[0] part from the DP process while the first one does not.

    Also
    if (nums.length == 1) return nums[0];
    if (nums.length == 2) return Math.max(nums[0], nums[1]);
    if (nums.length == 3) return Math.max(Math.max(nums[0], nums[1]), nums[2]);

    These three lines of code are redundant.


  • 0
    K

    The aforementioned lines are not redundant. Considerring Arrays.copyOfRange(nums, 2, nums.length-1), nums.length - 1 must be no less than 2.


  • 1
    S

    If you choose i not robbed, there missing one condition that i is robbed, as your said. The fact is this condition (i is robbed) is considered in "i+1 not robbed" assumption (by saying considered, it is not necessarily calculated for the final dp result of "i+1 not robbed"). So you just need to get the max of "i not robbed" & "i+1 not robbed"


  • 0
    R

    This was much much more intuitive to understand thank you.


  • 10
    Z

    A very nice solution, thanks. Let me give a try to prove it. For nums[0..n-1], 0 and n-1 are neighboring to each other. Basically, there are only three possible cases: (1) rob 0, but leave n-1 untouched, (2) leave 0 untouched, rob n-1, (3) leave both 0 and n-1 untouched. Obviously, case (3) can be covered by case(1) or case (2) in the simple House Robber problem. Hence, the above solution covers all the possible cases.


  • 0
    K

    that is correct,ok,let me add some explanations: the analysis above does not mean that we must pick at least one of the two adjacent elements,but means that:
    in case (1),if we get the maxvalue by not robbing 0,then this also means that we neither rob 0 nor n-1 ,so this equals the condition in case (3), is my analysis correct?


  • 0
    Z

    Yes, your understanding is correct.


  • 0
    M

    Using generalized indices i and i+1 are easier to understand, since the specific indices 0 and n-1 are prone to misleading...


  • 0
    M

    This is more intuitive, thank you. To be honest, I don't think your idea is "a little different" from @lx223 's. They are two completely different perspectives, both upvoted!

    Although your idea is good, your code can be improved a lot further :p 1). there is no need to copy the array, you can simply adjust the index; 2). based on 1)., there is no need for 3 base cases -- if rob house i, return nums[i] + helper(nums, staring_index_is_i+2, n-3_house_to_rob), jf n-3<=0, helper() simply returns 0; if not rob house i, return helper(nums, starting_index_is_i+1, n-1_house_to_rob).


  • 1

    As you have said , there are n different choices for the value of the start point. What I think is that there are n possible points can be chosen as the start point and the end point. So why you just calculate one case ?? I can not understand why this can pass all the cases ??


  • 0
    S

    It's same. Just rotate the list.


  • 0
    O

    Cool solution. Thanks. One small improvement: it will be better to move initialization of i, e variables outside the for-loop.


  • 0
    D

    @shenhualong easy to understand, thanks


  • 2
    Z

    Nice Solution.

    Two calls of private rob function can be merged into one, so there is only one loop.

    public class Solution {
        public int rob(int[] nums) {
            if(nums.length == 0) return 0;
            if(nums.length == 1) return nums[0];
            
            int prev0 = 0,curr0 = 0, prev1 = 0, curr1 = 0;
            
            for(int i = 0; i < nums.length - 1; i++){
                int temp0 = prev0;
                prev0 = curr0;
                curr0 = Math.max(temp0 + nums[i], prev0);
                int temp1 = prev1;
                prev1 = curr1;
                curr1 = Math.max(temp1 + nums[i + 1], prev1);
            }
            return Math.max(curr1,curr0);
        }
    }
    

Log in to reply
 

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