For a given array of integers, find the maximum distance between 2 points (i and j) that have higher values than any element between them.
Example:
values: 0 10 8 9 6 7 4 10 0 index : 0 1 2 3 4 5 6 7 8
for the values above the solution is i=1, j=7, but
I can't see a solution in O(n) ... anyone ?
Rafals solution is good, but we can do without the stack and so save some memory.
Here is a short and efficient implementation in O(n) time:
def highDist(seq):
res, ltr, rtl = 0, 0, 0
for i in range(len(seq)):
if seq[i] >= seq[ltr]:
res = max(res, i-ltr)
ltr = i
if seq[-i-1] >= seq[-rtl-1]:
res = max(res, i-rtl)
rtl = i
return res
Run on the example input:
>>> print highDist([0, 10, 8, 9, 6, 7, 4, 10, 0])
6
>>> print highDist([0, 10, 8, 9, 6, 7, 4, 9, 0])
4
>>> print highDist([0, 10, 8, 9, 6, 7, 4, 7, 0])
2
>>> print highDist([])
0
The trick is, that if we have two points a and b s.t. everything between them is smaller than them, then the maximum distance we are searching for, is either |b-a| or entirely outside the range. Hence if we partition the entire sequence that way, one of them is the range we are searching for.
We can make the partition easily be creating an upsequence from each end.