# Fast algorithm for linear context finding

I am trying to figure out a quick algorithm which solves the following problem.

For the rest of this question, assume $0\in\mathbb{N}$.

Denote by $\mathbb{R}^\mathbb{N}$ the set of all real sequences and by $\mathbb{N}^\mathbb{N}$ the set of all natural sequences. The algorithm should emulate a function $F:\mathbb{R}^\mathbb{N}\to\mathbb{N}^\mathbb{N}$ which can be defined as follows: given a real sequence $\{x_n\}$, $F(\{x_n\}) = \{y_n\}$, where $y_n$ is the maximum natural number for which both $y_n\le n$ and $x_{n-i} < x_n$ for all $0<i\le y_n$.

The emulation is of the following sense: the algorithm should receive floats, one by one, and for the float $x_n$ return the integer $y_n$. By quick I mean of linear speed. The naive algorithm is $O(n^2)$.

Note: there is a similar (?) algorithm which for a given positive integer $n$, receives a sequence of floats and returns for each the maximal value among the last $n$ received values, which is linear.

You can solve this in $O(n \lg n)$ time through an appropriate use of interval trees.

I'm going to explain how to process the $x$'s in an incremental, streaming fashion. So, suppose we've already received $x_1,\dots,x_n$. Define the sequence $m_1,\dots,m_n$ by $m_i=\max(x_i,x_{i+1},\dots,x_n)$. In previous processing, we'll have accumulated a data structure that summarizes the sequence $m_1,\dots,m_n$. This data structure supports two kinds of operations:

• $\text{find}(\alpha)$: given a real number $\alpha$, return the largest index $i$ such that $m_i<\alpha$ but $m_{i-1}\ge \alpha$.

• $\text{append}(x_{n+1})$: given the value of $x_{n+1}$, update the data structure to reflect that we've now received $x_1,\dots,x_{n+1}$. In other words, the data structure should now summarize the sequence $m'_1,\dots,m'_{n+1}$ where $m'_i = \max(x_i,x_{i+1},\dots,x_{n+1})$.

Given such a data structure, it is easy to see how to process the $x$'s in a streaming way. When we receive $x_{n+1}$, we first set $y_{n+1} = \text{find}(x_{n+1})$ and then execute $\text{append}(x_{n+1})$ to update the data structure. We iteratively repeat this for each $x$-value we receive.

I'm going to show a data structure that supports each of these two operations in $O(\lg n)$ time. This shows that we solve this problem, for the sequence $x_1,\dots,x_n$, in $O(n \lg n)$ time.

So, how do we build the data structure to represent the sequence $m_1,\dots,m_n$ and enable us to update it rapidly? We'll use an interval tree.

Consider the mapping from $\{1,2,\dots,n\} \to \mathbb{R}$ given by $i \mapsto m_i$. We want to represent this mapping efficiently. We'll do this by actually building a mapping from a set of intervals to $\mathbb{R}$, where the intervals are disjoint and their union is $\{1,2,\dots,n\}$. Whenever we have a consecutive sequence $j,j+1,\dots,k$ of indices that all map to the same value (i.e., where $m_j = m_{j+1} = \dots = m_k$), we'll collapse them into a single interval $[j,k]$. The interval tree will record the mapping $[j,k] \mapsto m_j$, which is a compact way of representing the mapping $j \mapsto m_j$, $j+1 \mapsto m_j$, $\ldots$, $k \mapsto m_j$.

Suppose we've decomposed $\{1,2,\dots,n\}$ into $k$ intervals. Our data structure will be a (balanced) binary tree with $k$ leaves, where each leaf corresponds to one of these $k$ intervals, and the leaves are in sorted order. At each internal node, we'll record the interval that covers the union of intervals at all the leaves underneath that node. Also, at each leaf, we'll record the corresponding value of $m$ (e.g., at the leaf for $[j,k]$, we'll record the value of $m_j$, which is of course the same as the value for $m_{j+1}$ and $\ldots$ and $m_k$). At each internal node, we'll record the minimal and maximum values of $m$ at all of the leaves underneath that node. This forms a binary search tree on intervals, where the search key at a node is the minimum $m$-value for the subtree rooted at that node. Since the intervals are disjoint, everything is nice and clean.

Notice that the $m_i$'s are in decreasing order, i.e., $m_1\ge m_2 \ge \dots \ge m_n$. This will help us implement both operations that the data structure needs to support. In particular, we can think of the search key at a node as the index of the left endpoint of the interval covered by the subtree rooted at that node, or we can think of the search key as the maximum $m$-value for the subtree rooted at that node.

To implement $\text{find}(\alpha)$, it's easy to traverse the tree to find the rightmost interval whose $m$-value is smaller than $\alpha$. Return the index $i$ of the left endpoint of this interval. This operation can be implemented in $O(\lg n)$ time, since we only need to traverse the search tree from the root down to an appropriate leaf.

To implement $\text{append}(x_{n+1})$, we find the rightmost interval whose $m$-value is smaller than $x_{n+1}$ and let $i$ be the left endpoint of this interval. Then, we delete this interval and every interval to its right from the interval tree. Next, we add the interval $[i,n+1]$ to the interval tree, with $m$-value $x_{n+1}$. Each of these steps can be done in $O(\lg n)$ time, so this operation can also be implemented in $O(\lg n)$ time.

• This is simply a wonderful answer. – Bach Oct 28 '13 at 13:16

You can solve this in $O(n \lg^2 n)$ time.

Build a (balanced) binary tree with $n$ nodes, where the leaves are annotated with the values $x_1,x_2,\dots,x_n$, and $x_i$ is placed on the $i$th leaf from the left. Annotate each internal node $v$ in the tree with the maximum value over all the leaves in the subtree rooted at $v$. For instance, the root is annotated with $\max(x_1,x_2,\dots,x_n)$. The tree and the annotations can be built in $O(n)$ time.

Next, note that, for any $j,k$, a sequence $x_j, x_{j+1}, \dots, x_k$ of consecutive leaves can be covered by some union of $O(\lg n)$ subtrees. In particular, given any $j,k$, we can compute $\max(x_j,x_{j+1},\dots,x_k)$ in $O(\lg n)$ time, by traversing the tree and using the annotations on the internal nodes at the top of those $O(\lg n)$ subtrees.

Now, to compute $y_k$, we do a binary search to find the largest $j$ such that $\max(x_j,x_{j+1},\dots,x_{k-1})<x_k$ but $\max(x_{j-1},x_j,x_{j+1},\dots,x_{k-1})\ge x_k$. Each iteration of the binary search takes $O(\lg n)$ time, and the binary search takes at most $O(\lg n)$ iterations, so this allows us to compute each $y_k$ in $O(\lg^2 n)$ time.

Finally, there are $n$ $y$-values that we want to compute, so the total running time is $O(n \lg^2 n)$.

This can be adjusted to work in an incremental/online/streaming fashion, with $O(\lg^2 n)$ running time per value of $x$ received, by tweaking the structure of the binary tree appropriately.

It's possible you might be able to get a slightly better solution by using 2-D range trees, where you store the $n$ points $(i,x_i)$ in the tree (for $i=1,2,\dots,n$). However, I'm not certain.

• Thanks, that answer is great. I'll have a deeper look into it. – Bach Oct 28 '13 at 12:27