Problem with "Number List" problem from HackerRank

Python Help
1

I’m trying to solve the Number List problem from HackerRank

Here’s what I did at first, but I was getting the error “time limit exceeded”:

def solve(a, k):
    N = len(a)
    # s_max contains the max elements of each contiguous subarray
    s_max=[max(a[i:i+j]) for i in range(0,N) for j in range(1,N-i+1)]
    s_max.sort()
     
    l = 0
    r = len(s_max)-1
    while True:
        mid = (r+l)//2
        if mid == l:
            return len(s_max)-r
        elif s_max[mid] <= k:
            l = mid
        else:
            r = mid

The double for loop thing while creating s_max was probably the problem here. For large lists a , this would take a lot of time.

The next thing I tried was this: for each number ‘n’ in array a , if it’s larger than k, find out in how many subarrays it is the maximum. It can be done by counting elements to the left of ‘n’ till I get something larger, and then doing the same thing on the right. Then the number of such subarrays where n>k and ‘n’ is the max = product of those two ‘left’ and ‘right’ numbers. This is my code:

def solve(a, k):
    N = len(a)
    if max(a) < k:  # no subarray will have a max > k
        return 0
    if k < min(a):  # all subarrays will have max > k
        return N*(N+1)//2
    cnt = 0
    for ind, val in enumerate(a):
        if val > k:
            # count subarrays where val > k and val=max(subarray) 
            # and val is the rightmost element
            j = ind-1
            left = 1
            while j >= 0 and a[j] <= val:
                left += 1
                j -= 1
             
            # count subarrays where val > k and val=max(subarray) 
            # and val is the leftmost element
            right = 1
            j = ind+1
            while j < N and a[j] <= val:
                right += 1
                j += 1
                 
            # total subarrays with max(subarray) > k 
            cnt += left * right    
    return cnt

This did solve the problem of “time limit exceeded”, but in two test cases, I’m getting the error “Wrong Answer”. What am I doing wrong here?