#### 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[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 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[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 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] 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[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

- Directly use LRM-tree

- [E] https://leetcode.com/problems/next-greater-element-i/
- [M] https://leetcode.com/problems/next-greater-element-ii/
- [M] https://leetcode.com/problems/online-stock-span/
- [H] https://leetcode.com/problems/number-of-valid-subarrays/
- [M] https://leetcode.com/problems/sum-of-subarray-minimums/
- for each element A[i], find the number of subarray having A[i] as mininum value =
`(i-L[i]) * (R[i]-i)`

- for each element A[i], find the number of subarray having A[i] as mininum value =
- [M] https://leetcode.com/problems/132-pattern/
`min[i] = min{A[0..i]}`

- for each k: if
`L[k] != -1 && min[L[k]] < A[k]`

then return true

- Histogram problem

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

- [H] https://leetcode.com/problems/largest-rectangle-in-histogram/
- [H] https://leetcode.com/problems/maximal-rectangle/
- build the histogram for each row, the apply above problem

- [H] https://leetcode.com/problems/count-submatrices-with-all-ones/
- build the histogram for each row i,
`fx[j]`

is the number submatrices with all ones having rightmost column at column j and the bottom row at row i:`fx[j] = fx[L[j]] + histogram[j] * (j - L[j])`

- build the histogram for each row i,

- 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).

[M] https://leetcode.com/problems/maximum-binary-tree/

```
/**
* 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) {
TreeNode* head;
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;
}
}
head = new TreeNode(ma);
nodeMap[maxIndex] = head;
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;
}
}
}
return head;
}
};
```