0
$\begingroup$

I reached a subproblem where I have an array of numbers (0 to n) un-sorted and I want to retrieve, for each element, the index of the farthest value from it to the RIGHT of that element.

Like

0 1 2 3 4 5 6 7 8 (indexes)
0 3 7 5 4 2 8 1 6 (array)

so the answer would be

6 6 7 7 6 6 7 8 -1

Can anyone suggest some algorithm so that this information can be retreived in O(n)

Farthest is in the sense of absolute difference of values. Hence it means for index i, the index j would be farthest if

 abs(arr[k] - arr[i]) is maximum at k=j for all k>i
$\endgroup$
6
  • 1
    $\begingroup$ (Please check the tag info on c++.) Please add to the question a definition of farthest - it might mean difference in index (granted, boring) as well as difference in value. $\endgroup$
    – greybeard
    Commented Jun 9, 2022 at 14:30
  • $\begingroup$ Pre-processing is typical in preparation of (independent) queries. A result like the answer presented would be 1) an output from an algorithm on a set 2) just the information to keep for answering queries of the form For index $i$, what is an index $j \gt i$ such that $|A_j-A_i| = \max(|A_k-A_i|, k \gt i)$? $\endgroup$
    – greybeard
    Commented Jun 9, 2022 at 14:40
  • 1
    $\begingroup$ Are the values permutation of the indices? $\endgroup$
    – Russel
    Commented Jun 9, 2022 at 14:48
  • $\begingroup$ I don't understand what "farthest value to the right" means. Why isn't the answer always the last item of the array? That's always the farthest away. Can you define what you want using mathematics? Why do you think it can be done in $O(n)$ time? Where did you encounter this task? Can you credit the original source? Perhaps it would help us understand what you're asking if you could give a reference or link to where you encountered this. $\endgroup$
    – D.W.
    Commented Jun 9, 2022 at 14:52
  • $\begingroup$ @Russel Yes these are indices $\endgroup$
    – mr.loop
    Commented Jun 9, 2022 at 15:03

2 Answers 2

3
$\begingroup$

Based on your sample, I would assume that farthest from $x$, means the value $y$ on the right of $x$ that maximizes $|x-y|$. And that's what I am using in my answer.

Observe that the farthest value is either the lowest or highest value among the elements on the right of $x$.

Let $min$ and $max$ be the inidices of the current minimum and maximum. Both are initially set to $n-1$. Let $A$ be your given array and $B$ be the array that will contain the index of the farthest value on the right. Initially $B[n-1] = - 1$. Let $i$ be the current index in $A$, which is initially set to $n-2$.

  1. If $|A[i] - A[min]|\ge |A[i] - A[max]| $, let $B[i] = min$, else $B[i] = max$.
  2. If $A[i] < A[min]$, $min=i$.
  3. If $A[i] > A[max]$, $max=i$.
  4. Decrement $i$. If $i>0$, go to step 1., else stop.
$\endgroup$
1
  • $\begingroup$ Amazing, we came up with nearly eaxct solutions $\endgroup$
    – mr.loop
    Commented Jun 9, 2022 at 15:11
2
$\begingroup$

I figured out that the maximum difference can only be found at the minimum or maximum value to the right of concerned value.

So, I start from end of the array in reverse order and keep track of max and min upto the traversed part (k to n-1)

Now, at each iteration, max(ele-min, max-ele) would be the answer for the element.

    int minI = idx.size()-1, maxI = idx.size()-1;
    vector<int> farthest(idx.size());

    for(int i=idx.size()-1; i!=-1; i--) {

        farthest[i] = ((idx[i]-idx[minI]) > (idx[maxI]-idx[i])) ? minI : maxI;
        minI = (idx[minI] > idx[i]) ? i : minI;
        maxI = (idx[maxI] > idx[i]) ? maxI : i;

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