Array Manipulation Hackerrank using python [closed]

This logic is working for most of the test cases but not all. What I am doing wrong?

def arrayManipulation(n, queries, m):
    li = []
    for j in range(0, m):
        p = queries[j][0]
        r = queries[j][1]
        v = queries[j][2]

        lo = []
        for i in range(0, n):
            lo.append(0)

        for i in range(p - 1, r):
            lo[i] = lo[i] + v

        li.append(lo)

    for i in range(1, m):
        for j in range(0, n):
            li[i][j] = li[i-1][j] + li[i][j]
    return max(max(li))

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')
    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 = arrayManipulation(n, queries,m)
    print(result)
    fptr.write(str(result) + 'n')
    fptr.close()

Answer

None of the python samples pass m to arrayManipulation as it is not necessary – in python you can just iterate over the list rather than an index of the list:

You are making this way more complicated than it needs to be, you don’t need to keep the previous lists just update the one list, e.g.:

def arrayManipulation(n, queries):
    arr = [0]*n
    for a, b, k in queries:
        for i in range(a-1, b):
            arr[i] += k
    return max(arr)

This is still a brute force approach and unlikely to solve challenges from sites like hankerrank that want you to solve these problems more analytically.

So considering this more analytically, you can just consider the endpoints of each query and just have a counter that increments at the start and decrements at the end. Now the challenge just becomes sorting all these starts and ends. So this uses itertools.chain.from_iterable() to flatten all the (a, k), (b, -k) values and itertools.accumulate() over the sorted list to providing a running total. Return the max() of this, e.g.:

import itertools as it

def arrayManipulation(n, queries):
    q = it.chain.from_iterable([(a, k), (b, -k)] for a, b, k in queries)
    return max(it.accumulate(c for _, c in sorted(q, key=lambda x: (x[0], -x[1]))))

Note: you need to sort based on negative k or you will subtract before adding at the same endpoint value, which gives the wrong answer, this can be done using the key param to sorted(). Alternatively, you can invert the ks in q and then accumulate(-c ...) removing the need for the key param:

def arrayManipulation(n, queries):
    q = it.chain.from_iterable([(a, -k), (b, k)] for a, b, k in queries)
    return max(it.accumulate(-c for _, c in sorted(q)))

A quick comparison of the 2 approaches using a random 5000 queries over an array of 100000 entries (below the limits of the test, but at the limits of the brute force approach for comparison):

Brute force: 19.6 s ± 1.04 s per loop (mean ± std. dev. of 7 runs, 1 loop each)
Efficient  : 12.4 ms ± 3.25 ms per loop (mean ± std. dev. of 7 runs, 100 loops each)

At the limits of the test: 2*10**5 queries over 10**7 array length:

Efficient  : 891 ms ± 34 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)