## Thursday, August 17, 2017

### LeetCode OJ - Maximum Binary Tree

Problem:

Solution:

This is basically asking for building a Cartesian tree, we will incrementally build it from left to right.

The base case is trivial, a Cartesian with a no node is null, a Cartesian tree with a single node is also trivial.

Given a Cartesian tree and then we wanted to add one node to it's right, how do we do it?

The first observation is that it has to be a right-most node, so the most obvious thing to do is to start with the current right-most node and see how we can patch the tree there.

If the value of the node we wanted to add to the tree is smaller than the current right-most value, we are lucky, we can simply add that as the right child of the current right-most node, and that's it, we get a new Cartesian tree!

If we are not so lucky, then what? We know that the new node must be higher up in the tree, so we go to the parent of the right-most node and try again, eventually we will go to the root and we will find one.

Once we find the right spot to put the new node in, the updating of the tree is easy.

Analysis:

The not-so-trivial fact is that this algorithm runs in linear time. The key observation is that once a node on the current right-most spine of the tree is less than a new node, it will never be on the right-most spine again. Therefore, we can account for the cost of comparison at node insertion time. That means the overall cost is $O(n)$.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/maximum-binary-tree

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

using namespace std;

namespace _LEET_MAXIMUM_BINARY_TREE
{

struct TreeNode
{
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution
{
public:
TreeNode* constructMaximumBinaryTree(vector<int>& nums)
{
int n = nums.size();
if (n == 0)
{
return nullptr;
}

vector<int> parent;
vector<TreeNode*> nodes;
parent.resize(n);
nodes.resize(n);

parent[0] = -1;
nodes[0] = new TreeNode(nums[0]);
TreeNode* root = nodes[0];

for (int i = 1; i < n; i++)
{
nodes[i] = new TreeNode(nums[i]);
nodes[i]->left = nullptr;
nodes[i]->right = nullptr;

int parent_candidate = i - 1;
int child_candidate = -1;
while (nums[i] > nums[parent_candidate])
{
child_candidate = parent_candidate;
parent_candidate = parent[parent_candidate];

if (parent_candidate == -1)
{
break;
}
}

if (child_candidate != -1)
{
nodes[i]->left = nodes[child_candidate];
parent[child_candidate] = i;
}
parent[i] = parent_candidate;
if (parent_candidate != -1)
{
nodes[parent_candidate]->right = nodes[i];
}
else
{
root = nodes[i];
}

}

return root;
}
};

void Dump(TreeNode* node, int indent)
{
if (node != nullptr)
{
for (int i = 0; i < indent; i++)
{
cout << " ";
}
cout << node->val << endl;
Dump(node->left, indent + 2);
Dump(node->right, indent + 2);
}
}
};

using namespace _LEET_MAXIMUM_BINARY_TREE;

int LEET_MAXIMUM_BINARY_TREE()
{
Solution solution;
int test1[] = { 3,2,1,6,0,5 };
TreeNode* answer = solution.constructMaximumBinaryTree(vector<int>(test1, test1 + _countof(test1)));
return 0;
}

## Saturday, August 12, 2017

### LeetCode OJ - Print Binary Tree

Problem:

Analysis:

The height of a binary tree is easy to find. I claim that the width is simply $2^h - 1$.

It is trivial for tree of height 1, for tree with height $h + 1$, one of the sub-tree must be of height $h$, by induction we can assume its width is $2^h - 1$, now the another side by have exactly the same width by the rules, therefore the total width is $2(2^h - 1) + 1 = 2^{h + 1} - 1$. Therefore we proved my claim with induction.

Solution:

With the width, it is relatively easy to code the solution. We will do that in two passes, in the first pass, we compute the height, and therefore the width, with that, we allocate the result, and we use another pass to fill in the array.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/print-binary-tree

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

using namespace std;

namespace _LEET_PRINT_BINARY_TREE
{
struct TreeNode
{
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution
{
public:
vector<vector<string>> printTree(TreeNode* root)
{
int height;
getHeight(root, &height);
int width = 0;
for (int i = 0; i < height; i++)
{
width = 2 * width + 1;
}
vector<vector<string>> result;
result.resize(height);
for (int i = 0; i < height; i++)
{
result[i].resize(width);
}
fillTree(root, width, 0, 0, result);
return result;
}

void getHeight(TreeNode* node, int* pHeight)
{
if (node == nullptr)
{
*pHeight = 0;
}
else
{
int leftHeight;
int rightHeight;
getHeight(node->left, &leftHeight);
getHeight(node->right, &rightHeight);
*pHeight = max(leftHeight, rightHeight) + 1;
}
}

void fillTree(TreeNode* node, int width, int height, int offset, vector<vector<string>>& result)
{
if (node != nullptr)
{
ostringstream sout;
int mid = width / 2;
sout << node->val;
result[height][offset + mid] = sout.str();
fillTree(node->left, mid, height + 1, offset, result);
fillTree(node->right, mid, height + 1, mid + 1 + offset, result);
}
}
};
};

using namespace _LEET_PRINT_BINARY_TREE;

int LEET_PRINT_BINARY_TREE()
{
Solution solution;
TreeNode a(2);
TreeNode b(1);
TreeNode c(3);
a.left = &b;
a.right = &c;
b.left = nullptr;
b.right = nullptr;
c.left = nullptr;
c.right = nullptr;
vector<vector<string>> result = solution.printTree(&a);
for (int i = 0; i < result.size(); i++)
{
for (int j = 0; j < result[i].size(); j++)
{
cout << "'" << result[i][j] << "',";
}
cout << endl;
}
return 0;
}

## Saturday, August 5, 2017

### LeetCode OJ - Set Mismatch

Problem:

Solution:

My idea is sorting - if we sort the array, then we basically get the answer. A naive sorting would take $O(n \log n)$ time, but a simple one could be done by pushing numbers.

In particular, imagine the numbers are put in the array like stone put in boxes. Let's start from a box where it has a wrong number to begin with, take the number away the slot, we have an empty box there and a stone outside.

But we know where that stone should go, there could be a few cases:

Case 1: The box has the right number already

This is easy, we have found our duplicate!

Case 2: The box is empty.

Just put the right number in, and try another slot with a wrong number.

Case 3: The box has a wrong number.

In this case, we pick the wrong number up and put the right number in, and do the whole thing again.

Eventually, we will find the duplicate. Once we have the duplicate known, we can easily find the missed number by comparing the sums.

Consider the difference of expected sum - actual sum, every number in the sums should cancel out except the missing number - the duplicated number, so if we know the duplicated number, the missing number can be calculated by the sums.

Analysis:

The algorithm is fine, but is it fast? We claim the algorithm is linear. Computing sum is linear, trying the slot is linear, the only unclear part is how many iterations the while loop could run, while a single instance of the while loop could be bad, we claim that the total number of iterations for all while loop iteration must be $O(n)$, this is because for each iteration that does not end the while loop, the iteration must bring one slot from its incorrect state to its correct state, that can happen only once per slot. Therefore we claim this is a linear time algorithm.

Moreover, this obviously does not take up extra space, this should be optimal. We could have also solve this problem with a hash table or another array with the same size, but that would mean extra space.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/set-mismatch/description/

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

using namespace std;

namespace _LEET_SET_MISMATCH
{
class Solution
{
public:
vector<int> findErrorNums(vector<int>& nums)
{
vector<int> result;
int n = (int)nums.size();
int duplicated = -1;
int sum = 0;
int correct_sum = (n + 1) * n / 2;
for (int i = 0; i < n; i++)
{
sum += nums[i];
}
for (int i = 1; i <= n; i++)
{
int value = i;
int index = value - 1;

if (nums[index] == value)
{
continue;
}

value = nums[index];
nums[index] = -1;
index = value - 1;

while (true)
{
if (nums[index] == value)
{
duplicated = value;
break;
}
else if (nums[index] == -1)
{
nums[index] = value;
break;
}
else
{
int next_value = nums[index];
nums[index] = value;
value = next_value;
index = value - 1;
}
}

if (duplicated != -1)
{
break;
}
}
result.push_back(duplicated);
result.push_back(correct_sum - sum + duplicated);
return result;
}
};
};

using namespace _LEET_SET_MISMATCH;

int LEET_SET_MISMATCH()
{
Solution solution;
int test_array[] = { 2, 4, 1, 2 };
vector<int> test(test_array, test_array + _countof(test_array));
vector<int> result = solution.findErrorNums(test);
cout << result[0] << " " << result[1] << endl;
return 0;
}

## Sunday, June 25, 2017

### LeetCode OJ - Merge Two Binary Trees

Problem:

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;

return 0;
}

## Sunday, May 28, 2017

### LeetCode OJ - Subtree of Another Tree

Problem:

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:

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;
}