#### 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 uses 2 nested loops (it is trivial that I cannot give it a name).
###### 1.1.a
L[0] = -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 could not prove its runtime complexity until recently when I encountered a paper about the LRM tree - Left-to-Right-Minima tree. Turns out, we can use an 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[0] = −∞. 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:

A[9] = 9
L[9] = 7 because A[7] = 1 is the nearest smaller element to the left of A[9]. So L[9] = 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[0] = −∞ be the root of the tree
• scan over array A, starting from A[1], 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 the child of x. Now i will be the new rightmost node of the tree

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

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

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

For each new node A[i] added 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[8] to compare with A[9], 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[1] 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[0] = -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[0] = -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;
}
}
}