Problem Statement:
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.
Example 1:
Input: nums = [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.
Example 2:
Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3). Total amount you can rob = 1 + 3 = 4.
Example 3:
Input: nums = [1,2,3]
Output: 3
Constraints
1 <= nums.length <= 1000 <= nums[i] <= 1000
Approach:
- Since houses are in a circle, you can’t rob both the first and last house.
- So, split the problem into two linear cases:
- Case 1 → Rob houses from
0 to n-2(exclude last). - Case 2 → Rob houses from
1 to n-1(exclude first).
- Case 1 → Rob houses from
- For each case, use DP with space optimization (p1, p2) to decide for every house:
curr=max(val[i]+p2,p1)- Rob current house →
val[i] + p2 - Skip current house →
p1
- Rob current house →
Final = max of both cases.
Time & Space Complexity:
Time Complexity: O(n)
Space Complexity: O(1)
Dry Run
Input: val = [2, 3, 2]
Step 0: Start Function: rob([2, 3, 2])
n = 3
Since n != 1 → continue
We call:
- robHelper(0, n-2) → robHelper(0, 1)
- robHelper(1, n-1) → robHelper(1, 2)
Call robHelper(0, 1):
p1 = 0, p2 = 0
Iteration (i = 0):
- curr = Math.max(val[0] + p2, p1)
= Math.max(2 + 0, 0) = 2
- temp = p1 = 0
- p1 = curr = 2
- p2 = temp = 0
- curr++ → 3
State → p1 = 2, p2 = 0
Iteration (i = 1):
- curr = Math.max(val[1] + p2, p1)
= Math.max(3 + 0, 2) = 3
- temp = p1 = 2
- p1 = curr = 3
- p2 = temp = 2
- curr++ → 4
State → p1 = 3, p2 = 2
Loop ends
Return p1 = 3
---------------------------------------
Call robHelper(1, 2):
p1 = 0, p2 = 0
Iteration (i = 1):
- curr = Math.max(val[1] + p2, p1)
= Math.max(3 + 0, 0) = 3
- temp = p1 = 0
- p1 = curr = 3
- p2 = temp = 0
- curr++ → 4
State → p1 = 3, p2 = 0
Iteration (i = 2):
- curr = Math.max(val[2] + p2, p1)
= Math.max(2 + 0, 3) = 3
- temp = p1 = 3
- p1 = curr = 3
- p2 = temp = 3
- curr++ → 4
State → p1 = 3, p2 = 3
Loop ends
Return p1 = 3
---------------------------------------
Final Step:
Return Math.max(robHelper(0,1), robHelper(1,2))
= Math.max(3, 3) = 3
Output: 3
Visualisation:
var rob = function(val) {
let n = val.length;
if (n == 1) return val[0];
var robHelper = function(start, end) {
let p2 = 0, p1 = 0;
for (let i = start; i <= end; i++) {
let curr = Math.max(val[i] + p2, p1);
let temp = p1;
p1 = curr;
p2 = temp;
curr++;
}
return p1;
};
return Math.max(robHelper(0, n - 2), robHelper(1, n - 1));
};
from typing import List
def rob(val: List[int]) -> int:
n = len(val)
if n == 0:
return 0
if n == 1:
return val[0]
def rob_helper(start: int, end: int) -> int:
p1 = 0
p2 = 0
for i in range(start, end + 1):
curr = max(val[i] + p2, p1)
temp = p1
p1 = curr
p2 = temp
return p1
return max(rob_helper(0, n - 2), rob_helper(1, n - 1))
class Solution {
public int rob(int[] val) {
int n = val.length;
if (n == 0) return 0;
if (n == 1) return val[0];
java.util.function.IntBinaryOperator robHelper = (start, end) -> {
int p1 = 0, p2 = 0;
for (int i = start; i <= end; i++) {
int curr = Math.max(val[i] + p2, p1);
int temp = p1;
p1 = curr;
p2 = temp;
}
return p1;
};
return Math.max(robHelper.applyAsInt(0, n - 2), robHelper.applyAsInt(1, n - 1));
}
}
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int rob(const vector& val) {
int n = (int)val.size();
if (n == 0) return 0;
if (n == 1) return val[0];
auto robHelper = [&](int start, int end) {
int p1 = 0, p2 = 0;
for (int i = start; i <= end; ++i) {
int curr = max(val[i] + p2, p1);
int temp = p1;
p1 = curr;
p2 = temp;
}
return p1;
};
return max(robHelper(0, n - 2), robHelper(1, n - 1));
}
};
#include <stdio.h>
int max(int a, int b) { return a > b ? a : b; }
int robHelper(const int *val, int start, int end) {
int p1 = 0, p2 = 0;
for (int i = start; i <= end; ++i) {
int curr = max(val[i] + p2, p1);
int temp = p1;
p1 = curr;
p2 = temp;
}
return p1;
}
int rob(const int *val, int n) {
if (n == 0) return 0;
if (n == 1) return val[0];
int a = robHelper(val, 0, n - 2);
int b = robHelper(val, 1, n - 1);
return max(a, b);
}
using System;
public class Solution {
public int Rob(int[] val) {
int n = val.Length;
if (n == 0) return 0;
if (n == 1) return val[0];
int RobHelper(int start, int end) {
int p1 = 0, p2 = 0;
for (int i = start; i <= end; i++) {
int curr = Math.Max(val[i] + p2, p1);
int temp = p1;
p1 = curr;
p2 = temp;
}
return p1;
}
return Math.Max(RobHelper(0, n - 2), RobHelper(1, n - 1));
}
}
