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.
[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.
Today I am working on a summation problem made to look like building a tower out of cubic bricks. It’s fun to brute force sometimes.
Coming back to Rust code after a bit of a hiatus with a simple problem… The Two-sum problem. Finding numbers in an array. Yay, fun.
King Pinn: I Salute You. I’m driving halfway across the country and this song is on repeat. Rest in Peace Tonderai Makoni. You were awesome.
After a few weeks off I’m back to business. This is just an update post detailing plans for the rest of the year.
At last we finally have the great reveal, our mystery project was implementing RSA encryption in rust.