We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

I still havent understood this logic.Even though i implemented this logic in java with ease,i dont understand how this logic helps us arrive at the solution.

After thinking like that i also understood the logic the solution.

Let's think our summing part input like that
{A B S} =
{1 3 100}
{2 5 150}
{3 4 110}
{2 4 160}

Instead of writing all elements of array we can write maximum value at just starting and ending indexes to have less writing operation. So, after first input row, array can be something like that.

0 100 0 100 0 0 0 0 0

But the problem is here that even we didn't write anything, value of index 2 is also 100. When we wanted to continue with second step we have to check whether index 2 is between indexes of first row operation or not.

Instead of doing like that we can write S value to index A and -S value to B+1, so it is still similar logic. Starting from A to B all indexes have S value and rest of them have less than these indexes as S as. Now the array is like that:

0 100 0 0 -100 0 0 0 0

While calculating second row, we are writing 150 to index 2 and -150 to index 6. It will be like that: 0 100 150 0 -100 0 -150 0 0

If we write array with old method, which means that all numbers calculated one, it will be:
0 100 250 250 150 150 0 0 0

It shows that value of index 2 is : 100+150 = 250. Value of index 5: 100 + 150 + (-100) = 150. So by calculating with the solution written above, instead of writing all numbers, we are writing changes at edge indexes.

vararr=[];varmax=0;// init each element of arr to 0for(letl=0;l<n;l++){arr[l]=0;}// for each sum operation in queriesfor(leti=0;i<queries.length;i++){// update arr with number to add at index=queries[i][0] and number to remove at index=queries[i][0]+1 => this will allow us to build each element of the final array by summing all elements before it. The aim of this trick is to lower time complexityarr[queries[i][0]-1]+=queries[i][2];if(queries[i][1]<arr.length){arr[queries[i][1]]-=queries[i][2];}}for(letj=1;j<n;j++){arr[j]+=arr[j-1];}for(letk=0;k<arr.length;k++){max=Math.max(max,arr[k]);}//max = Math.max(...arr); // not working for big arraysreturnmax;

Hey,
I did the code in Java8 and my code is getting failed for input type - where only single value is present in a row of array. meaning only left index value is provided and right and k value is missing from array.
So can you help me how to solve this issue?

can you expalin this:
But the problem is here that even we didn't write anything, value of index 2 is also 100. When we wanted to continue with second step we have to check whether index 2 is between indexes of first row operation or not.

but if you dont mind can you please leave the same comment along with like, dislike on my video. it motivates me and help others too find the solution over internet.

Most of the peope solved this problem but time complexity of solution is O(n*m) (due to two nested for loops)which can not be used to solve this problem for given time constraint, so you need better approach which beats O(n*m)

I have created a video tutorial for you and uploaded the same on youtube with complete explanation along with code complexity analysis.

Here is the video tutorial for my solution O(n+m) complexity passed all test cases.

We are creating a "difference array" Which shows how many steps up or down have occurred (the difference between 0 and result of each operation) and where in the array they have occurred. This way, you can see how high the max ends up and return that for the solution.

I'm still trying to figure it out myself. But if you graph result after doing the operations, you would see some rise and fall in the graph.

It looks like his solution tracks the differences between each data point. It went up by x, down by y, remained the same...etc. And his solutions finds the highest increase.

Example:
5 3
1 2 100
2 5 100
3 4 100

After doing the operations you get [100, 200, 200, 200, 100]
His solutions final array is [0, 100, 100, 0, 0, -100]
Meaning starting at 0 the graph went up by 100, went up by 100 again, remained the same, then went back down by 100.

## Array Manipulation

You are viewing a single comment's thread. Return to all comments →

It is the same logic as mentioned above.

Hi i dont understand how the difference array works. What is the logic behind adding at one index and subtracting at the other and taking its sum?

You can try to visualize the array as steps / stairs

We are just noting down the bump ups and bump downs

I still havent understood this logic.Even though i implemented this logic in java with ease,i dont understand how this logic helps us arrive at the solution.

me netheir, I am looking for the maths here, I am pretty sure the solution has a math method. Somebody here wrote "Prefix sum".

I tried an answer in the spirit of digital signal processing here.

After thinking like that i also understood the logic the solution.

Let's think our summing part input like that {A B S} = {1 3 100} {2 5 150} {3 4 110} {2 4 160}

Instead of writing all elements of array we can write maximum value at just starting and ending indexes to have less writing operation. So, after first input row, array can be something like that.

0 100 0 100 0 0 0 0 0

But the problem is here that even we didn't write anything, value of index 2 is also 100. When we wanted to continue with second step we have to check whether index 2 is between indexes of first row operation or not.

Instead of doing like that we can write S value to index A and -S value to B+1, so it is still similar logic. Starting from A to B all indexes have S value and rest of them have less than these indexes as S as. Now the array is like that:

0 100 0 0 -100 0 0 0 0

While calculating second row, we are writing 150 to index 2 and -150 to index 6. It will be like that: 0 100 150 0 -100 0 -150 0 0

If we write array with old method, which means that all numbers calculated one, it will be: 0 100 250 250 150 150 0 0 0

It shows that value of index 2 is : 100+150 = 250. Value of index 5: 100 + 150 + (-100) = 150. So by calculating with the solution written above, instead of writing all numbers, we are writing changes at edge indexes.

check it out here, you will get all your doubts solved https://www.geeksforgeeks.org/difference-array-range-update-query-o1/

Below link will also help to understand theory behind it. https://www.geeksforgeeks.org/constant-time-range-add-operation-array/

Same solution in Javascript

Hey, I did the code in Java8 and my code is getting failed for input type - where only single value is present in a row of array. meaning only left index value is provided and right and k value is missing from array. So can you help me how to solve this issue?

you could post your code,and we can check it out

simpler in es6:

`function arrayManipulation(n, queries) { let arr = new Array(2*n).fill(0); let max = 0;`

`}`

I did something pretty similar, just with a little bit more readable forEach:

This produces wrong answer in some of the tests.

Hi,

try this. Here is the video tutorial for my solution O(n+m) complexity.

https://www.youtube.com/watch?v=hDhf04AJIRs&list=PLSIpQf0NbcCltzNFrOJkQ4J4AAjW3TSmA

Would really appreciate your feedback like and comment etc. on my video.

Your last for loop isn't needed. You can move Math.max to the previous for loop.

Added some ES6 syntax suger...

Got stuck because of this

Thanks man!

Thank you @Kemal_caymaz for the explanation, I have found this very useful.

Thank you!

thnx

super awesome X 1000!!!

can you expalin this:

But the problem is here that even we didn't write anything, value of index 2 is also 100. When we wanted to continue with second step we have to check whether index 2 is between indexes of first row operation or not.Hi,

I have created a video tutorial for you and uploaded the same on youtube. Here is the video tutorial for my solution O(n+m) complexity.

https://youtu.be/hDhf04AJIRs

Would really appreciate your feedback like, dislike , comment etc. on my video.

fantastic video, thank you!

most welcome.

but if you dont mind can you please leave the same comment along with like, dislike on my video. it motivates me and help others too find the solution over internet.

impressive ...

thanks bro..

Hi,

Most of the peope solved this problem but time complexity of solution is O(n*m) (due to two nested for loops)which can not be used to solve this problem for given time constraint, so you need better approach which beats O(n*m)

I have created a video tutorial for you and uploaded the same on youtube with complete explanation along with code complexity analysis.

Here is the video tutorial for my solution O(n+m) complexity passed all test cases.

https://youtu.be/hDhf04AJIRs

Would really appreciate your feedback like, dislike , comment etc. on my video.

To explain further for people confused:

We are creating a "difference array" Which shows how many steps up or down have occurred (the difference between 0 and result of each operation) and where in the array they have occurred. This way, you can see how high the max ends up and return that for the solution.

I found this explanation helpful to have this fact dawn on me after much noodling: https://www.geeksforgeeks.org/difference-array-range-update-query-o1/

Like piling up blocks? Adding a number -> going up one step and subtracting -> down . Finally, we count how high we can go.

I'm still trying to figure it out myself. But if you graph result after doing the operations, you would see some rise and fall in the graph.

It looks like his solution tracks the differences between each data point. It went up by x, down by y, remained the same...etc. And his solutions finds the highest increase.

Example: 5 3

1 2 100

2 5 100

3 4 100

After doing the operations you get [100, 200, 200, 200, 100] His solutions final array is [0, 100, 100, 0, 0, -100] Meaning starting at 0 the graph went up by 100, went up by 100 again, remained the same, then went back down by 100.

So the highest point is 200, the solution.

you add up all the numbers > 0 in the final list, which is 100 + 100 = 200

Hi,

I have created a video tutorial for you and uploaded the same on youtube. Here is the video tutorial for my solution O(n+m) complexity.

https://youtu.be/hDhf04AJIRs

Would really appreciate your feedback like, dislike , comment etc. on my video.