LeetCode: House Robber III

https://leetcode.com/problems/house-robber-iii/, problem statement:

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 forms a binary tree". It will automatically contact the police if two directly-linked houses were broken into on the same night.
Determine the maximum amount of money the thief can rob tonight without alerting the police.
Example 1:
     3
    / \
   2   3
    \   \ 
     3   1
Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
Example 2:
     3
    / \
   4   5
  / \   \ 
 1   3   1
Maximum amount of money the thief can rob = 4 + 5 = 9.

Key idea is to do a DFS (Depth-First-Search) but using post-order traversal (left-right-current). Whenever the current node can be robbed, it will be robbed, but regardless we also need to try with the current node not being robbed (think about an extrapolated tree such as 1000->1(R)->1(R)->1000(R). In this case the best solution is 2000). We should also try from the beginning the root being robable and with it being not robable. This solution will be exponential and will eventually time out for long inputs. An DP (Dynamic Programming) like approach comes handy here: keep a hash table with the results seen for the current node and the current rob state, and whenever you see that situation, pull the result out of the hash table. This will speed up the code significantly, or at least enough to be accepted. Cheeers, Marcelo.


using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Threading.Tasks;
using System.IO;

namespace LeetCode
{
    class Program
    {
        static void Main(string[] args)
        {
            TreeNode tree = new TreeNode(3);
            tree.left = new TreeNode(2);
            tree.right = new TreeNode(3);
            tree.left.right = new TreeNode(3);
            tree.right.right = new TreeNode(1);

            Solution sol = new Solution();
            Console.WriteLine(sol.Rob(tree));
        }
    }
     public class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int x) { val = x; }
     }

    public class Solution
    {
        public int Rob(TreeNode root)
        {
            if (root == null) return 0;

            int maxAmount = Int32.MinValue;
            Hashtable htMap = new Hashtable();
            MaxRob(root, true, htMap, ref maxAmount);
            MaxRob(root, false, htMap, ref maxAmount);

            return maxAmount;
        }

        private void MaxRob(TreeNode currentNode,
                            bool canRob,
                            Hashtable htMap,
                            ref int maxAmount)
        {
            if (currentNode == null)
            {
                return;
            }

            string key = currentNode.GetHashCode().ToString() + "@" + canRob.ToString();
            if (htMap.ContainsKey(key))
            {
                maxAmount = (int)htMap[key];
                return;
            }

            int maxAmountLeft = 0;
            int maxAmountRight = 0;

            if (canRob)
            {
                //Will rob current
                MaxRob(currentNode.left, false, htMap, ref maxAmountLeft);
                MaxRob(currentNode.right, false, htMap, ref maxAmountRight);

                if (maxAmountLeft + maxAmountRight + currentNode.val > maxAmount)
                {
                    maxAmount = maxAmountLeft + maxAmountRight + currentNode.val;
                }
            }

            //Skip current
            maxAmountLeft = 0;
            maxAmountRight = 0;
            MaxRob(currentNode.left, true, htMap, ref maxAmountLeft);
            MaxRob(currentNode.right, true, htMap, ref maxAmountRight);

            if (maxAmountLeft + maxAmountRight > maxAmount)
            {
                maxAmount = maxAmountLeft + maxAmountRight;
            }

            if (!htMap.ContainsKey(key))
            {
                htMap.Add(key, maxAmount);
            }
        }
    }
}

Comments

  1. Cool problem! Since I'm a lazy potato I didn't bother using hashtable and used a RB-tree for a cache, but it's more than enough for good performance:

    using Cache = map, int>;
    class Solution {
    private:
    int rob(TreeNode* root, bool canRob, Cache& cache) {
    if (root == nullptr) return 0;
    pair key {root, canRob};
    auto cacheIt = cache.find(key);
    if (cacheIt != cache.end()) return cacheIt->second;
    int money = rob(root->left, true, cache) + rob(root->right, true, cache);
    if (canRob) money = max(money, root->val + rob(root->left, false, cache) + rob(root->right, false, cache));
    cache[key] = money;
    return money;
    }
    public:
    int rob(TreeNode* root) {
    Cache cache;
    return rob(root, true, cache);
    }
    };

    Small nit for your implementation - you don't need if (!htMap.ContainsKey(key)) in the end, since you've already checked this at the beginning of your method and that's the actual reason why you had to compete the maxAmount in the first place :)

    ReplyDelete
  2. FYI: in C++ cache is actually not required to pass the tests ;) I used cache just to speed things up, even though technically the super simple solution below is good enough too:

    class Solution {
    private:
    int rob(TreeNode* root, bool canRob) {
    if (root == nullptr) return 0;
    int money = rob(root->left, true) + rob(root->right, true);
    if (canRob) money = max(money, root->val + rob(root->left, false) + rob(root->right, false));
    return money;
    }
    public:
    int rob(TreeNode* root) {
    return rob(root, true);
    }
    };

    ReplyDelete

Post a Comment

Popular posts from this blog

Changing the root of a binary tree

Prompt Engineering and LeetCode

ProjectEuler Problem 719 (some hints, but no spoilers)