101 Logo
onenoughtone

Code Implementation

Neighborhood Heist Implementation

Below is the implementation of the neighborhood heist:

solution.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
/**
 * Find the maximum amount of money you can rob without alerting the police.
 * Dynamic Programming approach.
 *
 * @param {number[]} nums - Array of money in each house
 * @return {number} - Maximum amount of money
 */
function rob(nums) {
  const n = nums.length;
 
  // Handle edge cases
  if (n === 0) return 0;
  if (n === 1) return nums[0];
 
  // Initialize dp array
  const dp = new Array(n);
  dp[0] = nums[0];
  dp[1] = Math.max(nums[0], nums[1]);
 
  // Fill the dp array
  for (let i = 2; i < n; i++) {
    dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
  }
 
  return dp[n - 1];
}
 
/**
 * Find the maximum amount of money you can rob without alerting the police.
 * Space-Optimized Dynamic Programming approach.
 *
 * @param {number[]} nums - Array of money in each house
 * @return {number} - Maximum amount of money
 */
function robOptimized(nums) {
  const n = nums.length;
 
  // Handle edge cases
  if (n === 0) return 0;
  if (n === 1) return nums[0];
 
  // Initialize variables
  let prev2 = 0;
  let prev1 = 0;
 
  // Iterate through the array
  for (let i = 0; i < n; i++) {
    const current = Math.max(prev2 + nums[i], prev1);
    prev2 = prev1;
    prev1 = current;
  }
 
  return prev1;
}
 
/**
 * Find the maximum amount of money you can rob without alerting the police.
 * Recursive approach with memoization.
 *
 * @param {number[]} nums - Array of money in each house
 * @return {number} - Maximum amount of money
 */
function robRecursive(nums) {
  const n = nums.length;
  const memo = new Array(n).fill(-1);
 
  /**
   * Helper function to calculate the maximum amount of money we can rob starting from the i-th house.
   *
   * @param {number} i - Current house index
   * @return {number} - Maximum amount of money
   */
  function dp(i) {
    // Base cases
    if (i >= n) return 0;
 
    // Check if we've already computed this subproblem
    if (memo[i] !== -1) return memo[i];
 
    // Recursive cases: rob the current house or skip it
    const result = Math.max(nums[i] + dp(i + 2), dp(i + 1));
 
    // Memoize and return
    memo[i] = result;
    return result;
  }
 
  return dp(0);
}
 
// Test cases
console.log(rob([1, 2, 3, 1]));  // 4
console.log(rob([2, 7, 9, 3, 1]));  // 12
 
console.log(robOptimized([1, 2, 3, 1]));  // 4
console.log(robOptimized([2, 7, 9, 3, 1]));  // 12
 
console.log(robRecursive([1, 2, 3, 1]));  // 4
console.log(robRecursive([2, 7, 9, 3, 1]));  // 12

Step-by-Step Explanation

Let's break down the implementation:

  1. Understand the Problem: First, understand that we need to find the maximum amount of money we can rob without alerting the police, which means we can't rob adjacent houses.
  2. Define the State: Define the state dp[i] as the maximum amount of money we can rob up to the i-th house.
  3. Define the Recurrence Relation: For each house, we have two options: rob it or skip it. We choose the option that gives us the maximum amount: dp[i] = max(dp[i-2] + nums[i], dp[i-1]).
  4. Handle Base Cases: Handle base cases: dp[0] = nums[0] and dp[1] = max(nums[0], nums[1]).
  5. Implement the Solution: Implement the solution using dynamic programming, space-optimized dynamic programming, or recursive approach with memoization.
PreviousNext
ProblemSolutionCode
101 Logo
onenoughtone