Hackerrank array manipulation assistance

user_9044962 0
Viewed 85

This is related to the question "Manipulate Arrays" on hackerrank: https://www.hackerrank.com/challenges/crush/problem

Could you explain why this code subtracts from the 2nd element in the queries array and how is it totalling the numbers at the end. I added print statements to see why this works but I am stuck.

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]
    maxval = 0
    itt = 0
    for q in arr:
        itt += q
        if itt > maxval:
            maxval = itt
    return maxval
python-3.x arrays
1 Answers

Instead of adding the value to each element in the range, the value is added to the first element of the range and subtracted from the element after the last element of the range. This way, when iterating over the array from the beginning and summing all the values, you get the current value of each element. So, an example with n == 5:

0 0 0 0 0

query 1 3 100

100 0 0 -100 0

query 2 4 200

100 200 0 -100 -200

If you now iterate over the array and sum the values while doing so, you will get the values:

100 300 300 200 0

which is the correct state of the array after such queries.

Edit: For queries where the ending index is equal to the length of the array the value is not subtracted from anything because there are no elements after the last one, so there is no point in doing so.

user_81500660
Related