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.
Make sure to use long instead of int to avoid integer overflow.
Don't update all values in your array. Just update the interval's endpoint values as shown below.
importjava.util.Scanner;publicclassSolution{publicstaticvoidmain(String[]args){Scannerscan=newScanner(System.in);intN=scan.nextInt();intM=scan.nextInt();/* Save interval endpoint's "k" values in array */long[]array=newlong[N+1];while(M-->0){inta=scan.nextInt();intb=scan.nextInt();intk=scan.nextInt();array[a-1]+=k;array[b]-=k;}scan.close();/* Find max value */longsum=0;longmax=0;for(inti=0;i<N;i++){sum+=array[i];max=Math.max(max,sum);}System.out.println(max);}}
For each of the "m" operations, we do not want to take O(n) time to process it. That's because our runtime will end up being O(nm). To get a O(n+m) runtime, we have to process each operation in O(1) time. To do so, we keep track of just the endpoints, which are just 2 numbers, instead of the O(n) numbers in between the endpoints. This is the main idea to decrease our runtime.
For a value k, we can mark its left endpoint a in the original array, along with its right endpoint b in the original array. To distinguish between a and b we can store +k for a and -k for b. Now, we technically have stored all information that the m operations represent, into an array. Most importantly, we stored it in O(m) time.
The next step is to actually find the maximum value based off of our unique representation of the data. We traverse our array from left to right. Whenever we reach a left endpoint a (which we represented with a positive number), we just add that to our sum. Whenever we reach a right endpoint b (which we represented with a negative number), we subtract that from our sum (well, technically we add a negative value). By doing so, the value sum represents the value that array[i] would have if we had applied all m operations to it. The maximum value of sum that we get while traversing the array is the value we return. If this algorithm is still unclear to you, try walking through HackerRank's Testcase 0 with the code above.
Let's try an example
Let's try to walk through an example. If we have 1 query and it wants to add 100 to elements 2 through 4 inclusive in a 7-element array, we want to have:
[0,0,100,100,100,0,0]
The idea is that we can represent this initially as:
[0,0,100,0,0,-100,0]
It's important to realize that this above array is not our final answer. We will walk through the array from array[0] to array[6] to create our final answer. When we reach array[2], it basically tells us that every element from here and to the right of it (array[2] to array[6]) should have 100 added to them. When we reach array[5], it tells us the same thing, except that every element should have -100 added to it. By following these 2 rules, we get
Hi. Thank you. Just keep coding and solving problems on HackerRank and you will steadily improve. Being active on the discussion forums is also a great learning experience. Best of luck.
Thanks !
If only all lthe explanations above said these words ,
"cumulative Slope algorithm works, when we add the value K only to the starting index(and assume it is being added until the end), but the Qs wants us to add only until till a index B, Therefore to stop the continous assumtion of adding K even after index B, we must put the index b+1 as -K. Thus from the working of our algorithm all the places form b+1 to end(inclusive) will be summed as (+K )+(-K), this way every new queries have to be started from their A index and ended at B by -K at B+ 1 , Now whe we cumulative add upto each index and replace it with the sum we get the previos ans array which we were getting from brute force
"
Hi. As for why we subtract k, I just added a detailed example to help answer your question in my original post.
Regarding the exact values of a and b, it's a little tricky since a and b are 1-indexed but our array is 0-indexed. So we want to subtract 1 from both a and b. However, for b we re-add 1 because we want to change values from a to binclusive as stated in the problem, so we want the end of the interval to be 1 to the right of b which is why we re-add the 1.
long int arr[n+1];
memset(arr,0,sizeof(arr));
long int m = queries.size();
long int max = 0;
long int sum = 0;
for(int i=0;i<m;i++)
{
long int a = queries[i][0];
long int b = queries[i][1];
long int k = queries[i][2];
arr[a-1] += k;
arr[b] -= k;
}
for(int x=0;x<n;x++)
{
sum += arr[x];
if(max < sum)
max = sum;
}
return max;
Addition needs to be done at a and subtraction at b+1.
Also,avoid memset on hackerrank sometimes it doesn't work fine.
Lastly,the final loop would run till <=n.
fromsysimportstdinif__name__=='__main__':(N,M)=[int(i)foriinstdin.readline().split()]vals=[0]*Nforiinrange(M):(a,b,k)=[int(i)foriinstdin.readline().split()]vals[a-1]+=ktry:vals[b]-=kexcept:# out of range of list (at the end)passprev=0foriinrange(len(vals)):prev+=vals[i]vals[i]=prevprint(max(vals))
Small difference is that the array is not N+1 long, but handle out of range via catching the exception.
The substraction is because at the end when are adding the values in vals array together, we shall add "k" to all values in val between "a" and "b", knowing when to stop adding "k" is impossible so we just add k upto the end of the list but subtract it starting from "b"
var arr = Array(repeating: 0, count: n+1)
for query in queries {
let a = query[0] - 1
let b = query[1]
let k = query[2]
arr[a] += k
arr[b] -= k
}
var largestValue = Int.min
var sum = 0
for n in arr {
sum += n
largestValue = max(sum, largestValue)
}
return largestValue
I have written array[b] in the code. Since b can have a maximum value of N (according to the problem description), we must have N+1 elements so that array[b] = array[N] does not crash the program.
Wow! I am so glad I found this explanation. Banging my head against this since a long time. Thanks a lot for taking out the time to add this explanation.:)
Disclaimer: Please correct me if i am wrong, I am just trying to provide a different explanation in the way that it clicked into my head while viewing your solution.
First Loop, Pt 1
I am first going to start off with why the indexes are chosen the way they are. This will lead into the next part of the same loop.
Ok, the first part is array[a - 1], Because the "indexes" given to us in the problem are actually the index + 1,which is something calles 1-indexed, which means the array its based off starts at 1, to stay true to the inclusive rule told to us in the problem, we must start at the beginning index.
We stop at array[b-1] beacuse, like the lat one, the var b given is not a accurate index so we must subtract one from it to get the starting point. To describe when to stop the set (more on this in a second), we need to put the -k one past the index where the k is being applied. Remebering that b is not a true index, we do array[(b-1) + 1]. The b - 1 gives us the true index of the end of the subarray that k is being applied to. But simplifying it gives us b as the index we need to use.
First Loop, Pt 2 and Second Loop
This part of the loop, in my opinion, is the hardest to understand. The start of the subarray is array[a - 1], which was explained up top. This marks where, in the second loop, sum will add that value to itself. Ex. 0,0,100,0,0,-100,0. This is an example of 1 query array implented in the way shown in the above solutuon. Think of of sum as a way to temporarily view what the index would look like at that period in time and adding numbers to starts this. For example, when the second loop hits the index with 100, sum, until it hits the -100, will be 100. Imagine the zeroes are basically saying "No other modifiers here like another set being in this set or an end of another set in the middle of this set". The -k at b is very interesting. The solution above says its a marker but it serves to strip the sum in the second loop of k. This is saying that because the loop has ended, we need a way to make the next indexes reflect that it has ended and remove k from the ongoing sum. The combination of multiple implmentations of this will allow the array to take full shape. We then find the max based on these multiple implmentations. It can be like the index viewed could be 500 but if you were to break it apart it could actually be (300 + -100 + 300). Which could mean many diffrent things, the 300s could repersent the start of diffrent sub lists and the -100 repsersents the end of another list. They all come together to repersent a mean. Adding this to a sum allows to find a max which will give us our answer.
Conclusion
So, in conclusion, the solution handles the array like diffrent points in time and adding up these points allows us to find a max.
Great solution. Very interesting to see how you can use edges to your advantage on these problems that deal with uniformly changing segments of arrays at a time. Saves time and helps with analysis. Incredible.
In the original code, " sum +=array[i] " adds up all the elements in the array at the end ...could you please tell me at what point we get the as 200 for " max "..??
static long ArrayManipulation(int n, int[][] queries) {
var additions = new long[n + 1];
foreach (var query in queries) {
var start = query[0];
var end = query[1];
var valueToAdd = query[2];
additions[start] += valueToAdd;
if (end + 1 < additions.Length)
additions[end + 1] -= valueToAdd;
}
long sum = 0;
long max = 0;
for (var x = 1; x < additions.Length; x ++) {
sum += additions[x];
max = sum > max ? sum : max;
}
return max;
}
Brilliant!!! It took me hours to solve but some failed due to timeout and next hours to read some hints in the discussion. I was stuck until I saw your explaination. Thanks.
mam I do this challenges in c# and could understand that C# and java are not different. i am not able to get to all the test cases passed somehow. are you sure it is working 100%? just want to understand in my IDE first so that i can get some idea
Thanks for providing such a good explanation. The code snippets help, but I definitely get more from you examples and explanations in the discussions. It was an easy translation from Java to C++ :)
Array Manipulation
You are viewing a single comment's thread. Return to all comments →
Java solution - passes 100% of test cases
From my HackerRank solutions.
Runtime: O(n + m)
Space Complexity: O(n)
Make sure to use long instead of int to avoid integer overflow.
Don't update all values in your array. Just update the interval's endpoint values as shown below.
For each of the "m" operations, we do not want to take O(n) time to process it. That's because our runtime will end up being O(nm). To get a O(n+m) runtime, we have to process each operation in O(1) time. To do so, we keep track of just the endpoints, which are just 2 numbers, instead of the O(n) numbers in between the endpoints. This is the main idea to decrease our runtime.
For a value k, we can mark its left endpoint a in the original array, along with its right endpoint b in the original array. To distinguish between a and b we can store +k for a and -k for b. Now, we technically have stored all information that the m operations represent, into an array. Most importantly, we stored it in O(m) time.
The next step is to actually find the maximum value based off of our unique representation of the data. We traverse our array from left to right. Whenever we reach a left endpoint a (which we represented with a positive number), we just add that to our sum. Whenever we reach a right endpoint b (which we represented with a negative number), we subtract that from our sum (well, technically we add a negative value). By doing so, the value sum represents the value that array[i] would have if we had applied all m operations to it. The maximum value of sum that we get while traversing the array is the value we return. If this algorithm is still unclear to you, try walking through HackerRank's Testcase 0 with the code above.
Let's try an example
Let's try to walk through an example. If we have 1 query and it wants to add 100 to elements 2 through 4 inclusive in a 7-element array, we want to have:
The idea is that we can represent this initially as:
It's important to realize that this above array is not our final answer. We will walk through the array from array[0] to array[6] to create our final answer. When we reach array[2], it basically tells us that every element from here and to the right of it (array[2] to array[6]) should have 100 added to them. When we reach array[5], it tells us the same thing, except that every element should have -100 added to it. By following these 2 rules, we get
giving us the final array of
I hope this helps. It was challenging for me to explain.
Let me know if you have any questions.
Could you explain why this works?
Hi. I added a detailed answer to your question in my original post. Hopefully it helps, it was tough to explain.
HackerRank solutions.
Awesome that definitely helped a lot! Thank you so much! :D
you are a great thinker rshaghoulian sir....Proud of you how to think like you... guide me
Hi. Thank you. Just keep coding and solving problems on HackerRank and you will steadily improve. Being active on the discussion forums is also a great learning experience. Best of luck.
I know this is kinda late, but holy, that is some genius work right here.
Lots of thanks for spending sooo much time and efforts to help us!
His thinking is his own skill/achievement, Why you are proud of him or his achievement???
Thanks for the amazing explanation!
You can watch this video : https://youtu.be/JtJKn_c9lB4 Really short video of 7 mins and explained awesome
Thanks for it : )
Thanks for the vid, this helped me greatly!
Thanks ! If only all lthe explanations above said these words , "cumulative Slope algorithm works, when we add the value K only to the starting index(and assume it is being added until the end), but the Qs wants us to add only until till a index B, Therefore to stop the continous assumtion of adding K even after index B, we must put the index b+1 as -K. Thus from the working of our algorithm all the places form b+1 to end(inclusive) will be summed as (+K )+(-K), this way every new queries have to be started from their A index and ended at B by -K at B+ 1 , Now whe we cumulative add upto each index and replace it with the sum we get the previos ans array which we were getting from brute force "
why we are subtracting k at b interval? why you are subtracting k to a[b] not a[b-1]?
Hi. As for why we subtract k, I just added a detailed example to help answer your question in my original post.
Regarding the exact values of a and b, it's a little tricky since a and b are 1-indexed but our array is 0-indexed. So we want to subtract 1 from both a and b. However, for b we re-add 1 because we want to change values from a to b inclusive as stated in the problem, so we want the end of the interval to be 1 to the right of b which is why we re-add the 1.
Hope this helps.
HackerRank solutions.
can u guyz tell me whats wrong in my code?
long arrayManipulation(int n, vector> queries) {
}
Addition needs to be done at a and subtraction at b+1. Also,avoid memset on hackerrank sometimes it doesn't work fine. Lastly,the final loop would run till <=n.
actually this code works fine in 1st 3 test cases... and my code is for 0-indexed that is why I used a-1 and b does it wrong?
Same algorithm in python3
Small difference is that the array is not N+1 long, but handle out of range via catching the exception.
of course,
Should be faster by a constant factor.
The substraction is because at the end when are adding the values in vals array together, we shall add "k" to all values in val between "a" and "b", knowing when to stop adding "k" is impossible so we just add k upto the end of the list but subtract it starting from "b"
This code still gives me a time error
This is giving "Runtime Error" in some test cases (when the input is big).
Same solution in Swift 3:
Updated version:
Cool, representing the array in unique way reduced O(mn) to just O(m+n). The explanation was good. Keep sharing knowledge, thanks !!
Thank you for the description, skipped right past the code.
Thanks man.. its ExtraOrdinary!!.. thanks again
thats a nice explaination...
awesome explanation,thank you
absolutely awesome explanation,thank you
can u tell me why u have taken size of array n+1
I have written array[b] in the code. Since b can have a maximum value of N (according to the problem description), we must have N+1 elements so that array[b] = array[N] does not crash the program.
HackerRank solutions.
thanq.... i got it..:)
Wow! I am so glad I found this explanation. Banging my head against this since a long time. Thanks a lot for taking out the time to add this explanation.:)
Disclaimer: Please correct me if i am wrong, I am just trying to provide a different explanation in the way that it clicked into my head while viewing your solution.
First Loop, Pt 1
First Loop, Pt 2 and Second Loop
Conclusion
So, in conclusion, the solution handles the array like diffrent points in time and adding up these points allows us to find a max.
Perfect explanation! Thanks buddy!
Nice Explaination.Good Approch.Thanks dude.
Thanks - today is my second day here in hackerrank and I totally did not expect such a problem and nimble sulution.
Mind=blown
That is amazing! Incredible logic! Thanks! ^_^
ITs very inciteful THANK YOU
Wow man!! Thank you so much!!
Awesome!
Great job! If you don't mind answering, roughly how long did it take you to think of this solution initially?
I didn't come up with this solution. I think I was told the solution, and I coded it myself.
HackerRank solutions.
I appreciate your honesty here Rodney, it makes me feel a little less inadequte! Your solution is beautiful either way.
thanks for the explaination :D
Good idea, I have just copied your idea too :) Thanks!
Your example showing how the expected array can be derived from the range-based array is a perfect explanation. Thank you!
@RodneyShag Finally understood the logic. Thanks a lot
Glad to hear. Glad I could help.
Amazing explaination.Thanks.
great solution. thank you.
Same algorithm on C++ // Complete the arrayManipulation function below. long arrayManipulation(int n, vector> queries) {
}
This code has a little bug. This is the code fixed:
Great solution. Very interesting to see how you can use edges to your advantage on these problems that deal with uniformly changing segments of arrays at a time. Saves time and helps with analysis. Incredible.
extra array[5] = 0 + 100 - 100 = 0; is a typo?
Got stuck with bad runtime O(nm), but didn't want to spend much time figuring it out on my own.
Then I saw your explanation.
You did a nice job explaining.
The example helped, too.
great idea!
Awesome work! Thanks for your explanation :)
impressive solution
In the original code, " sum +=array[i] " adds up all the elements in the array at the end ...could you please tell me at what point we get the as 200 for " max "..??
Nicely explained! Thanks.
Absolutely brilliant!
This explanation should be at the top. Was having a hard time wrapping my head around the solution till I read this explanation.
Brilliant job explaining! thanks
Very clever
great :)
Good explaination. Finally I got it. Thank you.
Thank you! your explanation was very clear to me.
this is very clear, thank you!
Really good explaination and example. Thanks!
Similar solution in C#:
what is the issue if i just traverse from assuming j= a to b and modify array[j] by array[j]+=k more efficient isn't it!!?
Brilliant!!! It took me hours to solve but some failed due to timeout and next hours to read some hints in the discussion. I was stuck until I saw your explaination. Thanks.
Great solution
was breakin my head as to how this solution works. thank you for the detailed explanation ... especially the code walkthrough
Very good explanation
Great Explanation! Thanks :)
Great explanation, thank you very much! That was an amazing approach
works perfectly. Thanks
you are genius , thank you
Thanks for the tip about using long, debugged that issue for a while.
mam I do this challenges in c# and could understand that C# and java are not different. i am not able to get to all the test cases passed somehow. are you sure it is working 100%? just want to understand in my IDE first so that i can get some idea
thanks for explaining
Hi, thanks for the wonderful explanation. Can you please check where I am wrong in this java code which I feel is similar to the one you posted.
public static long arrayManipulation(int n, List> queries) {
Great explanation. Took me a few minutes to grab it but it's really impressive.
Thanks for providing such a good explanation. The code snippets help, but I definitely get more from you examples and explanations in the discussions. It was an easy translation from Java to C++ :)
Thanks, It made me to think with a different POV to solve in Python
def arrayManipulation(n, queries):
i'm impressed with this solution.)) brilliant
good