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.

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.

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.

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.

## 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

longinstead ofintto 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 endpointain the original array, along with its right endpointbin the original array. To distinguish betweenaandbwe can store+kforaand-kforb. Now, we technically have stored all information that themoperations 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 endpointb(which we represented with a negative number), we subtract that from our sum (well, technically we add a negative value). By doing so, the valuesumrepresents 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.

Thanks for the amazing explanation!

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

aandb, it's a little tricky sinceaandbare 1-indexed but our array is 0-indexed. So we want to subtract 1 from bothaandb. However, forbwe re-add 1 because we want to change values fromatobinclusiveas stated in the problem, so we want the end of the interval to be 1 to the right ofbwhich is why we re-add the 1.Hope this helps.

HackerRank solutions.

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.

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 1First Loop, Pt 2 and Second LoopConclusionSo, 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) {

}

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!