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?
5
Lo0oks easy enough to do O(1) if you precompute all the answers.
- Generate a 2D array of maximum differences, such that maxdiff[x,y] = max(diff[x], diff[x+1]…diff[y]). Since x
- 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.
- 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.
3