How do you solve House Robber III on LeetCode?

House Robber III (LeetCode #337) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(h) space complexity. Key insight: Dynamic programming helps avoid redundant calculations.

What is the brute force solution for House Robber III?

The brute force approach for House Robber III is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves checking all possible combinations of houses that can be robbed without alerting the police. This means exploring every path in the binary tree and calculating the maximum money that can be robbed for each path. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve House Robber III?

House Robber III uses the following concepts: Dynamic Programming, Tree, Depth-First Search, Binary Tree. The recommended patterns to study are: Dynamic Programming, Tree Traversal.

What are the interview tips for House Robber III?

Explain your thought process clearly while coding. Consider edge cases and test your solution with them. Discuss the time and space complexity of your approach.

What are common mistakes when solving House Robber III?

Not considering both scenarios (robbing vs not robbing) for each node. Failing to account for base cases in recursion.

#337

House Robber III

Medium

Dynamic ProgrammingTreeDepth-First SearchBinary TreeDynamic ProgrammingTree Traversal

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(h)

💡

Intuition

Time O(n)Space O(h)

The optimal approach uses dynamic programming to store results of subproblems, avoiding redundant calculations. By using a helper function that returns two values (maximum money if robbed and if not robbed), we can efficiently compute the result in a single traversal of the tree.

⚙️

Algorithm

3 steps

1Step 1: Create a helper function that returns two values: max money if the current node is robbed and if it is not robbed.
2Step 2: For each node, calculate the maximum money by considering both scenarios (robbing and not robbing).
3Step 3: Store results in a tuple and return the maximum of the two values.

solution.py17 lines

1class TreeNode:
2    def __init__(self, val=0, left=None, right=None):
3        self.val = val
4        self.left = left
5        self.right = right
6
7class Solution:
8    def rob(self, root: TreeNode) -> int:
9        def dfs(node):
10            if not node:
11                return (0, 0)
12            left = dfs(node.left)
13            right = dfs(node.right)
14            rob_current = node.val + left[1] + right[1]
15            skip_current = max(left) + max(right)
16            return (rob_current, skip_current)
17        return max(dfs(root))

ℹ

Complexity note: The time complexity is linear because we visit each node exactly once. The space complexity is O(h) due to the recursion stack, where h is the height of the tree.

1Dynamic programming helps avoid redundant calculations.
2Using recursion with memoization can optimize tree traversal.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.