Optimising Prefix Sum

Question

I have a question: Starting with a 1-indexed array of zeros and a list of operations, for each operation add a value to each the array element between two given indices, inclusive. Once all operations have been performed, return the maximum value in the array.

Given some queries in the form [a,b,k]:

[[1,5,3],[4,8,7],[6,9,1]]

Add the values of k between the indices a and b inclusive:

[0,0,0, 0, 0,0,0,0,0, 0]
[3,3,3, 3, 3,0,0,0,0, 0]
[3,3,3,10,10,7,7,7,0, 0]
[3,3,3,10,10,8,8,8,1, 0]

And then return the max value which is 10

My attempt is:

from itertools import accumulate

def Operations(size, Array):

    values = [0] * (size+2)
    for a,b,k in Array:
        values[a] += k
        values[b+1] -= k

    values = list(accumulate(values))

    Result = max(values)
    return Result




def main():
    nm = input().split()

    n = int(nm[0])

    m = int(nm[1])

    queries = []

    for _ in range(m):
        queries.append(list(map(int, input().rstrip().split())))

    result = Operations(n, queries)

if __name__ == "__main__":
    main()

This code works, however, hits runtime errors when the arrays get too large. I have no idea how to lower the runtime further.

Example input is as follows:

5 3
1 2 100
2 5 100
3 4 100

Answer 1

The solution looks good, my suggestions:

• Generators: the function itertools.accumulate returns a generator which doesn't create the whole list in memory, but calling list on it does create the actual list in memory. This is probably why you get the runtime error. Changing Operations from:

  def Operations(size, Array):
  
      values = [0] * (size+2)
      for a,b,k in Array:
          values[a] += k
          values[b+1] -= k
  
      values = list(accumulate(values))
  
      Result = max(values)
      return Result
  

  To:

  def Operations(size, Array):
      values = [0] * (size + 2)
      for a, b, k in Array:
          values[a] += k
          values[b + 1] -= k
      return max(accumulate(values))
  

  solves the problem and all tests pass.
• PEP 8: function names should be lowercase, with words separated by underscores as necessary to improve readability. Variable names follow the same convention as function names. More info. The function name is probably given by HackerRank, but the variable names Array and Result should be lowercase.

FYI, this is my old review on the same problem.