Array Manipulation | Hackerrank runtime error issue

Question

I am doing this Array Manipulation problem from hackerrank and it tells me runtime error. From my perspective, the time complexity is O(n). But it still got this problem. Anyone could help me out?

Below is the link:

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

For example, the length of your array of zeros . Your list of queries is as follows:

a b k
1 5 3
4 8 7
6 9 1

Add the values of between the indices and inclusive:

index -> 1 2 3  4  5 6 7 8 9 10
        [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]

The largest value is after all operations are performed.

I attached my code here:

def arrayManipulation(n,queries):
    increment=[]
    value=[]
    for i in range(n):
        increment+=[0]
        value+=[0]
    for j in range(m):
        left=queries[j][0]
        right=queries[j][1]
        k=queries[j][2]
        increment[left-1]+=k
        if right>=n:
            continue
        else:
            increment[right]-=k
    value[0]=increment[0]
    for i in range(1,n):
        value[i]=value[i-1]+increment[i]
    maximum=max(value)
    return maximum

Answer 1

You can simplify this problem if you just add/subtract at the correct indices - so you only have 2 ops instead of 2000 ops for

1 2000 3 

Your list of queries is as follows:

a b k
1 5 3
4 8 7
6 9 1


# demonstation purposes, do not create list with 200k zero entries - use a dict. see below.
[+3, 0, 0,  0, -3,  0, 0,  0, 0, 0]     # 2 index ops by 1 5 3
[+3, 0, 0, +7, -3,  0, 0, -7, 0, 0]      # 2 index ops by 4 8 7
[+3, 0, 0, +7, -3, +1, 0, -7,-1, 0]     # 2 index ops by 6 9 1

# sums:
  3  3  3  10   7   8  8   1  0  0  # for loop through list, adding all, remembering max

You get the largest value by passing through the whole list once, and simply adding up all numbers + remebering the max value while you pass through.

This simplifies the whole problem for huge lists that break your memory/computation time.

Instead of doing (for a 200k long list)

 1 2000 3  # 2000 times change value
11 2000 3  # 2000 times change value
21 2000 3  # 2000 times change value 
31 2000 3  # 2000 times change value
41 2000 3  # 2000 times change value

you do 10 value changes:

# demonstation purposes, do not create list with 200k zero entries - use a dict. see below.
[ ..., +3, ..., +3, ..., +3, ..., +3, ..., +3, ............, 
       -3, ..., -3, ..., -3, ..., -3, ..., -3, ...] 

{1:3, 11:3, 21:3, 31:3, 41:3, 2001:-3, 2011:-3, 2021:-3, 2031:-3, 2041:-3}

and when sorting by key and adding the values you get:

 3, 6, 9, 12, 15, 18, 15, 13, 12, 9, 6, 3 

You should be able to insert these things into a dict with key == position (make sure to update a key's value instead of replacing it, if it occures multiple times:

3 7 3
3 9 3
3 5 3

{3:9,7:-3, 9:-3, 5:-3} # 3 updated several times 

---

Figuring out these ideas is what makes some hackerranks fun (plenty are just bad/unclear though).

Here is the code, have fun - it is not much of an accomplishment to copy&paste solutions - thats why I did not write the code in the first place...

maxElem, inputs = [int(n) for n in input().split(" ")]
d = {}
for _ in range(inputs):
    x, y, incr = [int(n) for n in input().split(" ")]
    d.setdefault(x,0)
    d[x]=d[x]+incr 
    if(y <= maxElem+2):
        d.setdefault(y+1,0)
        d[y+1]=d[y+1]-incr

maxx = 0
x= 0 

for i in sorted(d): 
    x+=d[i]
    if(maxx<x): 
        maxx=x

print(maxx)