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.

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.

## Array Manipulation

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

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.

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!

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.

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.

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.