Java O(K + N)time complexity Solution

• Just store every start index for each value and at end index plus one minus it

for example it will look like:

[1 , 3 , 2] , [2, 3, 3] (length = 5)

res[ 0, 2, ,0, 0 -2 ]

res[ 0 ,2, 3, 0, -5]

sum 0, 2, 5, 5, 0

res[0, 2, 5, 5, 0]

`````` public int[] getModifiedArray(int length, int[][] updates) {

int[] res = new int[length];
for(int[] update : updates) {
int value = update[2];
int start = update[0];
int end = update[1];

res[start] += value;

if(end < length - 1)
res[end + 1] -= value;

}

int sum = 0;
for(int i = 0; i < length; i++) {
sum += res[i];
res[i] = sum;
}

return res;
}``````

• great idea!!!!!!!

• thank you !!!!!!!!!

• great answer! a little optimized:

``````public int[] getModifiedArray(int length, int[][] updates) {
if (length < 0 || updates == null || updates.length == 0) return null;
if (updates[0] == null || updates[0].length != 3) return null;

int[] modified = new int[length];
for (int[] upd : updates) {
modified[upd[0]] += upd[2];
if (upd[1] < length -1)
modified[upd[1] + 1] -= upd[2];
}

int sum = 0;
for (int i = 0; i < length; i++) {
sum += modified[i];
modified[i] = sum;
}

return modified;
}``````

• GREATE !!!!!!

• great idea!!

• Just explain res->sum:

res[0,2,3,0,-5]:

sum[0] = res[0] = 0;

sum[1] = res[0] + res[1] = 0 + 2 = 2;

sum[2] = res[0] + res[1] + res[2] = 0 + 2 + 3 = 5;

sum[3] = res[0] + res[1] + res[2] + res[3] = 0 + 2 + 3 + 0 = 5;

sum[4] = res[0] + res[1] + res[2] + res[3] + res[4] = 0 + 2 + 3 + 0 + (-5) = 0;

sum[0,2,5,5,0]

• nice explanation!@

• nice tags!!!!!

• a little bit optimization.

for(int i = 1; i < length; i++) {
res[i] += res[i - 1];
}

• Great solution. Though the code looks simple enough, it took me some time to figure out why exactly we do what we do here. We update the `value` at `start index`, because it will be used in the future when we are adding up the values for the sum at each index between `start index` and `end index` (both inclusive). We update the `negative value` at the `end index + 1`, because the `positive value` of it should be only added at its previous indices (from start index to end index). Thus, when we accumulate the sum at the end for each index, we will get the correct values for each index. If the `end index` is the last index in the resulting array, we don't have to do the `end index + 1` part, because there is no more index after the last index and there will be no error when we accumulate the sum. Hope I explain it well enough to help others understand!

Thanks.

• great idea

• @larrywang2014 nice optimization

• @dianhua1560 your explanation is amazing. I wish all those who post solutions could explain it as well as you did :)

• @acheiver thanks! :)

• "Just store every start index for each value and at end index plus one minus it"
your written english is reckless
Excellent idea, terrible explanation ...

• Discrete-Time Signal Processing

• First pass: taking the `differentiation` of the `updates`
=> finding out the `value change`(pulse) over `indiex positions`(time series)
• Second pass: taking the `integral` of the `value changes`
=> finding out the `accumulation` of the `value changes`(pulses) over `index positions`(time series)

https://en.wikipedia.org/wiki/Discrete-time_signal
special thanks to @alfred-huang-319 and @shogunsea

For this part

``````int sum = 0;
for(int i = 0; i < length; i++) {
sum += res[i];
res[i] = sum;
}
``````

It could be done in this way as well:

``````for(int i = 0; i < length-1; i++) {
result[i+1] = result[i+1] + result[i];
}
``````

• @dianhua1560 Thanks for explaining in detail. but why do we take this approach?

• So concise, thank you!!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.