HackerRank Data Structure: Array Manipulation Solution in Python3

I came across this interesting problem on HackerRank and I wanted to share my learning from this problem. If you are already familiar with the problem, please go directly to Step 3.

Problem

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

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

Add the values of between the indices and inclusive:

        1 2 3 4  5  6 7 8 9 10  <---index
Start :[0,0,0,0, 0, 0,0,0,0,0]
Step 1:[3,3,3,3, 3, 0,0,0,0,0]
Step 2:[3,3,3,10,10,7,7,7,0,0]
Step 3:[3,3,3,10,10,8,8,8,1,0]

The largest value is 10 after all operations are performed.

Sample Input

n = 3
arr = [[1, 2, 100],[2, 5, 100], [3, 4, 100]]

Sample Output

200

Step 1: Break down problem into simpler terms

• The starting state is a 1-dimensional array of length n. Index starts from 1.
• In the given 2-dimensional array of queries, each query contains 2 indices and a k-value. We will need to add k-value to all the elements between index a and b (inclusive).

Step 2: Create a brute force solution

def arrayManipulation(n, queries):
    arr = [0] * n
    for a, b, k in queries:
        for y in range(a-1,b):
            arr[y] += k
            print(arr)
    return max(arr)
n = 10
queries = [[1, 5, 3], [4, 8, 7], [6, 9, 1]]
arrayManipulation(n, queries)

This solution has a time complexity of O(m*n) where m is the length of the queries array and n is the size of the array between index a and b. This solution was not accepted as it was inefficient and gave a runtime error.

Step 3: Improve on solution

def arrayManipulation(n, queries):
    arr = [0] * n
    for a, b, k in queries:
        arr[a-1] += k
        if b < n:
            arr[b] -= k
    maxSum = 0
    currentSum = 0
    for each in arr:
        currentSum += each
        maxSum = max(maxSum,currentSum)
    return maxSum

You may have seen this solution in the discussion page / online videos — here, here. It took me a while before I finally understood the logic. The main confusion for me was (1) Why do we need to subtract k from the element in index b+1? (2) How does this algorithm account for the overlap in queries?

The above table shows that both methods give us the same output. But why? If we look how the sum output evolves from left to right, the need for subtraction starts to make sense from a cumulative total concept.

• Method 2 Step 1: Given a = 1, b=5, k= 3, we need to add 3 to elements between index 1 and 5. When we reach index 6, we need to subtract 3 from the cumulative total to remove its effect.
• Method 2 Step 2: Given a=4, b = 8, k = 7, we need to add 7 at index 4 to include it in the cumulative total, thus accounting for the overlap in the queries. At index 9, we need to subtract 7 to remove its effect from the total cumulative total.
• The time complexity for this solution is O(m+n).

Thanks for reading! Hope this helps!

If you found this article helpful, I would really appreciate if you could follow my account and give this article a clap! Thank you!! :D