Think of an array of 64-bit integers initialized to zero. It could be quite large, up to ten million elements. We change it applying up to 20 thousand times a series of simple operation: add to all its elements in a specified range an increase that could be in the order of billions. At the end, we want to know the max value in the array.
Please, try it on HackerRank before checking the Java solution here below. It is tagged as hard but, as you get its point, it is not actually so complicated.
The naive solution of applying the required operations just as stated in the problem description would obviously work, but a too high cost. It would be too slow, and a few test cases are bound to fail on a timeout.
We have to be smarter than that, we should avoid modifying all those elements in the array all over again. If you know what a partial sum is, you have already seen the (green) light to this problem.
We could keep track of just the increase and the interval! When asked to add 10 to all the elements between, say, 1_000 and 2_001_000, we could just add 10 to the element 1_000, and then subtract 10 to the element 2_001_001. The elements in the array won't store the actual value but the variation from the previous one.
We just need to do a final single pass on every element to apply the partial sum algorithm to convert our array of variations in an actual array of values, as expected by the user. And then check what is the max in it.
Once the approach is clear, the code is pretty simple.
long[] data = new long[n + 1]; // 1
for(int[] query: queries) { // 2
data[query[0]-1] += query[2]; // 3
data[query[1]] -= query[2]; // 4
}
for(int i = 1; i < data.length; i++) { // 5
data[i] += data[i-1];
}
return LongStream.of(data).max().orElseThrow(); // 6
- The caller specify the size of the array as n, it simplify the partial sum algorithm having one element more at the right
- Looping on all the queries passed in. First two components are the one-based indeces of the subinterval on which we should apply the change. The third value is the increase
- Being one-based, remember to decrease the index
- Remember also that we should decrease the first element outside the interval on the right
- Unfortunately, I don't know any standard Java functionality to generate the partial sum of an array, like C++ partial_sum() or Python accumulate(). So I did it "by hand"
- It is not strictly a necessity using streams here. In any case I guess it is clear what the code means. By the way, orElseThrow() is Java 10, if you want to run this code on Java 8 (as HackerRank asks) you'd better fallback to getAsLong()
Full Java code and relative test case pushed to GitHub.
