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:

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

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

Ref