My first thought is that this is much like the skyline problem, so i came up with the solution I, which sorts boundaries of each update, so that we can calculate the total increase at each sub-interval and apply to result array. This should take O(max(length, update)*log(update)).

I then find a much better solution from comments, which only takes O(max(length, update)).

Both solutions are accepted.

Solution I: Accepted, 24ms

```
public int[] getModifiedArray(int length, int[][] updates) {
int[] result = new int[length];
if (length == 0 || updates.length == 0)
return result;
PriorityQueue<int[]> q = new PriorityQueue<>(new Comparator<int[]>(){
@Override
public int compare(int[] a1, int[] a2) {
return a1[0] - a2[0]; // sort by index
}
});
for (int[] update : updates) {
int start = update[0], end = update[1], incr = update[2];
q.add(new int[]{start, incr, 0}); // incr rises from index 'start'
q.add(new int[]{end+1, incr, 1}); // NOTE: incr drops from index AFTER 'end'
}
q.add(new int[]{length, 0, 0}); // padding to the end; because update is triggered
// after encountering a new entry at this index.
int prevIdx = 0, totalIncr = 0;
while (!q.isEmpty()) {
int idx = q.peek()[0];
// trigger applying total incr for previous sub interval
for (int i = prevIdx; i < idx; result[i++] = totalIncr);
// find all bounaries falling at idx; could be more than 1
while (!q.isEmpty() && q.peek()[0] == idx) {
int[] a = q.poll();
if (a[2] == 0) // start of an update range
totalIncr += a[1];
else // end+1 of an update range
totalIncr -= a[1];
}
prevIdx = idx;
}
return result;
}
```

Solution II: Accepted (3ms)

```
public int[] getModifiedArray(int length, int[][] updates) {
int[] result = new int[length];
if (length == 0 || updates.length == 0)
return result;
for (int[] update : updates) {
int start = update[0], end = update[1], incr = update[2];
result[start] += incr;
if (end + 1 < length) // NOTE: end coulbe the last index on array
result[end + 1] -= incr;
}
for (int i = 1; i < length; result[i] += result[i-1], i++);
return result;
}
```