You are viewing a single comment's thread. Return to all comments →
Surely that's O(N) space. There's no need to store the array itself. Just record the update boundaries along with the k value (-k for the end boundary), sort them by location (then by value if at the same location), then scan over them with a running total.
Yes, that makes more sense and saves on memory and running time. Using a defaultdict in Python:
from collections import defaultdict
sums = defaultdict(int)
_, n_ranges = (int(x) for x in input().split())
for _ in range(n_ranges):
start, stop, value = (int(x) for x in input().split())
sums[start] += value
sums[stop+1] -= value
max_val = running_val = 0
for _, val in sorted(sums.items()):
running_val += val
max_val = max(max_val, running_val)
it is great that we don't have to store every key.
n, m = input().strip().split(' ')
n, m = [int(n), int(m)]
l =  * (n+1)
for a0 in range(m):
a, b, k = input().strip().split(' ')
a, b, k = [int(a), int(b), int(k)]
l[a:b+1] = list(map(lambda x:x+k,l[a:b+1]))
The above code is showing runtime error for test case 7 onwards. please suggest the reason?
I experience the same issue. If I run test case 13 locally, my code passes, but if I try the same code remotely on HR, cases 7 -> 13 all fail. Out of memory ?
why deleted :(
Most of the peope solved this problem but time complexity of solution is O(n*m) (due to two nested for loops)which can not be used to solve this problem for given time constraint, so you need better approach which beats O(n*m)
I have created a video tutorial for you and uploaded the same on youtube with complete explanation along with code complexity analysis.
Here is the video tutorial for my solution O(n+m) complexity passed all test cases.
Would really appreciate your feedback like, dislike , comment etc. on my video.
I too tried the same approach. Yes, It's giving runtime error.
Brilliant. It seems like the runtime error has since been fixed.