"Algorithmic Crush" problem hitting timeout errors

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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:

Let us start with the continuous case:

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.

Answer 4

Trying to explain @Snowhawk's answer in even simpler terms, The solution can be handled using prefix sum. Prefix sum calculates the summ of all integers before it and store the result in same or different array.

For the query a b k (a = left edge, b = right edge, k = no. to add)

Here, we'll add the 3rd no of query, k to the left boundary, a. Therefore when we calculate the prefix sum, all nos to its right will have k added to them.

However, k should be added only till the right edge, b, meaning the b+1th element onwards, it should not be be added. To make this happen, when we add k to the left edge, we'll also subtract it from the right edge + 1. Therefore, all no.s to the right will not have k when the prefix sum was calculated as the net effect will be +k (from the left edge) + -k (from the element next to the right edge).

For a 10 elemnt array with following query:
1 5 3
4 8 7
6 9 1

      | 1| 2| 3| 4| 5| 6| 7| 8| 9|10|
      -------------------------------
query | 0| 0| 0| 0| 0| 0| 0| 0| 0| 0|    // Initial Array
      -------------------------------
1 5 3 | 3| 0| 0| 0| 0|-3| 0| 0| 0| 0|    // Added 3 to 1 and -3 to 6 to neutrilize the net effect 6th element onwards when prefix sum is calculated
      -------------------------------
4 8 7 | 3| 0| 0| 7| 0|-3| 0| 0|-7| 0|
      -------------------------------
6 9 1 | 3| 0| 0| 7| 0|-2| 0| 0|-7|-1|   // Value of the 6th index was -3, added 1 to get -2 there
      -------------------------------
res:  | 3| 3| 3|10|10| 8| 8| 8| 1| 0|   // This is the prefix sum, 3+7 = 10, 10-2 = 8 and so on

Answer 5

Constraints-

3≤𝑁≤10^7

1≤𝑀≤2⋅10^5

1≤𝑎≤𝑏≤𝑁

0≤𝑘≤10^9

Why your brute force solution will not work?

Today generation system can perform 10^8 operation in one second. keep this in mind you have to process N=10^7 input per query in worse case. so if you use your solution with O(NM) complexity it has to handle (10^7 *10 ^5)= 10^12 operation in worse case (which can not be computed in 1 sec at all)

That is the reason you will get the time out error for your brute force solution. So you need to optimise your code which can be done with the help of prefix sum array.

instead of adding k to all the elements within a range from a to b in an array, accumulate the difference array

Whenever we add anything at any index into an array and apply prefix sum algorithm the same element will be added to every element till the end of the array.

ex- n=5, m=1, a=2 b=5 k=5

    i     0.....1.....2.....3.....4.....5.....6   //take array of size N+2 to avoid index out of bound
  A[i]    0     0     0     0     0     0     0

Add k=5 to at a=2

A[a]=A[a]+k // start index from where k element should be added

     i    0.....1.....2.....3.....4.....5.....6 
   A[i]   0     0     5     0     0     0     0

now apply prefix sum algorithm

     i    0.....1.....2.....3.....4.....5.....6 
  A[i]    0     0     5     5     5     5     5

so you can see K=5 add to all the element till the end after applying prefix sum but we don't have to add k till the end. so to negate this effect we have to add -K also after b+1 index so that only from [a,b] range only will have K element addition effect.

A[b+1]=A[b]-k // to remove the effect of previously added k element after bth index. that's why adding -k in the initial array along with +k.

    i    0.....1.....2.....3.....4.....5.....6 
  A[i]   0     0     5     0     0     0    -5

Now apply prefix sum Array

    i    0.....1.....2.....3.....4.....5.....6 
  A[i]   0     0     5     5     5     5     0

You can see now K=5 got added from a=2 to b=5 which was expected. Here we are only updating two indices for every query so complexity will be O(1).

Now apply the same algorithm in the input

         # 0.....1.....2.....3.....4.....5.....6    //taken array of size N+2 to avoid index out of bound
5 3      # 0     0     0     0     0     0     0
1 2 100  # 0    100    0   -100    0     0     0       
2 5 100  # 0    100   100  -100    0     0   -100
3 4 100  # 0    100   100    0     0  -100   -100

To calculate the max prefix sum, accumulate the difference array to 𝑁 while taking the maximum accumulated prefix.

After performing all the operation now apply prefix sum Array

    i      0.....1.....2.....3.....4.....5.....6 
  A[i]     0     100   200  200   200   100    0

Now you can traverse this array to find max which is 200. traversing the array will take O(N) time and updating the two indices for each query will take O(1)* number of queries(m)

overall complexity=O(N)+O(M) = O(N+M)

it means = (10^7+10^5) which is less than 10^8 (per second)

Note: If searching for video tutorial , you must check it out here for detailed explanation.