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.
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.
- 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
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.
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:
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.