hieuza
BAN USER
Comments (3)
Reputation 5
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
My algorithm:
* an array imin[i] is the index of min element of subarray 0..i
* run from right to left, maintain imax is the index of the max element in subarray i..n-1
* a triplet: imin[i] < i < imax
Code in Python
def find_ijk(a):
if len(a) < 3:
return None
imin = [0]*len(a)
for i in xrange(1, len(a)):
imin[i] = imin[i - 1]
if a[i] <= a[imin[i]]:
imin[i] = i
imax = len(a) - 1
for i in xrange(len(a) - 2, 0, -1):
if a[i] < a[imax] and i > imin[i]:
return imin[i], i, imax
if a[i] > a[imax]:
imax = i
return None
Comment hidden because of low score. Click to expand.
Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
My algorithm, run in O(n), space O(1).
- hieuza October 28, 2012