Command Palette

Search for a command to run...

Hectal
Problem 32.6 · Advanced DPMedium

House Robber III

PatternTree DFS1D Dynamic Programming

What it teaches: Tree DP returning (rob, skip) from every subtree.

Practise it on judges as “House Robber III”.

The problem

Houses form a binary tree. Robbing two directly linked houses alerts the police. Return the maximum money.

Example 1

Input: root = [3, 2, 3, null, 3, null, 1]
Output: 7

Constraints

  • 1 ≤ nodes ≤ 10⁴

Pattern clues in the wording

  • → Take-or-skip on a tree

These clues point to Tree DFS: Recurse into the left and right children and combine what they return (height, sums, paths).

Stuck? Take one hint at a time

Solution.java · starter
class Solution {
    public int rob(TreeNode root) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
root = [3,2,3,null,3,null,1]
7
2
root = [3,4,5,1,3,null,1]
9

From slow to fast

Approaches

1. Post-order pair · O(n)
1

Post-order pair

Time O(n) Space O(h)

dfs returns {rob, skip}; rob = val + l.skip + r.skip; skip = max(l) + max(r).

Approach 1
class Solution {
    public int rob(TreeNode root) {
        int[] r = dfs(root);
        return Math.max(r[0], r[1]);
    }

    private int[] dfs(TreeNode n) {
        if (n == null) return new int[2];
        int[] l = dfs(n.left), r = dfs(n.right);
        int rob = n.val + l[1] + r[1];
        int skip = Math.max(l[0], l[1]) + Math.max(r[0], r[1]);
        return new int[]{rob, skip};
    }
}

Verdict: No memo map needed.

Before you submit

Edge cases and common mistakes

Test these inputs

  • Single node
  • Skipping two levels is better

Mistakes people make

  • Robbing alternate levels (not always optimal).

Interview

Follow-up questions

What is the general name for this problem?