## Tuesday, September 12, 2017

### LeetCode OJ - Convert BST to Greater Tree

Problem:

Analysis:

It is a binary search tree, it is easy to iterate though the values in order. If we iterate them from greatest to smallest, it is easy to maintain the sum of the greater numbers.

Solution:

So all it remains is to create an iterator. For the fun of it, I tried to build it in a co-routine style, manually playing the role of a compiler to insert the right jumps. To read the code, manually set current and return true with an imaginary "yield return " statement, that should explain why I set the state and why I use those goto statements.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/convert-bst-to-greater-tree

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

using namespace std;

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

class ReverseOrderIterator
{
private:
int m_state;
TreeNode* m_current;
TreeNode* root;
ReverseOrderIterator* m_rightIterator;
ReverseOrderIterator* m_leftIterator;
public:
ReverseOrderIterator(TreeNode* root)
{
this->root = root;
this->m_state = 1;
}

bool MoveNext()
{
if (this->m_state == 2)
{
goto label2;
}
else if (this->m_state == 3)
{
goto label3;
}
else if (this->m_state == 4)
{
goto label4;
}
if (root == nullptr)
{
return false;
}
this->m_rightIterator = new ReverseOrderIterator(root->right);
while (this->m_rightIterator->MoveNext())
{
this->m_state = 2;
this->m_current = this->m_rightIterator->Current();
return true;
label2:
{

}
}
delete this->m_rightIterator;
this->m_state = 3;
this->m_current = root;
return true;
label3:
this->m_leftIterator = new ReverseOrderIterator(root->left);
while (this->m_leftIterator->MoveNext())
{
this->m_state = 4;
this->m_current = this->m_leftIterator->Current();
return true;
label4:
{

}
}
delete this->m_leftIterator;
return false;
}

TreeNode* Current()
{
return this->m_current;
}
};

class Solution
{
public:
TreeNode* convertBST(TreeNode* root)
{
bool first = true;
int sum = 0;
int last_value_before = 0;
int last_value_change = 0;

ReverseOrderIterator* iterator = new ReverseOrderIterator(root);
while (iterator->MoveNext())
{
TreeNode* current_node = iterator->Current();
if (first)
{
sum = last_value_before = last_value_change = current_node->val;
first = false;
}
else
{
int current_value = current_node->val;
sum = sum + current_value;
if (current_value == last_value_before)
{
current_node->val = last_value_change;
}
else
{
last_value_before = current_value;
current_node->val = last_value_change = sum;
}
}
}
delete iterator;
return root;
}
};
};

using namespace _LEET_CONVERT_BST_TO_GREATER_TREE;

int LEET_CONVERT_BST_TO_GREATER_TREE()
{
TreeNode a(2);
TreeNode b(1);
TreeNode c(2);
a.left = &b;
a.right = &c;
b.left = c.left = nullptr;
b.right = c.right = nullptr;
Solution s;
s.convertBST(&a);
cout << b.val << endl;
cout << a.val << endl;
cout << c.val << endl;
return 0;
}

### LeetCode OJ - Diameter of Binary Tree

Problem:

Analysis:

It is tempted to just find the height of the left sub-tree and the right sub-tree, sum them up, and then plus 1, we get the answer, but that's wrong, because in this tree, the correct answer is 7.

Solution:

Armed with this observation, the answer is easy. The answer is max of left diameter, right diameter and (left height + right height + 1).

Code:

#include "stdafx.h"

// https://leetcode.com/problems/diameter-of-binary-tree

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

using namespace std;

namespace _LEET_DIAMETER_OF_BINARY_TREE
{
struct TreeNode
{
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution
{
public:
void diameterOfBinaryTree(TreeNode* node, int* pSolution, int* pHeight)
{
if (node == nullptr)
{
*pSolution = 0;
*pHeight = 0;
}
else
{
int leftSolution;
int leftHeight;
int rightSolution;
int rightHeight;

diameterOfBinaryTree(node->left, &leftSolution, &leftHeight);
diameterOfBinaryTree(node->right, &rightSolution, &rightHeight);

*pHeight = 1 + max(leftHeight, rightHeight);
*pSolution = max(max(leftHeight + 1 + rightHeight, leftSolution), rightSolution);
}
}
int diameterOfBinaryTree(TreeNode* root)
{
if (root == nullptr)
{
return 0;
}
int solution;
int height;
diameterOfBinaryTree(root, &solution, &height);
return solution - 1;
}
};
};

using namespace _LEET_DIAMETER_OF_BINARY_TREE;

int LEET_DIAMETER_OF_BINARY_TREE()
{
Solution s;
TreeNode a(1);
TreeNode b(2);
TreeNode c(3);
TreeNode d(4);
TreeNode e(5);
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;
cout << s.diameterOfBinaryTree(&a) << endl;
return 0;
}

## Tuesday, August 29, 2017

### HackerRank - Almost sorted interval

Problem:

Solution:

To get started, my idea is to count all almost sorted interval by counting how many of them ends at position $i$. It is trivial that there is only one position ends at position 0, but how about position $k$?

A brute force way of thinking is that we try, for each possible index before $k$, is it a valid almost sorted interval, there are two possible ways that a interval fail to be almost sorted, basically, the first one is not minimal, and the last one is not maximal.

If we were to do it brute force, it would be $O(n^3)$, bad. The first observation is that if there are any index before $k$ has a value larger than the one at $k$, there is no need to try anything earlier, in other words, we can start the search for minimal elements there.

With the same token, there is no need to try $p$ if we know $q > p$ has a value smaller than $p$.

These observation leads to the idea of building up of two stacks.

The minimum stack consist of numbers that is minimum with respect to its right hand side up to $k$
The maximum stack consist of number that is maximum with respect to its right hand side up to $k$

We will use the maximum stack to help us find where to start the search, and the minimum stack to count how many elements are eligible to be the start of the almost sorted interval.

It is best illustrated with the example [3,1,2,5,4]

The min stack and the max stack values are listed below:

min     max
[3]     [3]
[1]     [3,1]
[1,2]   [3,2]
[1,2,5] [5]
[1,2,4] [4]

Now we can enumerate the almost sorted intervals as follow:

min     max   almost sorted intervals
[3]     [3]   [3]
[1]     [3,1] [1]
[1,2]   [3,2] [1,2] [2]
[1,2,5] [5]   [1,2,5] [2,5] [5]
[1,2,4] [4]   [4]

The way it works is that you use the max stack to find, where to start enumerating. Once you know where to start enumerate, just go through the values in the min stack.

I call them stacks because they can be built like a stack, just pop away the invalid entries and push the current value in. We will see this algorithm is fast in the analysis.

The key problem remains now is how to make the enumeration fast. Note that if we actually enumerate all the intervals, there will be a $O(n^2)$ cost, which is not good enough, all we need to finally output is the count, so we will NOT enumerate and output only the count.

That leads to two sub-problems, how do I find the starting min stack element fast, and how do I count how many min stack elements are there on the right fast.

The second problem is easy, if we know the stack node, we can simply store the number of elements on its left in the stack node (in fact, if the stack is implemented as an array, the left count is simply its index!). With the left count and the total count, we can compute the right count easily.

The former problem is harder, note that both stacks are, by construction, sorted by position. If the stacks are implemented as array, we can simply binary search them, that will lead to $O(n \log n)$

We can actually do faster (at least, asymptotically). The idea is that the max stack node can be used as a position index to find the min stack node directly. The only problem with that approach is that the element to the right of the max stack node might not be in the min stack anymore, but a min stack node associated with that index must have existed.

What if - at the time of popping - we make the min stack node corresponding to the popped node points to the node currently at the top of the stack right after pop? That worked for a while until this case happen.

min stack   index
[a b c d e] [a b c d e]     pop e,d and push f
[a b c f]   [a b c c c f]   pop f,c,b and push g
[a g]       [a a a c c a g]

Apparently, some $c$ are not properly renamed to $a$, causing problems. With this visualization, I suddenly realize disjoint set union find could be used. Instead of changing the popped node to the top node right about pop, we model them as disjoint set and union them, that will allow them to stay the same identity, even after the second pop as follow:

min stack   index
[a b c d e] [a b c d e]     pop e,d and push f
[a b c f]   [a b c c c f]   pop f,c,b and push g
[a g]       [a a a a a a g]

That conclude our thinking, how I constructed the solution.

There are a couple details in the code that worth explaining. The zero based index of the node has to be incremented by 1 to form the left count. Therefore we have an extra minus one after the finding the index of the left set. There is a special case in which all nodes are popped, in that case we give that disjoint set an identity of $n$ and an index of $-1$, that allow us to use the same formula to compute the left count, which should be $0$.

Analysis:

Here we prove the algorithm has complexity $O(n \log^* n)$.

The key observation is that each element enter the stack exactly once, and leave the stack at most once, therefore all the stack operations together take $O(n)$ time.

For each element pop, we do a union, and for each element, we used one find operation, together, we have $O(n)$ number of disjoint set operations, therefore we have spent $O(n \log^* n)$ with the disjoint set operations.

The overall complexity is $O(n \log^* n)$.

Code：

#include "stdafx.h"

// https://www.hackerrank.com/challenges/almost-sorted-interval

#include "HACKER_RANK_ALMOST_SORTED_INTERVAL.h"
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

namespace _HACKER_RANK_ALMOST_SORTED_INTERVAL
{
int set_union(int set1, int set2, int* set)
{
int size1 = -set[set1];
int size2 = -set[set2];
int size = size1 + size2;
if (size1 > size2)
{
set[set2] = set1;
set[set1] = -size;
return set1;
}
else
{
set[set1] = set2;
set[set2] = -size;
return set2;
}
}

int set_find(int x, int* set)
{
if (set[x] < 0)
{
return x;
}
else
{
return (set[x] = set_find(set[x], set));
}
}

int HACKER_RANK_ALMOST_SORTED_INTERVAL()
{
int n;
cin >> n;
int* input = new int[n];

int min_stack_size = 0;
int max_stack_size = 0;
int* min_stack_elements = new int[n];
int* max_stack_elements = new int[n];

int* min_stack_node_set = new int[n + 1];
int* min_stack_node_pos = new int[n + 1];

long long result = 0;

for (int i = 0; i < n; i++)
{
cin >> input[i];
}

for (int i = 0; i < n + 1; i++)
{
min_stack_node_set[i] = -1;
min_stack_node_pos[i] = -1;
}

for (int current_position = 0; current_position < n; current_position++)
{
int current_value = input[current_position];
int old_min_stack_size = min_stack_size;
while (min_stack_size > 0 && input[min_stack_elements[min_stack_size - 1]] > current_value)
{
min_stack_size--;
}
for (int i = min_stack_size; i < old_min_stack_size; i++)
{
int canon = min_stack_size == 0 ? n : min_stack_elements[min_stack_size - 1];
int left = set_find(canon, min_stack_node_set);
int right = set_find(min_stack_elements[i], min_stack_node_set);
int merge = set_union(left, right, min_stack_node_set);
min_stack_node_pos[merge] = min_stack_node_pos[left];
}
while (max_stack_size > 0 && input[max_stack_elements[max_stack_size - 1]] < current_value)
{
max_stack_size--;
}
min_stack_elements[min_stack_size++] = current_position;
max_stack_elements[max_stack_size++] = current_position;

min_stack_node_pos[current_position] = min_stack_size - 1;

if (max_stack_size == 1)
{
result += min_stack_size;
}
else
{
int after_position = max_stack_elements[max_stack_size - 2];
int min_node_at_of_before_after_position = set_find(after_position, min_stack_node_set);
result += min_stack_size - min_stack_node_pos[min_node_at_of_before_after_position] - 1;
}
}

cout << result << endl;
delete[] input;

return 0;
}
}

using namespace _HACKER_RANK_ALMOST_SORTED_INTERVAL;

int HACKER_RANK_ALMOST_SORTED_INTERVAL()
{
return _HACKER_RANK_ALMOST_SORTED_INTERVAL::HACKER_RANK_ALMOST_SORTED_INTERVAL();
}

## Friday, August 25, 2017

### LeetCode OJ - Remove 9

Problem:

Analysis:

It is interesting to look into the problem geometrically.

0  1  2  3  4  5  6  7  8  9
10 11 12 13 14 15 16 17 18 19
20 21 22 23 24 25 26 27 28 29
.............................
90 91 92 93 94 95 96 97 98 99

In this view, we can see that for numbers in [0, 81), we can find the corresponding value by fitting it in a 9 x 9 square with each row starting from a multiple of 10.

In particular, the last digit of the number has to be n % 9, that should work for all n since every row has 9 elements.

The interesting way to look at it further is to look at the next digit.

0  10  20  30  40  50  60  70  80  90
100 110 120 130 140 150 160 170 180 190
200 210 220 230 240 250 260 270 280 290
.......................................
900 910 920 930 940 950 960 970 980 990

This time around, we need to move 9 numbers (in the input space) at a time to move one unit in this box, that is, the next least significant digit (in the output space) has to be $\lfloor \frac{n}{9} \rfloor$ % 9.

Now the solution is pretty obvious.

Solution:

Just compute the base 9 representation of the number, and then interpret it as a base 10 number.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/remove-9

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

using namespace std;

namespace _LEET_REMOVE_9
{
class Solution
{
public:
int newInteger(int n)
{
if (n < 9)
{
return n;
}
else
{
return newInteger(n / 9) * 10 + n % 9;
}
}
};
};

using namespace _LEET_REMOVE_9;

int LEET_REMOVE_9()
{
Solution solution;
for (int i = 1; i <= 80; i++)
{
cout << solution.newInteger(i) << endl;
}
return 0;
}

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