Python Forum
Problem with "Number List" problem on HackerRank
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Problem with "Number List" problem on HackerRank
#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
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?
Reply
#2
Duplicate post deleted
Reply
#3
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)
Reply
#4
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()
Reply
#5
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()
Reply
#6
(Apr-09-2022, 07:15 AM)Gribouillis Wrote: 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)?
Reply


Possibly Related Threads…
Thread Author Replies Views Last Post
  pickle problem DPaul 13 313 Sep-27-2022, 05:25 PM
Last Post: DPaul
  Problem with BlackJack JengaBenga 0 66 Sep-27-2022, 02:07 PM
Last Post: JengaBenga
  List Sorting Problem ZZTurn 5 265 Sep-22-2022, 11:23 PM
Last Post: ZZTurn
  Problem with GridSearchCV ghnunes 0 235 Aug-23-2022, 02:11 PM
Last Post: ghnunes
  logging problem korenron 0 234 Jul-20-2022, 08:51 AM
Last Post: korenron
  TypeError: float() argument must be a string or a number, not 'list' Anldra12 2 407 Jul-01-2022, 01:23 PM
Last Post: deanhystad
  Need help solving a problem rufenghk 7 705 Jun-04-2022, 10:15 PM
Last Post: rufenghk
  How do I solve the second problem? Cranberry 1 462 May-16-2022, 11:56 AM
Last Post: Larz60+
  Split a number to list and list sum must be number sunny9495 5 824 Apr-28-2022, 09:32 AM
Last Post: Dexty
  Matplotlib Problem DaveG 0 560 Mar-14-2022, 04:05 AM
Last Post: DaveG

Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020