"Algorithmic Crush" problem hitting timeout errors

This is the HackerRank problem Algorithmic Crush:


You are given a list of size N, initialized with zeroes. You have to perform M operations on the list and output the maximum of final values of all the N elements in the list. For every operation, you are given three integers a, b and k. The value k needs to be added to all the elements ranging from index a through b (both inclusive).

Input Format


The first line will contain two integers N and M separated by a single space.

The next M lines will each contain three integers a, b and k separated spaces.

The numbers in the list are numbered from 1 to N.

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 be 100 200 100 100 100.

After the third update, the list will be 100 200 200 200 100.

So, the required answer will be 200.

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?

Constraints


\$3 ≤ N ≤ 10^7\$

\$1 ≤ M ≤ 2 \cdot 10^5\$

\$1 ≤ a ≤ b ≤ N\$

\$0 ≤ k ≤ 10^9\$

You should verify that every value you read from the user is a valid value in your program.

As far as complexity goes, a suffix tree with a complexity of \$O(N\log{}N)\$ compared to your current \$O(MN)\$ solution that adds difference to every value in the range \$[A,B]\$. With \$N \sim 10^7\$, an \$O(N\log{}N)\$ solution may still be too slow.

For this problem, I would employ a max prefix sum scan on a difference array. To generate a set of range differences, we adjust \$arr_{a} \mathrel{{+}{=}} k\$ and \$arr_{b+1} \mathrel{{-}{=}} k\$. Going back to your sample data, your difference array would look like this:

#   1.......................N...N+1
5 3      #   0     0     0     0     0     0
1 2 100  # 100     0  -100     0     0     0       
2 5 100  # 100   100  -100     0     0  -100
3 4 100  # 100   100     0     0  -100  -100

To calculate the max prefix sum, accumulate the difference array to \$N\$ while taking the maximum accumulated prefix. (*) denotes new max found.

DiffArray  100  100    0    0  -100  -100
PrefixSum  100*
Max = 100

DiffArray  100  100    0    0  -100  -100
PrefixSum       200*
Max = 200

DiffArray  100  100    0    0  -100  -100
PrefixSum            200
Max = 200

DiffArray  100  100    0    0  -100  -100
PrefixSum                 200
Max = 200

DiffArray  100  100    0    0  -100  -100
PrefixSum                       100
Max = 200

Building a difference array in \$O(M)\$ and finding the max prefix sum in \$O(N)\$ results in a \$O(M+N)\$ linear algorithm.

StackExchange Code Review Q#95755, answer score: 16