This is the HackerRank problem Algorithmic Crush:
You are given a list of size
N
, initialized with zeroes. You have to performM
operations on the list and output the maximum of final values of all theN
elements in the list. For every operation, you are given three integersa
,b
andk
. The valuek
needs to be added to all the elements ranging from index a throughb
(both inclusive).Input Format
The first line will contain two integers
N
andM
separated by a single space.
The nextM
lines will each contain three integersa
,b
andk
separated spaces.
The numbers in the list are numbered from1
toN
.Output Format
A single integer on a separate line line containing maximum value in the updated list.
Constraints
\$3 ≤ N ≤ 10^7\$
\$1 ≤ M ≤ 2 \cdot 10^5\$
\$1 ≤ a ≤ b ≤ N\$
\$0 ≤ k ≤ 10^9\$Sample input:
5 3 1 2 100 2 5 100 3 4 100
Sample output:
200
Explanation
After the first update, the list will be
100 100 0 0 0
.
After the second update, the list will be100 200 100 100 100
.
After the third update, the list will be100 200 200 200 100
.
So, the required answer will be200
.
This is my Python 3 solution:
tempArray = [int(n) for n in input().split(" ")]
N = tempArray[0]
M = tempArray[1]
arr = [0 for x in range(N)]
for i in range(0,M):
tempArray = [int(n) for n in input().split(" ")]
for j in range(tempArray[0]-1, tempArray[1]):
arr[j] = arr[j] + tempArray[2]
print(max(arr))
It gives me running time-out error for some test cases. I know very little about time complexity but I think it's \$O(NM)\$. What am I doing wrong?
a
andb
are evenly distributed in the range 0..N). To reduce the complexity of your algorithm, you could use a data structure to pre-process all the input rows, and then perform the sums. \$\endgroup\$