1
$\begingroup$

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

enter image description here

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

enter image description here

$\endgroup$
3
  • 1
    $\begingroup$ 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...?) $\endgroup$
    – D.W.
    Dec 27, 2023 at 23:55
  • 1
    $\begingroup$ Shouldn’t the solution be the first nine numbers? $\endgroup$
    – gnasher729
    Dec 29, 2023 at 3:11
  • $\begingroup$ @gnasher729, you are right. I have edited the post. $\endgroup$
    – Nick
    Dec 29, 2023 at 9:15

1 Answer 1

1
$\begingroup$

The way your condition is written, it could be that almost all elements are considered equal. That will be hard to handle efficiently.

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.