Problem

We have another array operations question. This time we are given two inputs, a number n and a 2d array of operations. Each of the operations has 3 values, a start index, an end index and an increment value.

Source: HackerRank

The task is to implement each of those tasks on to a new array with initial values set to 0 and length n and return the maximum value found in the resulting array.

example

• n = 5
• A = [[1, 2, 100],[2, 5, 100],[3, 4, 100]]

[0, 0, 0, 0, 0]
[100, 100, 0, 0, 0]
[100, 200, 100, 100, 100]
[100, 200, 200, 100, 100] => return 200

My Solution

Brute Force

As per usual I first thought up a brute force approach, this is a simple matter of following the instructions step by step. It gives the correct answers but the run time is not acceptable.

function solution(n, queries) {
    const results = new Map()
    let max = 0
    for (const query of queries) {
        for (let i = query[0]; i <= query[1]; i++) {
            const value = (results.get(i) || 0) + query[2]
            results.set(i, value)
            max = Math.max(max, value)
        }
    }
    return max
}
Code language: JavaScript (javascript)

Solution 2.0

Full disclosure, I didn’t solve this one. I tried a number of different approaches but none of them worked perfectly so I put it on hold for the weekend. Then when I came back to it I still couldn’t wrap my head around it so I swallowed my pride and googled it.

The solution is pretty ingenious really but not very intuitive. The premise is not to add all the values into the array, but only the edges. We are creating a graph of the max value then we use that graph to return our desired value.

The code looks like this:

function solution(n, queries) {
    const results = Array(n + 1).fill(0);
    let maxValue = 0
    for (const query of queries) {
        results[query[0] - 1] += query[2]
        results[query[1]] -= query[2]
    }
    let sum = 0;
    for (const value of results) {
        sum += value
        maxValue = Math.max(maxValue, sum)
    }
    return maxValue
}
Code language: JavaScript (javascript)

This new approach works well and passes all the performance tests. I if you don’t understand how it works let me know and I’ll dive deeper into it. But until then, that’s all I have for today.