I can think of improvement over O(n^2), but need to verify if this is O(n) in worse case or not.
- Create a variable
BestSoln=0; and traverse the array for first element
and store the best solution for first element i.e bestSoln=k;.
- Now for 2nd element consider only elements which are
k distances away
from the second element.
- If
BestSoln in this case is better than first iteration then replace
it otherwise let it be like that. Keep iterating for other elements.
It can be improved further if we store max element for each subarray starting from i to end.
This can be done in O(n) by traversing the array from end.
If a particular element is more than it's local max then there is no need to do evaluation for this element.
Input:
{9, 2, 3, 4, 5, 6, 7, 8, 18, 0}
create local max array for this array:
[18,18,18,18,18,18,18,0,0] O(n).
Now, traverse the array for 9 ,here best solution will be i=0,j=8.
Now for second element or after it, we don't need to evaluate. and best solution is i=0,j=8.
But suppose array is Input:
{19, 2, 3, 4, 5, 6, 7, 8, 18, 0,4}
Local max array [18,18,18,18,18,18,18,0,0] then in first iteration we don't need to evaluate as local max is less than current elem.
Now for second iteration best solution is, i=1,j=10. Now for other elements we don't need to consider evaluation as they can't give best solution.
Let me know your view your use case to which my solution is not applicable.
lg Nfactor in its big-O complexity, might have to do with the solution? The array is unsorted. The question asks for two elements in it that are farthest apart which satisfy an inequality.