Is House Robber III easy or hard?

House Robber III is rated Medium on LeetCode but can feel closer to hard for beginners because it combines dynamic programming with tree traversal. Once you recognize the rob-or-skip decision pattern and apply memoization, the implementation becomes straightforward.

House Robber III Python/Java solution

Python and Java solutions typically implement recursive DFS with a memoization map. Each function call evaluates rob and skip cases for the node and caches the result. This ensures O(n) time complexity and works efficiently even for large trees.

How to solve House Robber III in O(n)?

Traverse the tree using DFS and store the computed maximum profit for each node in a memo table. For each node calculate two cases: rob the node and add values from grandchildren, or skip the node and add values from its children. Memoization ensures every subtree result is computed only once, giving O(n) time.

What is the best approach for House Robber III?

The best approach uses Depth-First Search with memoization. For every node you compute the maximum profit from robbing it or skipping it, then store the result in a hash map to avoid recomputation. This converts the problem into dynamic programming on a tree and runs in O(n) time.

Is House Robber III asked at Google/Amazon/Meta?

House Robber III represents a classic tree dynamic programming pattern and has appeared in interviews at companies like Amazon, Google, and Meta. Interviewers use it to test recursion, DFS traversal, and the ability to apply memoization on tree structures.

What data structure is used in House Robber III?

The problem primarily uses a binary tree with Depth-First Search traversal. A hash map (dictionary) is typically used for memoization to store computed results for each node, enabling dynamic programming over the tree structure.

What is the time complexity of House Robber III?

The optimal memoized DFS solution runs in O(n) time because each node in the binary tree is processed once. Space complexity is O(n) for the memoization map plus O(h) recursion stack where h is the tree height.

Description Solution Video 18:02

337. House Robber III

Medium56.3% acceptance13 companies

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called root.

Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that all houses in this place form a binary tree. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Given the root of the binary tree, return the maximum amount of money the thief can rob without alerting the police.

Example 1:

Input: root = [3,2,3,null,3,null,1]
Output: 7
Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Example 2:

Input: root = [3,4,5,1,3,null,1]
Output: 9
Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.

Constraints:

The number of nodes in the tree is in the range [1, 10⁴].
0 <= Node.val <= 10⁴

Asked at 13 companies

Two Sigma Oyo DocuSign Zip Sprinklr Amazon Uber Tiktok Salesforce

Google Microsoft Meta

+1 more

Bloomberg

Topics

18:02

Still stuck?Read 2 approaches, or watch a walkthrough.

Open solution

337. House Robber III

Asked at 13 companies

Topics

Similar problems