Sponsored
Sponsored
This approach involves splitting the problem into two scenarios: robbing from house 0 to house n-2, and from house 1 to house n-1. The aim is to apply the linear version of the House Robber problem to each scenario separately and then take the maximum of the two resulting summed values.
Time Complexity: O(n).
Space Complexity: O(1).
1
2var robLinear = function(nums) {
3 let prev1 = 0, prev2 = 0;
4 for (const num of nums) {
5 let temp = prev1;
6 prev1 = Math.max(num + prev2, prev1);
7 prev2 = temp;
8 }
9 return prev1;
10};
11
12var rob = function(nums) {
13 if (nums.length === 1) return nums[0];
14 return Math.max(robLinear(nums.slice(0, nums.length - 1)), robLinear(nums.slice(1)));
15};
16This JavaScript solution employs a helper function robLinear leveraging slice function for fresh arrays without the first or last element. It calculates the maximum sum possible in both scenarios and returns the greater value.
This approach implements a memoized version of the dynamic programming solution to avoid recomputing values. We explore two scenarios of the circle, taking into account the cycles explicitly by caching intermediate results.
Time Complexity: O(n).
Space Complexity: O(n) for the memoization array.
1
2
This Java solution uses an integer array memo for caching operations to minimize redundant computations. It features a robHelper private method to recursively determine the maximum amount drawable from specific index ranges. Each side of the circle is evaluated for maximizing results separately.