Problem with "Number List" problem on HackerRank

[Pnerd]

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

Here's what I did at first, but I was getting the error

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:
        return 0
    if k < min(a):
        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

Error:
Wrong Answer

. What am I doing wrong here?

[Pnerd]

Duplicate post deleted

[Gribouillis]

I think the problem in the algorithm is that if a value val is the maximum of a subarray and this value is reached more than once in the subarray, your algorithm counts the subarray once for each of these values. You could perhaps correct this by replacing a[j] <= val with a[j] < val at line 23 in the last «while» loop. This would count the subarray only if val is the last instance of this value in the subarray.

I suggest a third recursive approach: let [i,j( be the set of indices of a subsequence

• Find recursively the number of subsequences for which j <= N // 2
  
• Find recursively the number of subsequences for which N // 2 <= i
  
• Find by scanning the array, the number of subsequences for which i < N // 2 < j. This can be done by a O(N) scanning of the array similar to what you are doing in the second algorithm
  

This algorithm apparently has complexity O(N log N)

[Gribouillis]

Here is my attempt on this problem. It works on the given micro test cases. Clearly, it needs more testing. Every list element is compared to K only once, meaning that it is a O(n) algorithm.

def getnum(L, K, a, b):
    if b <= a:
        return 0
    m = (a + b) // 2
    i = next((k for k in range(m-1, a-1, -1) if L[k] > K), a-1)
    j = next((k for k in range(m, b) if L[k] > K), b)
    if j == b:
        if i < a:
            return 0
        else:
            return (i - a + 1) * (b - a) + getnum(L, K, a, i)
    else:
        s = (j - a + 1) * (b - j) + getnum(L, K, j+1, b)
        if i < a:
            return s
        else:
            return s + (i - a + 1) * (j - a) + getnum(L, K, a, i)
        
def solve(L, K):
    return getnum(L, K, 0, len(L))

inp = """\
2
3 2
1 2 3 
3 1
1 2 3
"""

def main():
    import io
    f = io.StringIO(inp)
    ntcase = int(next(f).strip())
    for i in range(ntcase):
        N, K = (int(x) for x in next(f).strip().split())
        L = [int(x) for x in next(f).strip().split()]
        assert(len(L) == N)
        print(solve(L, K))

if __name__ == '__main__':
    main()

[Gribouillis]

Here is a much shorter attempt

def solve(L, K):
    n, s, p = len(L), 0, -1
    for i, x in enumerate(L):
        if x > K:
            s += (i - p) * (n - i)
            p = i
    return s

inp = """\
2
3 2
1 2 3 
3 1
1 2 3
"""

def main():
    import io
    f = io.StringIO(inp)
    ntcase = int(next(f).strip())
    for i in range(ntcase):
        N, K = (int(x) for x in next(f).strip().split())
        L = [int(x) for x in next(f).strip().split()]
        assert(len(L) == N)
        print(solve(L, K))

if __name__ == '__main__':
    main()

[Pnerd]

I think the problem in the algorithm is that if a value val is the maximum of a subarray and this value is reached more than once in the subarray, your algorithm counts the subarray once for each of these values. You could perhaps correct this by replacing a[j] <= val with a[j] < val at line 23 in the last «while» loop. This would count the subarray only if val is the last instance of this value in the subarray.

Thanks. That solved it. But I didn't really get why. Can you elaborate a little (maybe with an example)?