Sunday, June 25, 2017

LeetCode OJ - Merge Two Binary Trees

Problem:

Please find the problem here.

Solution:

We basically walk the two trees at the same time, if a node is found on both tree, we create a new node and sum them up, if not, we take the non-null one (without cloning - as an optimization). Of course, it is possible that both trees are null after we walk, in that case we simply return null.

Analysis:

The algorithm above is optimal because in the worst case, the two trees have identical structure and one must walk the two trees to compute the sum for each nodes.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/merge-two-binary-trees

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

using namespace std;

namespace _LEET_MERGE_TWO_BINARY_TREES
{
    struct TreeNode
    {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };
    class Solution
    {
    public:
        TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2)
        {
            if (t1 == nullptr)
            {
                return t2;
            }
            else if (t2 == nullptr)
            {
                return t1;
            }
            else
            {
                TreeNode* left = mergeTrees(t1->left, t2->left);
                TreeNode* right = mergeTrees(t1->right, t2->right);
                TreeNode* result = new TreeNode(t1->val + t2->val);
                result->left = left;
                result->right = right;
                return result;
            }
        }
    };
};

using namespace _LEET_MERGE_TWO_BINARY_TREES;

int LEET_MERGE_TWO_BINARY_TREES()
{
    Solution solution;
    TreeNode l1(1);
    TreeNode l2(3);
    TreeNode l3(2);
    TreeNode l4(5);

    TreeNode r1(2);
    TreeNode r2(1);
    TreeNode r3(3);
    TreeNode r4(4);
    TreeNode r5(7);

    l1.left = &l2;
    l1.right = &l3;
    l2.left = &l4;
    l2.right = nullptr;
    l3.left = nullptr;
    l3.right = nullptr;
    l4.left = nullptr;
    l4.right = nullptr;

    r1.left = &r2;
    r1.right = &r3;
    r2.left = nullptr;
    r2.right = &r4;
    r3.left = nullptr;
    r3.right = &r5;
    r4.left = nullptr;
    r4.right = nullptr;
    r5.left = nullptr;
    r5.right = nullptr;

    TreeNode* answer = solution.mergeTrees(&l1, &r1);
    cout << answer->val << endl;
    cout << answer->left->val << endl;
    cout << answer->right->val << endl;
    cout << answer->left->left->val << endl;
    cout << answer->left->right->val << endl;
    cout << answer->right->right->val << endl;
    return 0;
}

Sunday, May 28, 2017

LeetCode OJ - Subtree of Another Tree

Problem:

Please find the problem here.

Analysis:

In this problem, I didn't spend much time to optimize the solution. It is a simple dirty yet $ O(n) $ solution. I simply computed the in-order traversal of both trees, and I claim that if the string representation matches, it must be an identical sub-tree.

Solution:

The key thing that we need to worry about is whether or not a substring match is due to reason other than a complete sub-tree matches, for example, the substring match was due to taking some data in the earlier subtrees or some later subtrees. It is made impossible by adding the brackets. The bracket helped us to make sure in the parent string the substring is properly parenthesized, so it has to be a subtree and a subtree alone. The commas are also important, it make sure we cannot concatenate numbers differently to yield the same string.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/subtree-of-another-tree

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

using namespace std;

namespace _LEET_SUBTREE_OF_ANOTHER_TREE
{
    struct TreeNode
    {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };
    class Solution
    {
    public:
        void ToString(TreeNode* s, ostringstream& sout)
        {
            if (s == nullptr)
            {
                sout << "#" << ",";
            }
            else
            {
                sout << "(";
                ToString(s->left, sout);
                sout << s->val;
                sout << ",";
                ToString(s->right, sout);
                sout << ")";
            }
        }
        bool isSubtree(TreeNode* s, TreeNode* t)
        {
            ostringstream sout;
            ostringstream tout;
            ToString(s, sout);
            ToString(t, tout);
            string sstr = sout.str();
            string tstr = tout.str();
            const char* x = strstr(sstr.c_str(), tstr.c_str());
            return (x != nullptr);
        }
    };
};

using namespace _LEET_SUBTREE_OF_ANOTHER_TREE;

int LEET_SUBTREE_OF_ANOTHER_TREE()
{
    TreeNode a(3);
    TreeNode b(4);
    TreeNode c(5);
    TreeNode d(1);
    TreeNode e(2);
    a.left = &b;
    a.right = &c;
    b.left = &d;
    b.right = &e;
    c.left = nullptr;
    c.right = nullptr;
    d.left = nullptr;
    d.right = nullptr;
    e.left = nullptr;
    e.right = nullptr;

    TreeNode p(4);
    TreeNode q(1);
    TreeNode r(2);
    p.left = &q;
    p.right = &r;
    q.left = nullptr;
    q.right = nullptr;
    r.left = nullptr;
    r.right = nullptr;

    Solution s;
    cout << (s.isSubtree(&a, &p) ? "True" : "False") << endl;
    return 0;
}

LeetCode OJ - Permutation in String

Problem:

Please find the problem here.

Analysis:

The idea is that we can check if two strings are equal to each other by comparing their histogram.

Solution:

We can easily compute the histogram of the s2, but for s1, we need a sliding histogram. Fortunately, computing a sliding histogram is pretty easy and simply take $ O(1) $ time to slide it. It is also $ O(1) $ time to compare two histograms since the strings only has lower case letters.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/permutation-in-string

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

using namespace std;

namespace _LEET_PERMUTATION_IN_STRING
{
    class Solution {
    public:
        bool checkInclusion(string s1, string s2)
        {
            if (s1.length() > s2.length())
            {
                return false;
            }
            char fixed_histogram[26];
            char slide_histogram[26];
            for (int i = 0; i < 26; i++)
            {
                fixed_histogram[i] = slide_histogram[i] = 0;
            }
            for (size_t i = 0; i < s1.length(); i++)
            {
                fixed_histogram[s1[i] - 'a']++;
                slide_histogram[s2[i] - 'a']++;
            }
            bool match = true;
            for (int i = 0; match && i < 26; i++)
            {
                match = fixed_histogram[i] == slide_histogram[i];
            }
            if (match)
            {
                return true;
            }
            for (size_t i = s1.length(); i < s2.length(); i++)
            {
                slide_histogram[s2[i - s1.length()] - 'a']--;
                slide_histogram[s2[i] - 'a']++;
                match = true;
                for (int i = 0; match && i < 26; i++)
                {
                    match = fixed_histogram[i] == slide_histogram[i];
                }
                if (match)
                {
                    return true;
                }
            }
            return false;
        }
    };
};

using namespace _LEET_PERMUTATION_IN_STRING;

int LEET_PERMUTATION_IN_STRING()
{
    Solution solution;
    cout << (solution.checkInclusion("ab", "eidbaooo") ? "True" : "False") << endl;
    return 0;
}

LeetCode OJ - Subarray Sum Equals K

Problem:

Please find the problem here.

Analysis:

We can use the running sum trick to reduce the problem of finding a sum to just do a subtraction. With that in mind, we are basically simply counting how many pairs of numbers in the running sum array such that when the right one subtracts the left one, yield $ k $.

Solution:

To find that count, we maintain a "wanted" list when we scan from left to right. The "wanted" list is basically a number such that if we encounter it in the future, it would make a right subtracted result. Building a wanted list is easy, and checking if it is wanted is also easy, so there we go.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/subarray-sum-equals-k

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

using namespace std;

namespace _LEET_SUBARRAY_SUM_EQUALS_K
{
    class Solution
    {
    public:
        int subarraySum(vector<int>& nums, int k)
        {
            int n = (int)nums.size();
            vector<int> running_sums;
            running_sums.resize(n + 1);
            running_sums[0] = 0;
            for (int i = 0; i < n; i++)
            {
                running_sums[i + 1] = nums[i] + running_sums[i];
            }
            map<int, int> wanted_count;
            int result = 0;
            for (int i = 0; i < (n + 1); i++)
            {
                auto probe1 = wanted_count.find(running_sums[i]);
                if (probe1 != wanted_count.end())
                {
                    result += probe1->second;
                }
                int wanted = k + running_sums[i];
                auto probe2 = wanted_count.find(wanted);
                if (probe2 == wanted_count.end())
                {
                    wanted_count.insert(make_pair(wanted, 1));
                }
                else
                {
                    probe2->second++;
                }
            }
            return result;
        }
    };
};

using namespace _LEET_SUBARRAY_SUM_EQUALS_K;

int LEET_SUBARRAY_SUM_EQUALS_K()
{
    Solution s;
    int input_array[] = { 1, 1, 1 };
    vector<int> input(input_array, input_array + _countof(input_array));
    cout << s.subarraySum(input, 2) << endl;
    return 0;
}

LeetCode OJ - Shortest Unsorted Continuous Subarray

Problem:

Please find the problem here.

Analysis:

Here is a simple observation, any element that is not the same as the sorted array need to be moved.

Solution:

Therefore the Shortest Unsorted Continuous Subarray must begin at the leftmost mismatch and ends with the rightmost mismatch.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/shortest-unsorted-continuous-subarray

#include "LEET_SHORTEST_UNSORTED_CONTINUOUS_SUBARRAY.h"
#include <map>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_SHORTEST_UNSORTED_CONTINUOUS_SUBARRAY
{
    class Solution
    {
    public:
        int findUnsortedSubarray(vector<int>& nums)
        {
            vector<int> sorted(nums.begin(), nums.end());
            sort(sorted.begin(), sorted.end());
            int result = (int)nums.size();
            int s = 0;
            while (s < nums.size() && nums[s] == sorted[s])
            {
                s++;
                result--;
            }
            int e = (int)(nums.size() - 1);
            while (e >= s && nums[e] == sorted[e])
            {
                e--;
                result--;
            }
            return result;
        }
    };
};

using namespace _LEET_SHORTEST_UNSORTED_CONTINUOUS_SUBARRAY;

int LEET_SHORTEST_UNSORTED_CONTINUOUS_SUBARRAY()
{
    Solution s;
    int input_array[] = { 2, 6, 4, 8, 10, 9, 15 };
    vector<int> input(input_array, input_array + _countof(input_array));
    cout << s.findUnsortedSubarray(input) << endl;
    return 0;
}

LeetCode OJ - Kill Process

Problem:

Please find the problem here.

Analysis:

This is really just a problem of finding all the nodes in a sub-tree.

Solution:

We begin with building the tree, and then finding the sub-tree using BFS.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/kill-process

#include "LEET_KILL_PROCESS.h"
#include <map>
#include <iostream>
#include <queue>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_KILL_PROCESS
{
    struct Node
    {
        int data;
        Node* child;
        Node* sibling;
    };
    class Solution {
    public:
        vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill)
        {
            map<int, Node*> nodes;
            Node* root = nullptr;
            size_t n = pid.size();
            for (size_t i = 0; i < n; i++)
            {
                Node* newNode = new Node();
                newNode->data = pid[i];
                newNode->child = newNode->sibling = nullptr;
                nodes.insert(make_pair(pid[i], newNode));
            }

            for (size_t i = 0; i < n; i++)
            {
                if (ppid[i] == 0)
                {
                    root = nodes[pid[i]];
                }
                else
                {
                    Node* curr = nodes[pid[i]];
                    Node* prev = nodes[ppid[i]];
                    curr->sibling = prev->child;
                    prev->child = curr;
                }
            }

            vector<int> result;
            queue<Node*> bfs;
            bfs.push(nodes[kill]);
            while (!bfs.empty())
            {
                Node* current = bfs.front();
                bfs.pop();
                result.push_back(current->data);
                Node* child = current->child;
                while (child != nullptr)
                {
                    bfs.push(child);
                    child = child->sibling;
                }
            }
            return result;
        }
    };
};

using namespace _LEET_KILL_PROCESS;

int LEET_KILL_PROCESS()
{
    Solution s;
    int pid_array[] = { 1,3,10,5 };
    int ppid_array[] = { 3,0,5,3 };
    vector<int> pid(pid_array, pid_array + _countof(pid_array));
    vector<int> ppid(ppid_array, ppid_array + _countof(ppid_array));
    vector<int> result = s.killProcess(pid, ppid, 5);
    for (size_t i = 0; i < result.size(); i++)
    {
        cout << result[i] << " ";
    }
    cout << endl;
    return 0;
}

LeetCode OJ - Longest Harmonious Subsequence

Problem:

Please find the problem here.

Analysis:

The key misleading word in the problem name is "subsequence". If we can pick non consecutive elements, and there is no requirement where the smallest and the largest is in the subsequence, the word subsequence can totally be replaced by subset. Once we have this realization, the rest is easy.

Solution:

To make calculation fast, we can build a histogram on counts of numbers by their value. Then we can search if there exists consecutive pairs. If we do, and have multiple of them, we can find the largest one.

I could have make this faster (e.g. $ O(n) $) by using a hash search instead, but this is simple and passes the judge.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/longest-harmonious-subsequence

#include "LEET_LONGEST_HARMONIOUS_SUBSEQUENCE.h"
#include <map>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

namespace _LEET_LONGEST_HARMONIOUS_SUBSEQUENCE
{
    class Solution
    {
    public:
        int findLHS(vector<int>& nums)
        {
            map<int, int> m;
            for (auto&& n : nums)
            {
                auto probe = m.find(n);
                if (probe == m.end())
                {
                    m.insert(make_pair(n, 1));
                }
                else
                {
                    probe->second++;
                }
            }
            vector<pair<int, int>> freq;
            for (auto&& p : m)
            {
                freq.push_back(p);
            }
            if (freq.size() < 2)
            {
                return 0;
            }
            else
            {
                int result = 0;
                for (size_t i = 1; i < freq.size(); i++)
                {
                    if (freq[i - 1].first + 1 == freq[i].first)
                    {
                        result = max(result, freq[i - 1].second + freq[i].second);
                    }
                }
                return result;
            }
        }
    };
};

using namespace _LEET_LONGEST_HARMONIOUS_SUBSEQUENCE;

int LEET_LONGEST_HARMONIOUS_SUBSEQUENCE()
{
    Solution s;
    int input_array[] = { 1,3,2,2,5,2,3,7 };
    vector<int> input(input_array, input_array + _countof(input_array));
    cout << s.findLHS(input) << endl;
    return 0;
}