onenoughtone

Code Implementation

House Robber II Implementation

Below is the implementation of the house robber ii:

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
/**
 * Find the maximum amount of money you can rob without alerting the police.
 * Dynamic Programming with Two Cases 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];
  if (n === 2) return Math.max(nums[0], nums[1]);
 
  // Case 1: Rob houses from index 0 to n-2 (excluding the last house)
  const dp1 = new Array(n - 1);
  dp1[0] = nums[0];
  dp1[1] = Math.max(nums[0], nums[1]);
 
  for (let i = 2; i < n - 1; i++) {
    dp1[i] = Math.max(dp1[i - 1], dp1[i - 2] + nums[i]);
  }
 
  // Case 2: Rob houses from index 1 to n-1 (excluding the first house)
  const dp2 = new Array(n - 1);
  dp2[0] = nums[1];
  dp2[1] = Math.max(nums[1], nums[2]);
 
  for (let i = 2; i < n - 1; i++) {
    dp2[i] = Math.max(dp2[i - 1], dp2[i - 2] + nums[i + 1]);
  }
 
  return Math.max(dp1[n - 2], dp2[n - 2]);
}
 
/**
 * 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];
  if (n === 2) return Math.max(nums[0], nums[1]);
 
  // Helper function to solve the original House Robber problem
  function robRange(nums, start, end) {
    let prev2 = 0;
    let prev1 = 0;
 
    for (let i = start; i <= end; i++) {
      const current = Math.max(prev1, prev2 + nums[i]);
      prev2 = prev1;
      prev1 = current;
    }
 
    return prev1;
  }
 
  // Case 1: Rob houses from index 0 to n-2 (excluding the last house)
  const result1 = robRange(nums, 0, n - 2);
 
  // Case 2: Rob houses from index 1 to n-1 (excluding the first house)
  const result2 = robRange(nums, 1, n - 1);
 
  return Math.max(result1, result2);
}
 
// Test cases
console.log(rob([2, 3, 2]));  // 3
console.log(rob([1, 2, 3, 1]));  // 4
console.log(rob([1, 2, 3]));  // 3
 
console.log(robOptimized([2, 3, 2]));  // 3
console.log(robOptimized([1, 2, 3, 1]));  // 4
console.log(robOptimized([1, 2, 3]));  // 3

Step-by-Step Explanation

Let's break down the implementation:

Understand the Problem: First, understand that this is a variation of the House Robber problem with a circular arrangement, where the first and last houses are adjacent.
Handle Edge Cases: Handle edge cases such as empty arrays, arrays with one element, and arrays with two elements.
Break the Circle: Break the circular arrangement by considering two cases: (1) excluding the last house, and (2) excluding the first house.
Apply Dynamic Programming: Apply the original House Robber algorithm to each case, using dynamic programming to find the maximum amount of money that can be robbed.
Optimize Space Complexity: Optimize the space complexity by using a helper function that only keeps track of the previous two values, rather than using arrays to store all the dp values.

Previous Next

String Problems

Palindrome Checker

Determine if a string reads the same forward and backward.

EasyString Manipulation

Message Encryption

Reverse a string to create a simple encryption system.

EasyString Manipulation

Word Puzzle Challenge

Check if two strings are anagrams of each other.

EasyString Manipulation

Learning Objective

Implement the house robber ii solution in different programming languages.

House Robber II Implementation

Below is the implementation of the house robber ii in different programming languages. Select a language tab to view the corresponding code.

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
/**
 * Find the maximum amount of money you can rob without alerting the police.
 * Dynamic Programming with Two Cases 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];
  if (n === 2) return Math.max(nums[0], nums[1]);
 
  // Case 1: Rob houses from index 0 to n-2 (excluding the last house)
  const dp1 = new Array(n - 1);
  dp1[0] = nums[0];
  dp1[1] = Math.max(nums[0], nums[1]);
 
  for (let i = 2; i < n - 1; i++) {
    dp1[i] = Math.max(dp1[i - 1], dp1[i - 2] + nums[i]);
  }
 
  // Case 2: Rob houses from index 1 to n-1 (excluding the first house)
  const dp2 = new Array(n - 1);
  dp2[0] = nums[1];
  dp2[1] = Math.max(nums[1], nums[2]);
 
  for (let i = 2; i < n - 1; i++) {
    dp2[i] = Math.max(dp2[i - 1], dp2[i - 2] + nums[i + 1]);
  }
 
  return Math.max(dp1[n - 2], dp2[n - 2]);
}
 
/**
 * 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];
  if (n === 2) return Math.max(nums[0], nums[1]);
 
  // Helper function to solve the original House Robber problem
  function robRange(nums, start, end) {
    let prev2 = 0;
    let prev1 = 0;
 
    for (let i = start; i <= end; i++) {
      const current = Math.max(prev1, prev2 + nums[i]);
      prev2 = prev1;
      prev1 = current;
    }
 
    return prev1;
  }
 
  // Case 1: Rob houses from index 0 to n-2 (excluding the last house)
  const result1 = robRange(nums, 0, n - 2);
 
  // Case 2: Rob houses from index 1 to n-1 (excluding the first house)
  const result2 = robRange(nums, 1, n - 1);
 
  return Math.max(result1, result2);
}
 
// Test cases
console.log(rob([2, 3, 2]));  // 3
console.log(rob([1, 2, 3, 1]));  // 4
console.log(rob([1, 2, 3]));  // 3
 
console.log(robOptimized([2, 3, 2]));  // 3
console.log(robOptimized([1, 2, 3, 1]));  // 4
console.log(robOptimized([1, 2, 3]));  // 3

Step-by-Step Explanation

1Understand the Problem

First, understand that this is a variation of the House Robber problem with a circular arrangement, where the first and last houses are adjacent.

2Handle Edge Cases

Handle edge cases such as empty arrays, arrays with one element, and arrays with two elements.

3Break the Circle

Break the circular arrangement by considering two cases: (1) excluding the last house, and (2) excluding the first house.

4Apply Dynamic Programming

Apply the original House Robber algorithm to each case, using dynamic programming to find the maximum amount of money that can be robbed.

5Optimize Space Complexity

Optimize the space complexity by using a helper function that only keeps track of the previous two values, rather than using arrays to store all the dp values.

Language-Specific Notes

javascript

JavaScript's Math.max() is used to find the maximum of two or more values.
The new Array() constructor is used to create arrays of a specific size.
The for loop is used to iterate through the array.
The if statement is used to handle edge cases.
A helper function is used to avoid code duplication in the optimized approach.

python

Python's max() function is used to find the maximum of two or more values.
List initialization [0] * (n - 1) is used to create arrays of a specific size.
The range() function is used to generate sequences for iteration.
Nested functions (rob_range) are used to avoid code duplication.
The len() function is used to get the length of a list.

java

Java's Math.max() is used to find the maximum of two values.
Arrays are initialized with a specific size using new int[n - 1].
The for loop is used to iterate through the array.
Private helper methods are used to avoid code duplication.
The if statement with early returns is used to handle edge cases.

cpp

C++'s std::max() from is used to find the maximum of two values.
std::vector is used to create dynamic arrays.
The for loop is used to iterate through the array.
Function parameters are passed by const reference to avoid copying.
Initializer lists {2, 3, 2} are used to create vectors in the test cases.

Key Takeaways

This problem is a variation of the House Robber problem with a circular arrangement.
The circular arrangement can be handled by considering two cases: excluding the first house and excluding the last house.
Dynamic programming can be used to solve each case, with dp[i] representing the maximum amount of money that can be robbed from the first i houses.
The space complexity can be optimized from O(n) to O(1) by only keeping track of the previous two values.
The time complexity is O(n) in both approaches, as we need to iterate through the array twice, once for each case.

Try It Yourself

Modify the code to implement an alternative approach and test it with the same examples.

Challenge:

Implement a function that solves the house robber ii problem using a different approach than shown above.

Common Edge Cases

Empty Array

Handle the case where the array is empty (return 0).

nums = []

Single House

Handle the case where there's only one house (return the amount of money in that house).

nums = [5]

Two Houses

Handle the case where there are only two houses (return the maximum of the two).

nums = [3, 7]

Solution Approach All Problems

Problem Solution Code

onenoughtone

Back to Home

onenoughtone

Back to Home

House Robber II - Implementation

Code Implementation

House Robber II Implementation

Below is the implementation of the house robber ii:

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
/**
 * Find the maximum amount of money you can rob without alerting the police.
 * Dynamic Programming with Two Cases 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];
  if (n === 2) return Math.max(nums[0], nums[1]);
 
  // Case 1: Rob houses from index 0 to n-2 (excluding the last house)
  const dp1 = new Array(n - 1);
  dp1[0] = nums[0];
  dp1[1] = Math.max(nums[0], nums[1]);
 
  for (let i = 2; i < n - 1; i++) {
    dp1[i] = Math.max(dp1[i - 1], dp1[i - 2] + nums[i]);
  }
 
  // Case 2: Rob houses from index 1 to n-1 (excluding the first house)
  const dp2 = new Array(n - 1);
  dp2[0] = nums[1];
  dp2[1] = Math.max(nums[1], nums[2]);
 
  for (let i = 2; i < n - 1; i++) {
    dp2[i] = Math.max(dp2[i - 1], dp2[i - 2] + nums[i + 1]);
  }
 
  return Math.max(dp1[n - 2], dp2[n - 2]);
}
 
/**
 * 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];
  if (n === 2) return Math.max(nums[0], nums[1]);
 
  // Helper function to solve the original House Robber problem
  function robRange(nums, start, end) {
    let prev2 = 0;
    let prev1 = 0;
 
    for (let i = start; i <= end; i++) {
      const current = Math.max(prev1, prev2 + nums[i]);
      prev2 = prev1;
      prev1 = current;
    }
 
    return prev1;
  }
 
  // Case 1: Rob houses from index 0 to n-2 (excluding the last house)
  const result1 = robRange(nums, 0, n - 2);
 
  // Case 2: Rob houses from index 1 to n-1 (excluding the first house)
  const result2 = robRange(nums, 1, n - 1);
 
  return Math.max(result1, result2);
}
 
// Test cases
console.log(rob([2, 3, 2]));  // 3
console.log(rob([1, 2, 3, 1]));  // 4
console.log(rob([1, 2, 3]));  // 3
 
console.log(robOptimized([2, 3, 2]));  // 3
console.log(robOptimized([1, 2, 3, 1]));  // 4
console.log(robOptimized([1, 2, 3]));  // 3

Step-by-Step Explanation

Let's break down the implementation:

Understand the Problem: First, understand that this is a variation of the House Robber problem with a circular arrangement, where the first and last houses are adjacent.
Handle Edge Cases: Handle edge cases such as empty arrays, arrays with one element, and arrays with two elements.
Break the Circle: Break the circular arrangement by considering two cases: (1) excluding the last house, and (2) excluding the first house.
Apply Dynamic Programming: Apply the original House Robber algorithm to each case, using dynamic programming to find the maximum amount of money that can be robbed.
Optimize Space Complexity: Optimize the space complexity by using a helper function that only keeps track of the previous two values, rather than using arrays to store all the dp values.

Previous Next

String Problems

Palindrome Checker

Determine if a string reads the same forward and backward.

EasyString Manipulation

Message Encryption

Reverse a string to create a simple encryption system.

EasyString Manipulation

Word Puzzle Challenge

Check if two strings are anagrams of each other.

EasyString Manipulation

Learning Objective

Implement the house robber ii solution in different programming languages.

House Robber II Implementation

Below is the implementation of the house robber ii in different programming languages. Select a language tab to view the corresponding code.

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
/**
 * Find the maximum amount of money you can rob without alerting the police.
 * Dynamic Programming with Two Cases 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];
  if (n === 2) return Math.max(nums[0], nums[1]);
 
  // Case 1: Rob houses from index 0 to n-2 (excluding the last house)
  const dp1 = new Array(n - 1);
  dp1[0] = nums[0];
  dp1[1] = Math.max(nums[0], nums[1]);
 
  for (let i = 2; i < n - 1; i++) {
    dp1[i] = Math.max(dp1[i - 1], dp1[i - 2] + nums[i]);
  }
 
  // Case 2: Rob houses from index 1 to n-1 (excluding the first house)
  const dp2 = new Array(n - 1);
  dp2[0] = nums[1];
  dp2[1] = Math.max(nums[1], nums[2]);
 
  for (let i = 2; i < n - 1; i++) {
    dp2[i] = Math.max(dp2[i - 1], dp2[i - 2] + nums[i + 1]);
  }
 
  return Math.max(dp1[n - 2], dp2[n - 2]);
}
 
/**
 * 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];
  if (n === 2) return Math.max(nums[0], nums[1]);
 
  // Helper function to solve the original House Robber problem
  function robRange(nums, start, end) {
    let prev2 = 0;
    let prev1 = 0;
 
    for (let i = start; i <= end; i++) {
      const current = Math.max(prev1, prev2 + nums[i]);
      prev2 = prev1;
      prev1 = current;
    }
 
    return prev1;
  }
 
  // Case 1: Rob houses from index 0 to n-2 (excluding the last house)
  const result1 = robRange(nums, 0, n - 2);
 
  // Case 2: Rob houses from index 1 to n-1 (excluding the first house)
  const result2 = robRange(nums, 1, n - 1);
 
  return Math.max(result1, result2);
}
 
// Test cases
console.log(rob([2, 3, 2]));  // 3
console.log(rob([1, 2, 3, 1]));  // 4
console.log(rob([1, 2, 3]));  // 3
 
console.log(robOptimized([2, 3, 2]));  // 3
console.log(robOptimized([1, 2, 3, 1]));  // 4
console.log(robOptimized([1, 2, 3]));  // 3

Step-by-Step Explanation

1Understand the Problem

First, understand that this is a variation of the House Robber problem with a circular arrangement, where the first and last houses are adjacent.

2Handle Edge Cases

Handle edge cases such as empty arrays, arrays with one element, and arrays with two elements.

3Break the Circle

Break the circular arrangement by considering two cases: (1) excluding the last house, and (2) excluding the first house.

4Apply Dynamic Programming

Apply the original House Robber algorithm to each case, using dynamic programming to find the maximum amount of money that can be robbed.

5Optimize Space Complexity

Optimize the space complexity by using a helper function that only keeps track of the previous two values, rather than using arrays to store all the dp values.

Language-Specific Notes

javascript

JavaScript's Math.max() is used to find the maximum of two or more values.
The new Array() constructor is used to create arrays of a specific size.
The for loop is used to iterate through the array.
The if statement is used to handle edge cases.
A helper function is used to avoid code duplication in the optimized approach.

python

Python's max() function is used to find the maximum of two or more values.
List initialization [0] * (n - 1) is used to create arrays of a specific size.
The range() function is used to generate sequences for iteration.
Nested functions (rob_range) are used to avoid code duplication.
The len() function is used to get the length of a list.

java

Java's Math.max() is used to find the maximum of two values.
Arrays are initialized with a specific size using new int[n - 1].
The for loop is used to iterate through the array.
Private helper methods are used to avoid code duplication.
The if statement with early returns is used to handle edge cases.

cpp

C++'s std::max() from is used to find the maximum of two values.
std::vector is used to create dynamic arrays.
The for loop is used to iterate through the array.
Function parameters are passed by const reference to avoid copying.
Initializer lists {2, 3, 2} are used to create vectors in the test cases.

Key Takeaways

This problem is a variation of the House Robber problem with a circular arrangement.
The circular arrangement can be handled by considering two cases: excluding the first house and excluding the last house.
Dynamic programming can be used to solve each case, with dp[i] representing the maximum amount of money that can be robbed from the first i houses.
The space complexity can be optimized from O(n) to O(1) by only keeping track of the previous two values.
The time complexity is O(n) in both approaches, as we need to iterate through the array twice, once for each case.

Try It Yourself

Modify the code to implement an alternative approach and test it with the same examples.

Challenge:

Implement a function that solves the house robber ii problem using a different approach than shown above.

Common Edge Cases

Empty Array

Handle the case where the array is empty (return 0).

nums = []

Single House

Handle the case where there's only one house (return the amount of money in that house).

nums = [5]

Two Houses

Handle the case where there are only two houses (return the maximum of the two).

nums = [3, 7]

Solution Approach All Problems

Code Implementation

House Robber II Implementation

Step-by-Step Explanation

String ProblemsShow All

Palindrome Checker

Message Encryption

Word Puzzle Challenge

Learning Objective

House Robber II Implementation

Step-by-Step Explanation

1Understand the Problem

2Handle Edge Cases

3Break the Circle

4Apply Dynamic Programming

5Optimize Space Complexity

Language-Specific Notes

javascript

python

java

cpp

Key Takeaways

Try It Yourself

Challenge:

Common Edge Cases

Empty Array

Single House

Two Houses

House Robber II - Implementation

Code Implementation

House Robber II Implementation

Step-by-Step Explanation

String ProblemsShow All

Palindrome Checker

Message Encryption

Word Puzzle Challenge

Learning Objective

House Robber II Implementation

Step-by-Step Explanation

1Understand the Problem

2Handle Edge Cases

3Break the Circle

4Apply Dynamic Programming

5Optimize Space Complexity

Language-Specific Notes

javascript

python

java

cpp

Key Takeaways

Try It Yourself

Challenge:

Common Edge Cases

Empty Array

Single House

Two Houses

String Problems

String Problems