This is my solution to the Algorithmic Crush problem from HackerRank. Can I get any comments regarding where I can improve the code to be more efficient?

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\$ and you have to add value to all the elements ranging from index \$a\$ to \$b\$ (both inclusive).

Input Format

First line will contain two integers \$N\$ and \$M\$ separated by a single space. Next \$M\$ lines will contain three integers \$a, b\$ and \$k\$ separated by a single space. Numbers in list are numbered from \$1\$ to \$N\$.


\$3 \leq N \leq 10^7\$

\$1\leq M \leq 2*10^5\$

\$1 \leq a \leq b \leq N\$

\$ 0 \leq k \leq 10^9\$

Output Format

A single line containing maximum value in the updated list.

Sample Input

5 3
1 2 100
2 5 100
3 4 100

Sample Output

def updateList(seq, listA):
    st, end, value = map(int, seq.split())
    for i in range(st-1, end):
        listA[i] = listA[i]+value
    return listA

n, m = map(int, raw_input().split())

lis = [0 for i in range(n)]

for ins in range(m):
    cmds = raw_input()
    resultSet = updateList(cmds, lis)
    lis = resultSet
print sorted(resultSet)[-1]
  • 7
    \$\begingroup\$ I think the biggest improvement (to the question, not to the code) would be adding a problem statement. \$\endgroup\$
    – CiaPan
    Commented Feb 1, 2017 at 7:03

1 Answer 1


The code is generally clean, however, maintaining the same algorithm will probably result in a timeout for this problem. Your current complexity is \$ O(N\cdot M) \$ which could be up to \$ 10^7 \times 10^5 \$ according to the problem statement.

A similar problem to this is the maximum interval overlap problem, discussed here. The problem is given the guest arrival and departure times in a party, find the interval with the maximum guests. It should be a good exercise to apply the same idea to this problem.

  • 1
    \$\begingroup\$ It's basically a 1D collision detection. The article you link uses sweep and prune to solve it. It is a very good read but if one needs further reading: There are a lot of articles on sweep and prune on the web. \$\endgroup\$
    – Christoph
    Commented Feb 1, 2017 at 9:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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