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

• 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;
}
};``````

• Good solution, very easy to understand!

• You are very welcome!

• 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));
}``````

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

• 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 ??

• This post is deleted!

• 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.

• 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;
}
``````

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!

• 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;
}``````

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