9-lines 0ms O(1)-Space C++ solution


  • 100

    This problem is a little tricky at first glance. However, if you have finished the House Robber problem, this problem can simply be decomposed into two House Robber problems.
    Suppose there are n houses, since house 0 and n - 1 are now neighbors, we cannot rob them together and thus the solution is now the maximum of

    1. Rob houses 0 to n - 2;
    2. Rob houses 1 to n - 1.

    The code is as follows. Some edge cases (n < 2) are handled explicitly.

    class Solution {
    public:
        int rob(vector<int>& nums) {
            int n = nums.size(); 
            if (n < 2) return n ? nums[0] : 0;
            return max(robber(nums, 0, n - 2), robber(nums, 1, n - 1));
        }
    private:
        int robber(vector<int>& nums, int l, int r) {
            int pre = 0, cur = 0;
            for (int i = l; i <= r; i++) {
                int temp = max(pre + nums[i], cur);
                pre = cur;
                cur = temp;
            }
            return cur;
        }
    };

  • 1
    J

    Good solution, very easy to understand!


  • 0

    You are very welcome!


  • 6
    U

    Awesome! Thank you for sharing such good solution.

    I also optimized your solution by reducing the space complexity to O(1).

    int __rob(vector<int> &nums, int begin, int end) {
      int ans = 0;
      int pre0 = 0, pre1 = 0;
      for (int i = begin; i < end; ++ i) {
        int ans0 = max(pre0, pre1);
        int ans1 = pre0 + nums[i];
        ans = max({ans0, ans1, ans});
        pre0 = ans0;
        pre1 = ans1;
      }
      return ans;
    }
    
    int rob(vector<int>& nums) {
      const int N = nums.size();
      if (N == 0) return 0;
      if (N == 1) return nums[0];
      return max(__rob(nums, 0, N - 1), __rob(nums, 1, N));
    }

  • 0

    Hi, user20. Thank you for your efforts! I have updated my code and it is of O(1)-space now. Moreover, it becomes shorter :-)


  • 1

    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
    This post is deleted!

  • 0
    W

    Very Good!!Thank you for your solution! I was thinking about how to deal with the adjacent two elements,the first and the last one.


  • 0

    Same here, C#

        public int Rob(int[] nums) {
            if (nums.Length == 0) return 0;
            if (nums.Length == 1) return nums[0];
            return Math.Max(Rob(nums, 0, nums.Length - 2), Rob(nums, 1, nums.Length - 1));
        }
        
        public int Rob(int[] nums, int start, int end) 
        {
            int prev1 = 0;
            int prev2 = 0;
            int curr = 0;
            for (int i = start; i <= end; i++)
            {
                curr = Math.Max(nums[i] + prev2, prev1);
                prev2 = prev1;
                prev1 = curr;
            }
            return curr;
        }
    

  • 1
    G

    @RainbowSecret I was confused about this too.

    But it actually doesn't matter where you start since it's a circle. As long as you get the max of two consecutive start points, it'll work out. I think has to be consecutive though, because those two houses won't ever be robbed together anyway.

    Because if you start at 2 locations that have skipped houses in between, e.g. [1, 105, 10, 1, 110], if you start at index 0 and index 2, it won't work.

    Actually I'm still kind of confused about why this is the way it is, so if anyone can explain it better, that'd be awesome!


  • 0
    A

    Further shortening the code:

    public int rob(int[] nums) {
         if(nums.length==0) return 0; 
         return Math.max(robhelper(nums, 0, nums.length), robhelper(nums, nums[0], nums.length-1));       
     }
     public int robhelper(int[] nums, int s, int e) {
         int a = 0, b = s;
         for(int i = 2;i<=e;i++)
             b = Math.max(a+nums[i-1], a=b);        
         return b;
     }

Log in to reply
 

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