# “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?

• The complexity is O(N*M). You do two loops, the outer loop executed M times, the inner loop executed on the average (N/2) times (if the values a and b 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. – Renzo Jul 4 '15 at 9:45
• You need to use a segment tree to solve this problem. – Rishav Jul 4 '15 at 9:56

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.

• A naive question, but I don't understand the logic of doing 'arr_a += k and arr_b+1 −=k' operation. Can you please explain this. – iankits May 5 '16 at 19:28
• @iankits this link helped me : wcipeg.com/wiki/Prefix_sum_array_and_difference_array – gaurav5430 Sep 6 '17 at 17:08
• you mentioned suffix trees, how can they be used to solve this particular problem ? – gaurav5430 Sep 6 '17 at 17:55

A few general coding style suggestions:

• Rather than assigning M and N on separate lines, you can use tuple unpacking:

N, M = tempArray

• I'd use different variable names for the first input line, and all subsequent lines. For example:

init_line = [int(n) for n in input().split()]  # split() defaults to whitespace
size_of_list, number_of_operations = init_line

for i in range(number_of_operations):
this_line = [int(n) for n in input().split()]
# Do some stuff


I’ve also changed the other variable names: M and N have been replaced by more descriptive names, and the Python convention is to use snake_case, not dromedaryCase.

Or even better, you could just drop those variables entirely:

size_of_list, number_of_operations = [int(n) for n in input().split()]

for i in range(number_of_operations):
a, b, k = [int(n) for n in input().split(" ")]


Note the tuple unpacking for a, b and k: this makes it easier to follow the logic if we have these named variables.

• In the look over M/number_of_operations, since the value of i is unused, a common convention is to use an underscore instead:

for _ in range(number_of_operations):


The time complexity is actually $O(MN)$, because there’s an outer loop of length M, and inner loop of length N, and a single addition for every step.

I can’t see a good way to improve the time complexity. Some people have suggested other data structures in the comments, but I don’t know enough CS to suggest one myself.

Allow me to cite my answer from the Hackerrank discussion.

Explanation:

A straight forward implementation would start with an array $s[i] = 0$ for $i \in \{ 1, \dotsc, n \}$ and perform $m$ modifications, where the elements $s[j]$ for $j \in \{ a_j, \dotsc, b_j \}$ are getting the value $k_j$ added.

This would need $$\sum_{j=1}^m \lvert \{ a_j, \dotsc, b_j \} \rvert \approx m \frac{n}{2}$$ operations, so it is $O(m n)$. The constraints require to handle up to $m=2\cdot 10^{5}$ and $n=10^7$ resulting in about $10^{12}$ operations, which is outside the given resources.

The above solution manages to requires $m$ setup steps and a final integration step visiting not more than $n$ array elements, so it is $O(\max\{m, n\})$. For the constraints not more than about $2\cdot 10^7$ steps are needed, which is possible to compute with the given resources.

In Detail:

We start with a constant function $s_0(t) = 0$ and then add the $m$ modifications, going through a sequence of modified functions $s_i(t)$.
Given $s_i(t)$ and adding the value $k$ for all times $t \in [a, b]$, this results into the modified function \begin{align} s_{i+1}(t) &= s_i(t) + k \, \chi_{[a, b]}(t) \\ &= s_i(t) + k \, \text{Rect}_{[a, b]}(t) \\ &= s_i(t) + k \, \Theta(t-a) - k \, \Theta(t-b) \end{align} where $\chi_I$ is the characteristic function of set $I$ and $\Theta(t)$ is the Heaviside distribution $$\Theta(t) = \begin{cases} 0 & t < 0 \\ 1 & t > 0 \end{cases}$$ The derivative is $$\dot{s}_{i+1}(t) = \dot{s}_i(t) + k \delta(t-a) - k \delta(t-b)$$ where $\delta$ is the Dirac distribution.
For the discrete case this seems to turn into $$\Delta s_{i+1}[t] = \Delta s_i[t] + k \delta[t-a] - k \delta[t-b+1]$$ with $$\delta [n] = \begin{cases} 1 & n = 0 \\ 0 & n \ne 0 \end{cases}$$
So the modeling of the derivative $\Delta s[t]$ is very efficient, only recording the changes at the interval borders.
After $m$ modifications of the constant null function we get: $$\Delta s[t] = \sum_{j=1}^m k_j \delta[t-a_j] - k_j \delta[t-b_j+1]$$
Finally $s$ is reconstructed by summing up (integrating) $\Delta s$ over $t$: $$s[t] = \sum_{\tau=1}^t \Delta s[\tau]$$ where we used $t_\min = 1$ as smallest value.