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.

Scannerscan=newScanner(System.in);intn=scan.nextInt();intm=scan.nextInt();//This will be the "difference array". The entry arr[i]=k indicates that arr[i] is exactly k units larger than arr[i-1]long[]arr=newlong[n];intlower;intupper;longsum;for(inti=0;i<n;i++)arr[i]=0;for(inti=0;i<m;i++){lower=scan.nextInt();upper=scan.nextInt();sum=scan.nextInt();arr[lower-1]+=sum;if(upper<n)arr[upper]-=sum;}longmax=0;longtemp=0;for(inti=0;i<n;i++){temp+=arr[i];if(temp>max)max=temp;}System.out.println(max);

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.

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:

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.

Here the indices are starting from 1. So, we should be subtracting 1 from both lower index and upper index. Here you have done so for lower index, but haven't done for upper index.

It's because it doesn't go back down until the element after the section ends.

eg: n = 4, a = 1, b = 2 k = 3.
So we have 3 3 0 0 after reading in that line.
In his array he represents this as 3 0 -3 0
ie the subtraction is the element after the last element in the section.

The reason the lower value has a "-1" is because java uses 0-indexed arrays, ie they start at 0. But the input for this question only starts at 1. So he puts the values one index lower in the array.
The upper value has no "-1" for the reason in the above paragraph about subtracting after the last element in the section

It's a difference array. He is storing the difference/the changes that should be made in each index and then runs a loop to add up all these changes. You increment the lower bound because everything inbetween the lower and upper bound should be incremented but you dont want this change to continue for the rest of the array so you decrement at (upper+1).

WTF!!! It's true! I had a time out problem with test case 7 up to 12 I think and my code is good enough and didn't know what to do...until I read your comment, I removed all the empty spaces and the debugging prints (System.out.println for Java 8) and it worked :O
LOL thanks.

In java, we don't need to loop explicitly to assign zero to all the arr locations. When we create it, it has the zero as default values. I like your solution, thanks.

Is there a reason all the solutions posted above are written inside main() and not the provided function arrayManipulation() ? Or did hackerrank just change this over the past few years for readability?

// Complete the arrayManipulation function below.staticlongarrayManipulation(intn,int[][]queries){// initialize array with 0's of size nlongarr[]=newlong[n];// each successive element contains the difference between itself and previous elementfor(inti=0;i<queries.length;i++){// when checking query, subtract 1 from both a and b since 0 indexed arrayinta=queries[i][0]-1;intb=queries[i][1]-1;intk=queries[i][2];arr[a]+=k;if(b+1<n){arr[b+1]-=k;}}// track highest val seen so far as we golongmax=Long.MIN_VALUE;for(inti=1;i<arr.length;i++){arr[i]+=arr[i-1];max=Math.max(arr[i],max);}returnmax;}

I was wondering the same thing. The instructions say to complete the manipulation method, not to rewrite the main method. I assumed that it should work without timing out if I just get the manipulation method to the point where it is efficient enough.

Your solution is good but time complexity of your solution is O(n*m) which can not be used to solve this problem for given time constraint, so you need better approach which beats O(n*m)

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

thanks.
But if would be great ,if you can provide your comments, like, dislike on my video how i did it..It motivates me to create better content for my audience.

thanks. But if would be great ,if you can provide your comments, like, dislike on my video how i did it..It motivates me to create better content for my audience.

Thanks @Kanahaiya for sharing. Your video is very helpful.
I really liked the way you explained by dry running the solution. One of the best programming tutroial ever seen.
Surely, will look into other videos as well.. Thanks.

process.stdin.resume();process.stdin.setEncoding('ascii');varinput_stdin="";varinput_stdin_array="";varinput_currentline=0;process.stdin.on('data',function(data){input_stdin+=data;});process.stdin.on('end',function(){input_stdin_array=input_stdin.split("\n");main();});functionreadLine(){returninput_stdin_array[input_currentline++];}/////////////// ignore above this line ////////////////////functionmain(){varn_temp=readLine().split(' ');varlistSize=parseInt(n_temp[0]);varlineNumber=parseInt(n_temp[1]);letslopList=newArray();for(leti=0;i<listSize;i++){slopList.push(0);}for(vara0=0;a0<lineNumber;a0++){vara_temp=readLine().split(' ');constbeginElementPos=parseInt(a_temp[0]);constendElementPos=parseInt(a_temp[1]);constaddValue=parseInt(a_temp[2]);slopList[beginElementPos-1]+=addValue;if(endElementPos<listSize){slopList[endElementPos]-=addValue;}}letactualList=newArray();letsum=0;for(leti=0;i<listSize;i++){sum+=slopList[i];actualList.push(sum);}letmax=actualList.reduce((acc,val)=>{return(acc>val)?acc:val;},0);console.log(max);}

usingSystem;usingSystem.Collections.Generic;usingSystem.IO;usingSystem.Linq;usingSystem.Numerics;classSolution{staticvoidMain(String[]args){string[]tokens_n=Console.ReadLine().Split(' ');intn=Convert.ToInt32(tokens_n[0]);intm=Convert.ToInt32(tokens_n[1]);// Instantiate and populate an array of size NBigInteger[]arr=newBigInteger[n];for(inti=0;i<n;i++)arr[i]=0;for(inta0=0;a0<m;a0++){string[]tokens_a=Console.ReadLine().Split(' ');inta=Convert.ToInt32(tokens_a[0]);intb=Convert.ToInt32(tokens_a[1]);intk=Convert.ToInt32(tokens_a[2]);// Apply operationfor(intj=a-1;j<b;j++)arr[j]+=k;}Console.WriteLine(arr.Max(i=>i));}}

long tempMax = 0;
long max = 0;
for(int i=1; i<=n; i++)
{
tempMax += numList[i];
if(tempMax > max) max = tempMax;
}
What is this code doing , why we cant use numList.Sum()

Used the idea o modifiers, but without the n-sized array. Also in C#. Complexity is O(m log m), that can be less than O(n).

static long arrayManipulation(int n, int m, int[][] queries) {
long max = 0;
SortedDictionary<int,long> fakeArray = new SortedDictionary<int,long>();
// 'm' times
for (int i=0; i<m; i++) {
int a = queries[i][0];
int b = queries[i][1];
int k = queries[i][2];
// bit optimization: a '0' valued query will make no difference on resultant ones
if (queries[i][2] <= 0) continue;
if (!fakeArray.ContainsKey(a)) { // O( log m )
fakeArray.Add(a, k); // O( log m )
}
else {
fakeArray[a] += k; // O( log m )
}
if (b < n) {
b++;
if (!fakeArray.ContainsKey(b)) { // O( log m )
fakeArray.Add(b, -1 * k); // O( log m )
}
else {
fakeArray[b] -= k; // O( log m )
}
}
}
long current = 0;
foreach(long modifier in fakeArray.Values){ // O( 2*m )
current += modifier;
if (current > max) max = current;
}
return max;
}

## Array Manipulation

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

Same solution in C#

Same solution in Java

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.

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.

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:

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.

did you got it?

getting it correct for few cases but when both indexes are same then its giving a error message

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.

Hi , I have a doubt.

Here the indices are starting from 1. So, we should be subtracting 1 from both lower index and upper index. Here you have done so for lower index, but haven't done for upper index.

Can you please explain the reason behind this ?

It's because it doesn't go back down until the element after the section ends.

eg: n = 4, a = 1, b = 2 k = 3. So we have 3 3 0 0 after reading in that line. In his array he represents this as 3 0 -3 0 ie the subtraction is the element after the last element in the section.

The reason the lower value has a "-1" is because java uses 0-indexed arrays, ie they start at 0. But the input for this question only starts at 1. So he puts the values one index lower in the array. The upper value has no "-1" for the reason in the above paragraph about subtracting after the last element in the section

You don't have to do this:

because

longby default is 0could you please explain me the working of the code?

i think test code bigger than long int,so we need a larger data structure

Hi,

I have uploaded a video tutorial which can help you to understand the problem as well as logic.

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.

tnks @kanahaiya

no need to init array elements to 0 in Java

Hi, your solution works but I am not convinced!

I don't see how do you increment all elements between lower and upper!

Can you please explain? Thanks.

It's a difference array. He is storing the difference/the changes that should be made in each index and then runs a loop to add up all these changes. You increment the lower bound because everything inbetween the lower and upper bound should be incremented but you dont want this change to continue for the rest of the array so you decrement at (upper+1).

but how can we know about the upper index of a particular increment,when we are adding all at a once in a loop?

Using Java 8 syntaxis:

large amount of lines will crash your solution. And map fucntion need to make Boxing methinks and this takes much time

WTF!!! It's true! I had a time out problem with test case 7 up to 12 I think and my code is good enough and didn't know what to do...until I read your comment, I removed all the empty spaces and the debugging prints (System.out.println for Java 8) and it worked :O LOL thanks.

This is true, I spent too much time trying figure out why my solution was timing out. Deleted some whitespace and it ran fine.

Hi,

I have uploaded a video tutorial which can help you to understand the problem as well as logic.

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.

why temp += arr[i];

Array is already 0, you dont have to assign 0s to each array elements

scanner on large lines of input is not suitable solution, it reads too long

You don't need to loop the arr to put 0. Bydefault, it has the value zero when you initialize.

In java, we don't need to loop explicitly to assign zero to all the arr locations. When we create it, it has the zero as default values. I like your solution, thanks.

using an if statement inside the for loop will just contribute in complexity. you can replace it with Math.max function.

Is there a reason all the solutions posted above are written inside main() and not the provided function arrayManipulation() ? Or did hackerrank just change this over the past few years for readability?

Probably just for readability.

I was wondering the same thing. The instructions say to complete the manipulation method, not to rewrite the main method. I assumed that it should work without timing out if I just get the manipulation method to the point where it is efficient enough.

Same solution in Golang

Clever solution!

Can you help me see what is wrong with my code here?

import java.io.

; import java.math.; import java.security.; import java.text.; import java.util.; import java.util.concurrent.; import java.util.regex.*;public class Solution {

}

What is wrong with this code. Please help.

it may be showing Terminated due to timeout error because in test case 7 there is a huge number of input 10000000 100000 (like that)

you should try prefix array sum it is so simple

Hi,

Your solution is good but time complexity of your solution is O(n*m) which can not be used to solve this problem for given time constraint, so you need better approach which beats O(n*m)

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 video is helpful

thanks. But if would be great ,if you can provide your comments, like, dislike on my video how i did it..It motivates me to create better content for my audience.

Your video helped me understand the algorithm. I liked the video. Thank you so much

thanks. But if would be great ,if you can provide your comments, like, dislike on my video how i did it..It motivates me to create better content for my audience.

Thanks @Kanahaiya for sharing. Your video is very helpful. I really liked the way you explained by dry running the solution. One of the best programming tutroial ever seen. Surely, will look into other videos as well.. Thanks.

you will get TLE. Try different algorithm which takes less time.

Thanks for the clean code and the comment! It helped more than the entire discussion!

This line is unnecessary due to the fact that the default value of long in Java is 0L and there is no need for assigning them again to 0.

`for(int i=0;i<n;i++) arr[i]=0;`

Same solution in javascript

very smart,here is follow output to help me understand the idea

Guys, if you look for a clear understanding of the solution, I read a pretty clear comment down the road that clarified my mind.

Basically, when you add value from a to b you just need to know that it goes up from k and goes down of k after.

What this algo does is to register the slopes only, so we just need 2 entry, with O(1) complexity.

We just need to know that we are upping from k at the beginning and decreasing at the end.

Finally, the maximum would be...

The addition of all the slopes, that is why it's max(sum) of the tables, because the tables itself registers the slopes

Thanks a lot!!That really helped!

Can you explain the concept of just adding add subtracting at a particular index? I mean how have we arrived to this logic?

Hi,

I have uploaded a video tutorial which can help you to understand the problem as well as logic.

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.

Hi,

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

https://youtu.be/hDhf04AJIRs

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

I've add it to my playlist

haha..thank you.

but if you dont mind, Would really appreciate your feedback like, dislike , comment etc. on my video.

I didnt well understand that what will happen if b+1 is out of array bounds?

it can't be out of bounds, it saids that b>n in the problem statement.

if b+1 > n then the the addition of k from position a will continue till the last element of the array.

Hi,

I have uploaded a video tutorial which can help you to understand the problem as well as logic.

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.

Jesus christ, it all makes sense now after that graph lol, I kept wondering what drug these people were taking to arrive at this conclusion.

can you explain ? :)

Very well explained (Y)

i have got correct output of your test cases but 3 test cases of hackerrank are getting wrong. iam not understanding whats wrong.please help me

brilliant idea!

what about the custom input:

5 1

1 5 -100

wouldn't the output be 0? But the max would be -100 since all elements would be -100.

There's a constraint: 0 <= k <= 10^9

In your case of negative k, the minimum value can be obtained by the similar approach. Imagine a valley rather than a mountain.

why are you subtracting???? "( b < n ) res [ b ] -= k;"

How is your method faster than the following?

The "Apply operation part" is O(k) here. In the diff array version, apply operation is O(1)

hey did u passed all with this...i used same logic in C#..but passes till 6

your database is int? some tests data is too big

your code is only passing 3 test cases out of 10 . Don't post the code unless it pass all the test cases dude !!!!

bro, this is a discussion forum. Why are you demotivating a begineers ? Anyway I have submitted that code successfully. Thanks for the advice.

I used the same logic, it passes most of the tests but I get timeout error.

Hi,

I have uploaded a video tutorial which can help you to understand the problem as well as logic.

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.

if(b+1 <= n) numList[b+1] -= k;

Why we are substracting?

It is failing test case 4 to 13. Not sure why

It is failing test case 4 to 13. Can you please check

Used the idea o modifiers, but without the n-sized array. Also in C#. Complexity is O(m log m), that can be less than O(n).