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?

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.

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.

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()

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

`}`

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

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.thanks bro..

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

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.

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?

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?

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.

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.

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