algoadvance

Leetcode 337. House Robber III

Problem Statement

The problem is defined as follows:

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the “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.

Clarifying Questions

  1. Can the binary tree contain negative values?
    • No, the value of each node is non-negative as it represents the amount of money in each house.
  2. Can the binary tree be empty?
    • Yes, if the binary tree is empty, the maximum amount of money to rob is 0.
  3. Are there any constraints on the size of the binary tree?
    • The number of nodes in the tree is in the range [0, 10^4], and the value of each node is between [0, 10^4].

Strategy

To solve this problem, we will use Dynamic Programming with memoization. The key observation is that for each node, the thief has two choices:

  1. Rob the current house and then skip its children.
  2. Skip the current house and then consider its children.

We will recursively calculate the maximum amount of money that can be robbed for each case and use memoization to store intermediate results to avoid redundant calculations.

Here is a breakdown of the steps:

  1. Define a helper function robHelper that returns two values: the maximum amount robbed if the current node is not robbed, and the maximum amount if it is robbed.
  2. For the current node:
    • Calculate the maximum amount if the node is robbed by summing the values of not robbing its children.
    • Calculate the maximum amount if the node is not robbed by considering the maximum values robbed from its children.
  3. Use a HashMap to store the results of subproblems to optimize the performance.

Code

import java.util.HashMap;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public int rob(TreeNode root) {
        HashMap<TreeNode, Integer> memo = new HashMap<>();
        return robHelper(root, memo);
    }

    private int robHelper(TreeNode node, HashMap<TreeNode, Integer> memo) {
        if (node == null) return 0;
        if (memo.containsKey(node)) return memo.get(node);

        // Money when robbing the current node
        int moneyWithRob = node.val;
        if (node.left != null) {
            moneyWithRob += robHelper(node.left.left, memo) + robHelper(node.left.right, memo);
        }
        if (node.right != null) {
            moneyWithRob += robHelper(node.right.left, memo) + robHelper(node.right.right, memo);
        }

        // Money when not robbing the current node
        int moneyWithoutRob = robHelper(node.left, memo) + robHelper(node.right, memo);

        // Max money we can rob from this node
        int result = Math.max(moneyWithRob, moneyWithoutRob);

        memo.put(node, result);
        return result;
    }
}

Time Complexity

The time complexity of this solution is O(N) where N is the number of nodes in the tree. This is because each node is visited once, and the results are stored and reused, thus avoiding redundant calculations.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI