Thursday, October 27, 2016

LeetCode OJ - Path Sum III

Problem:

Please find the problem here.

Analysis:

Although LeetCode mark this problem as easy. I do not believe this is an easy problem. It took me a while to think through, at least.

Imagine a depth first traversal, at a node with depth $ d $, I have to check $ d $ possibility of forming the target sum, my best chance is to use a map, but the problem is that the map seems to change, so updating the map is a problem, how do I make that quick.

Solution:

This is one possible solution. We maintain a list of targets to reach and pass to the children.

For example, if the target to reach is 8, the root node is 10, therefore, to my children, the target to reach is {-2}.

Next, suppose the left child of the root node is -3, but I was trying to reach {-2}, therefore my new goal for that would be {1}, because if I had 1 at my children, 10 - 3 + 1 = 8.

Of course, at this point, we can also ignore the 10, and if I can reach 11, that is also okay because -3 + 11 = 8.

Therefore the target set to pass to the children of the left child is {1, 11}, and so on.

The key problem in the above is that we need to shift the values of the existing set, the general formula is as follow:

target_set = {target_set} - val union (sum - val)

Union a single value into a set is easy, but how do I shift all values quickly? The key idea to that is to have an offset variable instead. One can imagine an abstract data type that allow shifting all values by having an offset variable, we just need to adjust for it before we query the map.

Last but not least, the set could contain duplicates, and they must be accounted for more than 1 match.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/path-sum-iii/

#include "LEET_PATH_SUM_III.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_PATH_SUM_III
{
    struct TreeNode
    {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };

    class Solution
    {
    public:
        int pathSum(TreeNode* root, int sum)
        {
            int offset = 0;
            map<int, int> targets;
            return pathSum(root, sum, targets, offset, 0);
        }
    private:
        int pathSum(TreeNode* root, int sum, map<int, int>& targets, int& offset, int indent)
        {
            if (root == nullptr)
            {
                return 0;
            }
            /*
            for (int i = 0; i < indent; i++) { cout << " "; }
            cout << "Processing " << root->val << endl;
            for (int i = 0; i < indent; i++) { cout << " "; }
            for (auto t : targets)
            {
                cout << "(" << (t.first + offset) << ", " << t.second << "), ";
            }
            cout << endl;
            */
            int count = 0;
            if (root->val == sum)
            {
                // Special case, this is a sum of 1 value
                count++;
            }
            map<int, int>::iterator probe1 = targets.find(root->val - offset);
            if (probe1 != targets.end())
            {
                count += probe1->second;
            }

            offset -= root->val;
            int entry = sum - offset - root->val;
            map<int, int>::iterator probe2 = targets.find(entry);
            bool foundEntry = false;
            if (probe2 == targets.end())
            {
                targets.insert(pair<int, int>(entry, 1));
            }
            else
            {
                foundEntry = true;
                probe2->second++;
            }
            
            count += this->pathSum(root->left, sum, targets, offset, indent + 2);
            count += this->pathSum(root->right, sum, targets, offset, indent + 2);

            if (foundEntry)
            {
                targets[entry]--;
            }
            else
            {
                targets.erase(entry);
            }
            offset += root->val;

            return count;
        }
    };
};

using namespace _LEET_PATH_SUM_III;

int LEET_PATH_SUM_III()
{
    Solution solution;
    TreeNode a(10);
    TreeNode b(5);
    TreeNode c(-3);
    TreeNode d(3);
    TreeNode e(2);
    TreeNode f(11);
    TreeNode g(3);
    TreeNode h(-2);
    TreeNode i(1);
    a.left = &b;
    a.right = &c;
    b.left = &d;
    b.right = &e;
    c.right = &f;
    d.left = &g;
    d.right = &h;
    e.right = &i;

    cout << solution.pathSum(&a, 8) << endl;

    return 0;
}

No comments :

Post a Comment