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?
but it would be great if you can please provide your comments, like, dislike on my video how i did it..It motivates me to create better content for my audience.
I appologize for my bad sound quality but i am trying to improve it.
but it will be very difficult to add subtitle for this video because its around half an hour which explains all the concepts in deep.
Making this long video took lot of effort and time now adding a subtitle will be very tedious without any support.
Will suggest you to try automatic transcribe feature from youtube to translate it.
I had the same issue. my mistake was decrementing lower and upper. you don't decrement upper, the difference array needs to show it went down AFTER then last index, not within.
You could simplify your code a smidge, and save a little processing power, by removing your final for loop, and putting in an if check in the second to last loop, like this:
My js solution ran out of time for a few test cases
function arrayManipulation(n, queries) {
let a = new Array(n).fill(0);
for(let j = 0; j < queries.length; j++) {
let temp = queries[j]
let k = temp[0];
while(k <= temp[1]) {
a[k-1] += temp[2];
k++;
}
this one is the one that finally made it click for me...crazy how many different explanations are "whoosh" until the right person finds the "right" explanations.
But let's keep doing standardized testing in schools /s
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.
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.
One insight that might help is that we're keeping track of the change in values rather than the values themselves at each index. Therefore, by adding the k at a and subtracting it after b, we are saying that at a the total value increases by k compared to the previous element, and after b the total value decreases by k compared to b. Hope that helps!
Here's the same solution in swift in case anyone needs it :).
func arrayManipulation(n: Int, queries: [[Int]]) -> Int {
var sums = Int: Int
for query in queries {
sums[query[0]] = (sums[query[0]] ?? 0) + query[2]
sums[query[1] + 1] = (sums[query[1] + 1] ?? 0) - query[2]
}
var currentmax = 0
var sum = 0
sums.sorted{ `$0.0 < $`1.0 }.
compactMap{ `$0.1; sum += $`0.1; currentmax = sum > currentmax ? sum : currentmax}
return currentmax
Array Manipulation
You are viewing a single comment's thread. Return to all comments →
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.
It is a good video. I understood the algorithm clearly.
thanks @chandraprabha90.
but it would be great if you can please provide your comments, like, dislike on my video how i did it..It motivates me to create better content for my audience.
Could you add subtitles? I tried watching it but couldn't quite understand your accent through the audio
Hi Grozny,
I appologize for my bad sound quality but i am trying to improve it. but it will be very difficult to add subtitle for this video because its around half an hour which explains all the concepts in deep.
Making this long video took lot of effort and time now adding a subtitle will be very tedious without any support.
Will suggest you to try automatic transcribe feature from youtube to translate it.
Anyway thanks for watching.
Hi Grozny,
I have added subtitle for this tutorial and I hope it will you to understand logic with more clarity.
Nice approach you got there!
I had the same issue. my mistake was decrementing lower and upper. you don't decrement upper, the difference array needs to show it went down AFTER then last index, not within.
Thought to myself ....no js solutions here? then I find 3 of them, Js, ES6, readable wow.
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!
You could simplify your code a smidge, and save a little processing power, by removing your final for loop, and putting in an if check in the second to last loop, like this:
Perfect! Could you please explain me the thought process behind the solution?
My js solution ran out of time for a few test cases
function arrayManipulation(n, queries) { let a = new Array(n).fill(0); for(let j = 0; j < queries.length; j++) { let temp = queries[j] let k = temp[0]; while(k <= temp[1]) { a[k-1] += temp[2]; k++; }
} return Math.max.apply(Math, a); }
this one is the one that finally made it click for me...crazy how many different explanations are "whoosh" until the right person finds the "right" explanations.
But let's keep doing standardized testing in schools /s
Thanks for the post, it really made me understand the logic clearly
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.
Thanks a lot budy for your fantastic explanation ! Your thinking is really amazing like you . Good job.
most welcome. It would be great, if you can provide your feedback like, dislike , comment etc. on my video. It motivate me to do more for you all
hey used this logic its failing for 10 test cases with large inputs
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.
Thanks, your explanation is very helpful
Thank you so much for clearly explaining this.
did you got it?
getting it correct for few cases but when both indexes are same then its giving a error message
How can you implement the logic with ease without understanding the logic? Copy and pasting is not the same as "implementing"
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.
One insight that might help is that we're keeping track of the change in values rather than the values themselves at each index. Therefore, by adding the k at a and subtracting it after b, we are saying that at a the total value increases by k compared to the previous element, and after b the total value decreases by k compared to b. Hope that helps!
Here's the same solution in swift in case anyone needs it :).
func arrayManipulation(n: Int, queries: [[Int]]) -> Int { var sums = Int: Int for query in queries { sums[query[0]] = (sums[query[0]] ?? 0) + query[2] sums[query[1] + 1] = (sums[query[1] + 1] ?? 0) - query[2] }
}
refer to prefix sum algorithm.....you'll be clear!