# Count unique increasing subsequences of length 3 in $O(n\log n)$

Problem: Given an array of $n$ integers, $A[1 \dots n]$, such that any integer occurs at most 2 times in the array, we have to find the number of unique increasing subsequences of length 3 (duplicate subsequences must be counted only once). In other words, we have to count the number of unique integers $A[i], A[j], A[k]$ such that $A[i] < A[j] < A[k]$ with $i < j < k$.

I have been stuck on this for quite a while now. I did look up this question which tests for the existence of such a triplet. But I think my question is different because it needs the count, and because it needs unique triplets (upto 1 repetition of any number is allowed).

Idea: $O(n^2)$ algorithm. For each number, we can scan the remaining array and find out how many unique numbers are greater than it and occur after it. This can be done in $O(n^2)$ by naive brute force. For every pair of numbers ($O(n^2)$), we now have the number of possible triplets that can be formed by using the pair as the first two numbers of the triplet (since we know how many are greater than the second number).

Unfortunately, $O(n^2)$ is too slow, and I need a faster solution - $O(n\log n)$ or $O(n)$. Space complexity also has to be sub-quadratic. I was thinking along the lines of sorting a copy of the array to find out the relative rank of each element, but could not go any further. Any help or hints are greatly appreciated!

• You need this for sequences of length 3? – user742 Dec 15 '12 at 15:05
• I wonder what the question to count "unique sequences" means. Does it mean we just count a sequence that occurs several times just once? Or not at all as it fails to be unique? – Hendrik Jan Dec 15 '12 at 15:07
• Here's an idea. First, process the array so that you can find the number of integers larger than $A[j]>k$ with $j>i$ quickly. This can be done using something like quad-trees or $k$-$d$ trees. Second, use the data structure created in the first step to answer the question. – Peter Shor Dec 15 '12 at 15:53
• @SaeedAmiri Yes, increasing subsequences of length 3. – mayank Dec 15 '12 at 16:27
• @PeterShor I would be much obliged if you could explain your algorithm in the form of an answer. I am not sure I understand why an element $A[j]$ is compared with an index $k$. Also, how are $k$-$d$ trees or quad-trees used for one dimensional data, or is some other parameter making it 2-D? Thank you! – mayank Dec 16 '12 at 11:40

Here is an algorithm to count distinct subsequences of length $3$ in time $O(n \log n)$, regardless of how many times any value $a$ occurs in $A[j]$.

First, create a binary search tree $T$ containing all possible values $a = A[j]$, storing at each node how many times it occurs in $A$, and how many nodes there are which follow it in the tree (are further to the right) representing larger values $A[k]$. Note that with each insertion (and later, removals), the tally of further-right values will become out of date for many of the nodes. However, we can maintain these values for each node lazily, by maintaining at each parent node a count of the pending counter updates for its left and right subtrees. (When we later traverse to a child node, its own counter of larger elements, and its pending-update counters for its children can be adjusted by the amount indicated by its parent.) Similarly, any insertions or removals in the right subtree of a node leads to a pending update for the left subtree. This should also be implementable for balanced trees as well, such as AVL trees or red-black trees. We will henceforth suppose that as we traverse any particular node that its counter is thereby kept up-to-date, though it may become out of date in between visitations. Constructing $T$ takes time $O(n \log n)$.

We traverse $A$ once more, creating a tree $F$ which also contains values $a = A[j]$ and the number of nodes to the left of each node, similarly to $T$. (We also maintain a separate counter at each node of $F$ of how many nodes have been added to its left since the last time we look up the node in the tree; this uses a similar update method as the total-counter, though because we would clear this counter each time the node is visited, in practise we just use the pending-update value for its parent node.) At the same time we will be disassembling the tree $T$, and counting distinct increasing subsequences in $A$ of length 3 by considering, using $F$ and $T$, how many different values of $a'$ and $a''$ can serve as the first and respectively third value in an ordered triple $(a',A[j],a'')$. We do this as follows.

Set $N := 0$. For each $1 \leqslant j \leqslant n$ in order, do the following:

• Let $a := A[j]$. Decrement the occurance counter of $a$ in $T$. This takes time $O(\log n)$.

• Search for $a$ in $F$. If it is not present, insert it, and set $$\text{incr} := \#(\text{nodes left of a in F}) \cdot \#(\text{nodes right of a in L}).$$ Otherwise, if $a$ is already present, set $$\text{incr} := \#(\mathop{*}\text{newly added}\mathop{*} \text{ nodes left of a in F}) \cdot \#(\text{nodes right of a in L}).$$ This takes time $O(\log n)$ as well.

• Add $\text{incr}$ to $N$.

• If the occurances counter of $a$ in $T$ has dropped to $0$, remove $a$ from $T$. This takes time $O(\log n)$.

[Edited to add: as Peter Shor notes in the comments, rather than storing in $T$ the number of times $a$ occurs in $A$, we can simply store the last index $1 \leqslant j \leqslant n$ such that $a = A[j]$ for the purposes of this algorithm. Then, rather than actually removing $a$ from $T$, we can just perform the decrement of the further-right tallies for all of the nodes to its left. The decrease in arithmetic and tree-modification operations would give rise to some modest savings in run-time.]

The total run-time of this algorithm is $O(n \log n)$. In each iteration of the loop above, we only count the number of ways in which elements smaller than $a$ which haven't been used yet as a subsequence starter can be combined with elements larger than $a$ which still have at least one occurance later in the list, with $a$ itself in the middle. Thus, we count the number of "newly possible" subsequences there are for each $A[j]$ as new first elements are made available for each remaining available third element, and accumulating them for $1 \leqslant j \leqslant n$.

• Thank you! I have so far only got upto the part of creation of trees, and have some questions. By a binary tree, do you mean a binary search tree? More specifically, a balanced BST? Since if I understood correctly, the tree creation will degenerate to $O(n^2)$ if the input is sorted. Also, pending count sort of does lazy propagation, right? – mayank Dec 16 '12 at 11:34
• I'm probably being stupid here, but I don't see how to build the binary tree $T$ without using quad-trees (or $k$-$d$ trees). The rest of your answer is very nice, and I think I see how to make everything work using quad-trees. – Peter Shor Dec 17 '12 at 2:40
• @mayank: I have in mind AVL trees or red-black trees, which have worst-case $O(\log n)$ insertion (and consequently have $O(n \log n)$ construction time). Also mayank, you're right that the propagation of the pending count being a sort of lazy update mechanism, which takes advantage of the hierarchical structure of the tree to allow each update to be done in time $O(\log n)$ as well, during the course of traversing a branch of the tree which would take $O(\log n)$ time to do anyway. – Niel de Beaudrap Dec 17 '12 at 12:18
• @PeterShor: The tree $T$ is only storing possible values of the third element of the tuple, as we traverse the array $A$. Possibly there is some equivalent algorithm which involves one quad-tree instead of two; I found this a more natural structure to formulate the algorithm, as I have no practical experience designing algorithms with quad-trees. – Niel de Beaudrap Dec 17 '12 at 12:20
• @Niel: thanks; that comment made it much clearer. It might be easier to update the counts only with the insertion of the last copy of $a$. That way, I think you don't have to deal with removals. – Peter Shor Dec 17 '12 at 13:00