0

I have an array which stores a set of positive x coordinates in sorted way, say arr={1, 4, 5, 9, 12, 45} etc.

And I have a maximum distance k which I can go from one point to another point let k=3. Now, given two points x and y(arr[x]<arr[y]) I need to determine if I can reach from x to y. I will be able to reach y from x if distance between every two hop is less that or equal to k.

Here suppose x=1 y=4 then I can go from 1->2 then 2->3 but since distance between 3 and 4 is greater than 3 I can't go so in this case I can't reach.

But if x=1 and y=2 then I can reach.

It can be simply solved with O(n). I have created a for loop from arr[x] to arr[y] and for each pair of points I check if distance between them is less than or equal to k.

But I want better algorithm. I am thinking of doing something like binary search. Can anybody please suggest a good algorithm?

Improve this question
5
  • Sharing your research helps everyone. Tell us what you've tried and why it didn’t meet your needs. This demonstrates that you’ve taken the time to try to help yourself, it saves us from reiterating obvious answers, and most of all it helps you get a more specific and relevant answer. Also see How to Ask. And please don't cross-post: stackoverflow.com/questions/24612244
    – gnat
    Commented Jul 7, 2014 at 14:39
  • i have created a for loop from arr[x] to arr[y] and for each pair of points i check if distance between them is less than or equal to k ig yes then i continue if not i stop because i cant go far but this has linear compleixity can i do better ? my array size is 100000.
    – biswpo
    Commented Jul 7, 2014 at 14:41
  • 2
    gnat means: Put your code on your question, so we can see it and analyze it.
    – Jorge Campos
    Commented Jul 7, 2014 at 15:39
  • Are you running the search multiple times, or just once? How many times? What are your data? What are your inputs? All of those questions need to be answered if we are talking about optimalizations.
    – Euphoric
    Commented Jul 8, 2014 at 5:59
  • what is the cardinality for the set of values of k. ie do you have lot of possible values of k? You can possibly optimize this if the number of possible k values is less than the size of array so that you can get O(1) time. Of course, this means some more memory as @david.pfx has pointed out.
    – InformedA
    Commented Jul 8, 2014 at 11:01

1 Answer 1

Reset to default
1

Lo0oks easy enough to do O(1) if you precompute all the answers.

  1. Generate a 2D array of maximum differences, such that maxdiff[x,y] = max(diff[x], diff[x+1]...diff[y]). Since x
  2. Note that maxdiff(x,y) = max(maxdiff(x,z), maxdiff(z,y)), so calculation of longer sequences reuses the work done on shorter ones. Build shortest paths first, then next shortest and so on.
  3. Result is true if maxdiff[x,y] <= k.

For a practical implementation I would memoise this. That is, calculate the results as needed and keep the result until it is needed again. Once you have built all the maxdiffs for x..y you have built all the shorter distances in between for later use.

This is a typical space-speed trade-off.

I believe this algorithm is O(nlogn) for a single value of (x,y,k), dropping asymptotically towards O(n) for a large input data set or if the same (x,y,k) occur frequently.

If the array is large it may be impractical to build the entire lookup table, but a combination of memoisation and a partially built table will still deliver returns for large input data sets.

Improve this answer
3
  • problem is my N is 100000 so i cant allocate a 2d array of 100000x100000
    – biswpo
    Commented Jul 8, 2014 at 7:08
  • also to generate the array we need o(N^2)
    – biswpo
    Commented Jul 8, 2014 at 7:21
  • 5
    See edit. Please note that I wrote this answer knowing perfectly well that some additional constraints would invalidate it. It is up to you to fully specific the constraints if you want an answer that satisfies them.
    – david.pfx
    Commented Jul 8, 2014 at 10:44

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.