#### 1. Background

##### 1.1 All nearest smaller values problem

Given an array A[0..n-1], for each element in A, search among the previous positions for the nearest position that contains a smaller value.
Formally, we need to find L[0..n-1] s.t.

`L[i] = max{j ∈ [0..i − 1] : A[j] < A[i]}`

example:
A = [1, 4, 3, 9, 10, 5]
L = [-1, 0, 0, 2, 3, 2]

When in high school, I was taught 2 algorithms to solve this problem:

• Using monotonic stack in O(n). We will get back to this topic in another post.
• One simpler algorithm just use 2 nested loops (it is trivial that I cannot give it a name).
###### 1.1.a
``````L = -1;
for(int i = 1; i < n; i++) {
int j = i - 1;
while (j != -1 && A[j] >= A[i]) j = L[j];
L[i] = j;
}
``````

I prefer the second algorithm because it is simple and fast. However, for years, I cannot prove its runtime complexity until recently when I encountered a paper about LRM tree - Left-to-Right-Minima tree. Turns out, we can use a LRM tree lemma to prove its runtime of O(n).

#### 2. Left-to-Right-Minima Tree (LRM-Tree)

Consider an array A[1..n] of n value, all >= A = −∞. The LRM-Tree of A is a tree with n+1 vertices, each labeled uniquely from {0, . . . , n} such that for 1 ≤ i ≤ n, L[i] is the parent node of i. The children of each node are ordered in increasing order from left to right. For example: An example of an array and its LRM-Tree. The numbers at the nodes are the array values, and the smaller numbers in parentheses are their positions in the array.

A = 9
L = 7 because A = 1 is the nearest smaller element to the left of A. So `L = 7` will be parent of node `9` in LRM-Tree

###### Lemma:

Given an array A[1..n], there is an algorithm computing its LRM-Tree in at most 2(n − 1) comparisons within A.

###### Proof

We can build the LRM-Tree as follow:

• let A = −∞ be the root of the tree
• scan over array A, starting from A, for each element A[i]: starting from the `rightmost` node of the tree, climb up toward the root until encountering a node x such that A[x] < A[i].
• let i be child of x. Now i will be the new `rightmost` node of the tree

For example, now we are adding A = 9 to the tree:

Starting from the current rightmost element `A = 10`, we follow the rightmost path and climb up toward root (the red path):

• A = 10 > A, so we climb to its parent A
• A = 1 < A, so we stop, and let A be child of A. A = 9 now is the new rightmost node

For each new node A[i] adding to the tree, we charge it one comparison when comparing A[i] with its parent. After being added to the tree, A[i] stays on the `rightmost` path and will be used to compare with A[i+1] at most once because after that it will be removed from the rightmost path. For example, after we use A to compare with A, it will be removed from the red path.

Thus, each element is charged at most 2 comparisons. Finally, the last element A[n] is never scanned, and the first element A is inserted without any comparison. Hence the total number of comparisons is at most 2(n-1).

We can easily see that the algorithm we use to construct the LRM-tree is the same as what we do in `1.1.a` to find L[1..n], so the runtime of the `1.1.a` algorithm is O(n).

From now, I will call this algorithm as `LRM-tree` algorithm. We can use it to solve the All nearest bigger values problem also.

``````rightBigger[n-1] = -1;
for(int i = n-2; i >= 0; i--) {
int j = i + 1;
while (j != -1 && A[j] <= A[i]) j = rightBigger[j];
rightBigger[i] = j;
}

leftBigger = -1;
for(int i = 1; i < n; i++) {
int j = i - 1;
while (j != -1 && A[j] <= A[i]) j = leftBigger[j];
leftBigger[i] = j;
}
``````

#### Application

We can use LRM-tree, we can solve a lot of problems

1. Directly use LRM-tree
1. Histogram problem

Find the maximum rectangle in histogram: result = max(A[i] * (R[i] - L[i] - 1))

1. Cartesian Tree
Cartesian Tree is a binary tree derived from an array A[0..n-1] of unique values. It is built as following:
• Create a root node whose value is the minimum value in A.
• Recursively build the left subtree on the subarray prefix to the left of the minimum value.
• Recursively build the right subtree on the subarray suffix to the right of the minimum value.

Compute `leftSmaller[0..n-1]` and `rightSmaller[0..n-1]` of `A[0..n-1]` using LRM-tree algorithm. Cartesian Tree has a special property: the parent of node `i` in the Cartesian tree is either `leftSmaller[i]` or `rightSmaller[i]`, whichever exists and has a larger value.

Here is the code to build a Maximum Cartesian Tree. Runtime is the same as LRM-tree: O(n).

``````/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:

TreeNode* getNode(int index) {
if (nodeMap.find(index) != nodeMap.end()) return nodeMap[index];
auto p = new TreeNode(a[index]);
nodeMap[index] = p;
return p;
}

unordered_map<int, TreeNode*> nodeMap;
vector<int> a;

TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
int ma = 0, maxIndex;
a = nums;
int n = a.size();

for(int i = 0; i < n; i++) {
if (a[i] > ma) {
ma = a[i];
maxIndex = i;
}
}

int left[n], right[n];
left = -1;
for(int i = 1; i < n; i++) {
int j = i-1;
while (j != -1 && a[j] <= a[i]) j = left[j];
left[i] = j;
}

right[n-1] = -1;
for(int i = n-2; i >= 0; i--) {
int j = i+1;
while (j != -1 && a[j] <= a[i]) j = right[j];
right[i] = j;
}

for(int i = 0; i < n; i++)
if (i != maxIndex) {
int l = left[i];
int r = right[i];
auto c = getNode(i);
if (l == -1) {
getNode(r)->left = c;
} else if (r == -1) {
getNode(l)->right = c;
} else {
if (a[l] < a[r]) {
getNode(l)->right = c;
} else {
getNode(r)->left = c;
}
}
}