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 the arr.
  • 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

Popular posts from this blog

Efficient Janitor

  The janitor of a high school is insanely efficient. By the end of the day, all of the waster from the trash cans in the school has been shifted into plastic bags which can carry waster weighting between 1.01 pounds and 3.00 pounds. All of the plastic bags must be dumped into the trash cans outside the school. The janitor can carry at most 3.00 pounds at once. One trip is described as selecting a few bags which together don't weigh more than 3.00 pounds, dumping them in the outdoor trash can and returning to the school. The janitor wants to make minimum number of trips to the outdoor trash can. Given the number of plastic bags, n and the weights of each bag, determine the minimum number of trips if the janitor selects bags in the optimal way. For example, given  n=5 , plastic bags weighing weights  [1.01, 1.99, 2.5, 1.5, 1.01] , the janitor can carry all of the trash out in 3 trips:  [1.01+1.99, 2.5, 1.5+1.01] Constraints 1 <= n <= 1000 1.01 <= weight <=...
Read more

Right Arrow Pattern

Write a program to print the Right Arrow Pattern. Input Format: Take an input Integer which is from stdin. Output Format: print Right Arrow pattern Example Input: 5 Output: ***** **** *** ** * ** *** **** ***** SOLUTION: n=int(input()) for i in range(n):     for j in range(2*i):      #for spaces as each i th row has 2*i spaces         print(" ",end="")     for k in range(n-i):     #for stars as each i th row has n-i stars         print("*",end="")          print("")                     # half pattern is completed here for i in range(2,n+1):     #range started from 2 as the single star at middle is already                                         ...
Read more

X Pattern

  Write a program to take String if the length of String is odd print X pattern otherwise print INVALID. Input Format: Take a String as input from stdin. Output Format: print the desired Pattern or INVALID. Example Input: edyst Output: e t d s y d s e t SOLUTION: s=input() l=len(s) if(l%2 != 0): for i in range(0,l): j=l-i-1 for k in range(0,l): if(k==i or k==j): print(s[k],end="") else: print(end=" ") print("") else: print("INVALID")
Read more