##### Problem with "Number List" problem on HackerRank
 Problem with "Number List" problem on HackerRank Pnerd Programmer named Tim Posts: 7 Threads: 3 Joined: Feb 2021 Reputation: Apr-09-2022, 12:25 AM (This post was last modified: Apr-09-2022, 01:30 AM by 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? Reply Pnerd Programmer named Tim Posts: 7 Threads: 3 Joined: Feb 2021 Reputation: Apr-09-2022, 12:40 AM (This post was last modified: Apr-09-2022, 12:40 AM by Pnerd.) Duplicate post deleted Reply Gribouillis Posts: 3,749 Threads: 54 Joined: Jan 2018 Reputation: Apr-09-2022, 07:15 AM (This post was last modified: Apr-09-2022, 07:16 AM by 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 subsequenceFind 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 Gribouillis Posts: 3,749 Threads: 54 Joined: Jan 2018 Reputation: Apr-09-2022, 01:49 PM (This post was last modified: Apr-09-2022, 01:49 PM by 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()``` Reply Gribouillis Posts: 3,749 Threads: 54 Joined: Jan 2018 Reputation: Apr-10-2022, 08:16 AM (This post was last modified: Apr-10-2022, 08:19 AM by 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()``` Reply Pnerd Programmer named Tim Posts: 7 Threads: 3 Joined: Feb 2021 Reputation: Apr-12-2022, 12:25 AM (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