# longest symmetric sequence

Suppose we are given a $$n$$-vector $$A$$ of real numbers. We need to find the longest sequence of symmetrical numbers. The numbers $$a_i$$ and $$a_j$$ are symmetrical if they are located at the same distance from element $$a_k$$ and $$|a_i-a_j|< \epsilon$$, $$\forall i < j$$.

Question

Can it be done in less than $$O(n^2)$$ comparisons in the worst case?

A $$O(n^2)$$ algorithm is to check the condition $$|a_i-a_j|< \epsilon$$ for element $$a_k$$.

Example:

Input: 0.006, 0.0061, 0.0069, 0.0135, 0.0065, 0.0193, 0.0086, 0.005, 0.01, 0.035, 0.065, 0.085, 0.1236, 0.086, 0.066, 0.037, 0.0024, 0.0712, 0.0032, 0.0174, 0.1504

There are two possible candidates of length 3 or more in this input (green and red).

1 (green). $$a_k$$ is 0.0065, and we have four pairs whose maximum absolute difference is 0.0058.

2 (red). $$a_k$$ is 0.1236, and we have three pairs whose maximum absolute difference is 0.002.

Ouput

If $$\epsilon > 0.0058$$ then 0.035, 0.065, 0.085, 0.1236, 0.086, 0.066, 0.037

If $$\epsilon <0.0058$$ then 0.006, 0.0061, 0.0069, 0.0135, 0.0065, 0.0193, 0.0086, 0.005, 0.01

Edit. After the comment by @D.W. It shound be noted that can be situation either $$a_i = a_k$$ or $$a_j=a_k$$, i.e. there is no the element $$a_k$$.

• If the condition was $a_i=a_j$ (instead of $|a_i-a_j|<\epsilon$), then it could can be solved in $O(n \log n)$ time. Let $h(a_i,a_{i+1},\dots,a_j)$ be a rolling hash of $a_i,\dots,a_j$. After a $O(n)$-time precomputation, you can compute $h(a_i,\dots,a_j)$ or $h(a_j,\dots,a_i)$ in $O(1)$ time for any $i,j$. Then, for each $k$, use binary search on $t$ to find the largest $t$ such that there is a symmetric sequence of length $2t$ centered at $k$, i.e., s.t. $h(a_{k-1},\dots,a_{k-t})=h(a_{k+1},\dots,a_{k+t})$. Your problem seems harder. (But maybe with locality sensitive hashing...?)
– D.W.
Dec 27, 2023 at 23:55
• Shouldn’t the solution be the first nine numbers? Dec 29, 2023 at 3:11
• @gnasher729, you are right. I have edited the post.
– Nick
Dec 29, 2023 at 9:15

By comparing $$x_i$$ and $$x_{i+128}$$ for example you can find all k that could be in the middle of a sequence with 129 or more elements. With your typical data that might very much restrict the values k, or there might be none at all and you compare $$x_i$$ and $$x_{i+64}$$ and so on. (Adjust depending on the number of items).
In your example you would find that $$x_i$$ and $$x_{i+8}$$ are close enough only for i = 0 and then compare 1 vs 7, 2 vs 6 and 3 vs 5.