Array Manipulation 2

Problem

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

For example, the length of your array of zeros n = 10. Your list of queries is as follows:

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

Add the values of k between the indices a and b inclusive:

index->	 1 2 3  4  5 6 7 8 9 10
	[0,0,0, 0, 0,0,0,0,0, 0]
	[3,3,3, 3, 3,0,0,0,0, 0]
	[3,3,3,10,10,7,7,7,0, 0]
	[3,3,3,10,10,8,8,8,1, 0]

The largest value is 10 after all operations are performed.

Function Description

Complete the function arrayManipulation in the editor below. It must return an integer, the maximum value in the resulting array.

arrayManipulation has the following parameters:

• n - the number of elements in your array
• queries - a two dimensional array of queries where each queries[i] contains three integers, a, b, and k.

Read more on the challenge page…

Analysis

This challenge is a typical example of an interview related problem. It is usually the case that we encounter this type of array exercise during a live interview.

The pattern in these exercises is that there is an obvious but less performant solution, which in these case is to perform each calculation, row by row, and storing the results in an array of size n.

Even if the time complexity of that solution is quite good, it’s using unnecessary amounts of memory to solve the challenge, and the interviewer will ask us to optimize it.

In the same way when we try to solve the challenge in Hacker Rank, we will see that some scenarios will fail due to this reason.

What’s very interesting about this problem, is that is giving us indices ranges that we can work with to optimize our algorithm.

Let’s manually work out an example to see what options we have and to better understand the solution I’m proposing bellow.

Example

    a b k
    1 2 3
    4 5 7
    2 2 1

If we manually now plot the steps of our initial algorithm we would get something like:

In this particular case we can now deduce that 7 is the maxium number. Let’s now take a different approach, one that is typical for these range problems.

Let’s again build a table, but this time, we will only focus on the extremes of the indices, highlighting the variations from left to right. So that everytime we enter a range we add k to the element, and then, we substract k when we exit the range.

The advantage is that now we only need to store partial data on our map, we only store 2 points for each range instead of every single one of them. And processing the maximum value is as easy as accumulating all the values from left to right of the accumulator structure.

My Solution

I’m providing the solution for Python and JS, please leave on the comments if you found a better way.

Python

def arrayManipulation(n, queries):
    acc = {}
    for [a, b, k] in queries:
        acc[a] = (acc[a] if a in acc else 0) + k
        acc[b+1] = (acc[b+1] if b+1 in acc else 0) - k

    last = 0
    m = 0
    for i in range(1,n+1):
        curr = acc[i] if i in acc else 0
        last = last + curr
        if (last > m):
            m = last

    return m

Javascript

function arrayManipulation(n, queries) {
    const acc = {};
    for (const [a, b, k] of queries) {
        acc[a] =  (acc[a] || 0) + k;
        acc[b+1] = (acc[b+1] || 0) - k;
    }   

    let last = 0
    let m = 0
    for (let i=0; i<n+1; i++) {
        const curr = acc[i] || 0;
        last = last + curr;
        if (last > m) {
            m = last;
        }
    }

    return m
}

Juan Cruz Martinez

Juan has made it his mission to help aspiring developers unlock their full potential. With over two decades of hands-on programming experience, he understands the challenges and rewards of learning to code. By providing accessible and engaging educational content, Juan has cultivated a community of learners who share their passion for coding. Leveraging his expertise and empathetic teaching approach, Juan has successfully guided countless students on their journey to becoming skilled developers, transforming lives through the power of technology.