This approach uses a dynamic programming table, where we maintain an array 'dp' such that dp[i] represents the maximum amount of money that can be robbed up to house i. We iterate through the list of houses and for each house, decide whether to rob it or skip it, based on the previous results stored in the dp table.
Time Complexity: O(n) - We iterate through all houses once.
Space Complexity: O(n) - We use an additional array 'dp' to store intermediate results.
1function rob(nums) {
2 if (nums.length === 0) return 0;
3 if (nums.length === 1) return nums[0];
4
5 let dp = new Array(nums.length).fill(0);
6 dp[0] = nums[0];
7 dp[1] = Math.max(nums[0], nums[1]);
8
9 for (let i = 2; i < nums.length; i++) {
10 dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]);
11 }
12
13 return dp[nums.length - 1];
14}
15
16const nums = [2, 7, 9, 3, 1];
17console.log("Max amount that can be robbed:", rob(nums));JavaScript implementation where an array 'dp' tracks the amount that can be maximally robbed up to each house index. The decision at each array position is made to either include it in the profit or skip it, depending on which yields a greater sum.
This approach optimizes the space complexity by not using a separate array for storing results of subproblems. Instead, we use two variables to keep track of the maximum amount that can be robbed up to the last two houses considered. This eliminates the need for an auxiliary array and reduces space complexity to O(1).
Time Complexity: O(n) - Elements from the house array are each visited once.
Space Complexity: O(1) - Only a few extra variables are used for keeping track.
1function rob(nums) {
2 if (nums.length === 0) return 0;
3 if (nums.length === 1) return nums[0];
4
5 let prev1 = 0, prev2 = 0, current = 0;
6
7 for (let num of nums) {
8 let temp = prev1;
9 prev1 = Math.max(prev2 + num, prev1);
10 prev2 = temp;
11 }
12 return prev1;
13}
14
15const nums = [2, 7, 9, 3, 1];
16console.log("Max amount that can be robbed:", rob(nums));Focused on using minimal extra space in JavaScript, this code defines two variables that respectively track previously calculated values, suffice for deriving the maximum rob potentials dynamically.