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\$.

Constraints

\$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

200
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
    I think the biggest improvement (to the question, not to the code) would be adding a problem statement. – CiaPan Feb 1 '17 at 7:03
up vote 5 down vote accepted

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
    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. – Christoph Feb 1 '17 at 9:31

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.