can anyone post the solution of HackerRank Array Manipulation?
https://www.hackerrank.com/challenges/crush/problem
I did my best with:
def listMax(n, operations):
# Write your code here
l = [0 for i in range(n)]
def doOperation(a,b,k):
for i in range(a-1,b):
val = l[i]
val += k
l[i] = val
for op in operations:
a,b,k = op[0],op[1],op[2]
doOperation(a,b,k)
l.sort()
return l [n-1]
...but I was not able to pass the performance tests getting
time out
My solution for it was:
N, M = map(int, raw_input().split())
arr=[0]*(N+2)
for _m in xrange(0, M):
a,b,k = map(int, raw_input().split())
arr[a]+=k
arr[b+1]-=k
for n in xrange(2, N+1):
arr[n]+=arr[n-1]
print max(arr)
I hope it helped!
I have found the solution there
https://jugsi.blogspot.com/2019/11/hacker-rank-array-manipulation-in-python.html
def listMax(n, operations):
# Write your code here
l = [0 for i in range(n+2)]
def _do(a,b,k):
l[a] +=k
l[b+1] -=k
for o in operations:
a,b,k = o[0],o[1],o[2]
_do(a,b,k)
c = 0
x_max = 0
for i in range(1,n+1):
c +=l[i]
c_max = max(c,v_max)
return x_max
how it works? Using the prefix sum algorithm https://en.wikipedia.org/wiki/Prefix_sum
There https://www.youtube.com/watch?v=hDhf04AJIRs the explanation.
Checkout my approach.
def arrayManipulation(n, queries):
mat=[]
r=len(queries)
row1=[0] * n
a=b=k=0
maximum_row=[]
for i in range(r):
a=queries[i][0]
b=queries[i][1]
k=queries[i][2]
row1[a-1:b] = map((k).__add__, row1[a-1:b])
maximum_row.append(max(row1))
return(max(maximum_row))
