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?

  • 1
    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.

  • 5
    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.

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

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.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.