Array Manipulation Hackerrank using python [closed]

Question

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 1

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)

Answer 2

def arrayManipulation(arr):
    check = []
    for i in range(len(arr)):
        check.append(arr[i][1])
    big_jug = max(check) + 1

    temps = []
    for i in range(len(arr)):
        temps = [[0] * big_jug for _ in range(len(arr))]

    for i in range(len(temps)):
        for j in range(arr[i][0], arr[i][1] + 1):     
            temps[i][j] = arr[i][2]
   
sums = list(map(sum, zip(*temps)))
print(max(sums))

first, check for all lower end (i.e:every array, second value of array) to get biggest value of them to create a nested array in which all values are zero. Then replace all zero values with upper and lower end descrided in all queries(main given array) the and put array third value The sum all nested list At last find highest value of the final list

Answer 3

use this approch due to

for this loop we usesess the variable insted of list it is Due to list take more space than the variable .Therefore try to use variable

def arrayManipulation(n, queries):
arr = [0]*n
for i in queries:
    arr[i[0] - 1] += i[2]
    if i[1] != len(arr):
        arr[i[1]] -= i[2]
k = 0
p = 0
print(arr)
for q in arr:
    p += q
    if p > k:
        k = p
return k

Answer 4

You're using too many for loops and it can be quickly reduced to only two.

The used approach can be:

1. Define both maximum_int_value = 0 and current_int_value = 0. This first will serve to store the the integer maximum value in the finished array and the current_int_value to store the current maximum.

2. The initial part of the first for can be substituted by something like li = [0] * n + 1.

3. Use only two loops - one for calculating the first and last steps in the array and another to get the maximum int value.

4. Calculate sum for each step or fall in the array.

5. If the value of maximum_int_value is lower than current_int_value, then maximum_int_value will be current_int_value.

All in all

#!/bin/python3

import math
import os
import random
import re
import sys

# Complete the arrayManipulation function below.
def arrayManipulation(n, queries):
    maximum_int_value = 0
    current_int_value  = 0
    li = [0] * n

    for query in queries:
        li[query[0] - 1] += query[2]
        # edge case taken from here - https://sites.northwestern.edu/acids/2018/11/12/solution-hackerrank-array-manipulation/
        if query[1] != len(li):
            li[query[1]] -= query[2]

    for i in range(len(li)):
        current_int_value  += li[i]
        if maximum_int_value < current_int_value :
            maximum_int_value = current_int_value 

    return maximum_int_value

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)

    fptr.write(str(result) + '\n')

    fptr.close()

which will pass all the current 16 Test cases in HackerRank