Array Manipulation 2

Array Manipulation 2 - A HackerRank challenge solution


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…


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.


    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:

Row / Index12345

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.

Row / Index12345

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.


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


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

Si te gusta el contenido, por favor apoya mi trabajo!

Juan Cruz Martinez - Author @ Live Code Stream

Juan Cruz Martinez


Soy Juan Cruz Martinez, el fundador de Me encanta programar y creo en el poder de la programación no solo para construir un mundo mejor, sino para hacer que TU vida sea mejor.

Fundé porque quería ayudarte a aprender a programar, construir una mejor carrera y, en última instancia, crear una vida mejor. Eso me sucedió hace más de una década cuando comencé a programar, y le sucede a decenas de miles de personas a diario. Quiero que TÚ te unas a esa revolución.

No importa cómo lo llames, escribir código, programación, desarrollo de software o cualquier otra cosa, las habilidades involucradas están en una demanda cada vez mayor. Y ya sea que quieras incursionar en el desarrollo de sitios web, diseño de juegos, desarrollo de blockchain o cualquier otra cosa, quiero ayudarte.