Crests and Troughs
Given an array of n
elements, find out all the crests and troughs along with their lengths. Find the absolute difference between the indexes of longest and shortest crests as well as troughs and display the maximum of both.
- An element is said to be
crest
if both it's previous and next elements are less than the current element. - An element is said to be
trough
if both it's previous and next elements are greater than the current element.
Note: The first and last elements are neither crests nor troughs.
In case of multiple occurrences of shortest crest/trough consider the left most one as shortest and right most one as longest.
Print -1
if at least one crest and trough doesn't exist.
Try to finish the task using O(1)
extra space and traversing the array only once.
Input Format
- The first line contains an integer,
t
denoting the number of test cases. - The first line of each test case contains an integer,
n
denoting the size of thearr
. - The second line of each test case contains
n
space-separated integers describing the elements of array.
Constraints
4<=n<=109
0<=arr[i]<=n
Output Format
For every test case print the required output in a new line.
Sample Input 0
1 8 3 6 2 8 9 5 10 1
Sample Output 0
2
Explanation 0
The crest with maximum length(length-->10-1=9) exists at index 6.
The crest with minimum length(length-->9-8=1) exists at index 4.
The trough with maximum length(length-->8-2=6) exists at index 2.
The trough with minimum length(length-->6-2=4) exists at index 2 (troughs with length 4 exists at two indexes 2 and 5, but take trough at index 2 as shortest trough as it is left most).
Print 2
as (difference between indexes of longest and shortest crests) 6-4 > 2-2 (difference between indexes of longest and shortest troughs).
Solution:
t=int(input())
for i in range(t):
n=int(input())
a=list(map(int,input().split()))
c=0
max_c_i={}
min_c_i={}
max_t_i={}
min_t_i={}
for i in range(1,len(a)-1):
if(a[i]>a[i-1] and a[i]>a[i+1]):
c=c+1
max_c_i[i]=max(a[i]-a[i-1],a[i]-a[i+1])
min_c_i[i]=min((a[i]-a[i-1]),(a[i]-a[i+1]))
elif(a[i]<a[i-1] and a[i]<a[i+1]):
c=c+1
max_t_i[i]=max((a[i-1]-a[i]),(a[i+1]-a[i]))
min_t_i[i]=min((a[i-1]-a[i]),(a[i+1]-a[i]))
if(c!=0):
mxc_i=max(max_c_i,key=max_c_i.get)
mnc_i=min(min_c_i,key=min_c_i.get)
mxt_i=max(max_t_i,key=max_t_i.get)
mnt_i=min(min_t_i,key=min_t_i.get)
p=abs(mxt_i-mnt_i)
q=abs(mxc_i-mnc_i)
print(max(p,q))
else:
print("-1")
Comments
Post a Comment