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.

see, you are adding sum to a[p] and adding negative sum at a[q+1]. which make sure that when you add element from a[p] to a[q] sum is added only once and it should be subtracted at a[q+1] as this sum span from p to q only.
Rest array element are either 0 or some other input sum.
max of addition will be output.
refer to above code for p, q, and sum.

Instead of storing the actual values in the array, you store the difference between the current element and the previous element. So you add sum to a[p] showing that a[p] is greater than its previous element by sum. You subtract sum from a[q+1] to show that a[q+1] is less than a[q] by sum (since a[q] was the last element that was added to sum). By the end of all this, you have an array that shows the difference between every successive element. By adding all the positive differences, you get the value of the maximum element

n, inputs = [int(n) for n in input().split(" ")]
list = [0]*(n+1)
for _ in range(inputs):
x, y, incr = [int(n) for n in input().split(" ")]
list[x-1] += incr
if((y)<=len(list)): list[y] -= incr;
max = x = 0
for i in list:
x=x+i;
if(max<x): max=x;
print(max)

And the same approach in ruby -- I claim no credit for working this out -- I wrote this after reading the comments and code posted here.

Just thought I'd add a ruby solution for anyone looking for one.

N,M=gets.chomp.split(' ').map(&:to_i)# create array of zeros of length N + 1arr=Array.new(N+1,0)M.timesdo# cycle through and get the inputsstart,finish,value=gets.chomp.split(' ').map(&:to_i)# increment value at start of sequencearr[start-1]+=value# decrement value at first position after sequencearr[finish]-=valueendtmp=0max=0arr.eachdo|value|# step through summing arraytmp+=value# capture the max value of tmpmax=tmpifmax<tmpendputsmax

intmain(){longlongintn,k,i,max=0,x=0;scanf("%lld %lld",&n,&k);int*a=(int*)malloc(sizeof(int)*(n+1));for(i=0;i<n;i++){*(a+i)=0;}for(i=0;i<k;i++){longlongintc,d,g;scanf("%lld %lld %lld",&c,&d,&g);*(a+c)+=g;if(d+1<=n){*(a+d+1)-=g;}}for(i=1;i<=n;i++){x+=*(a+i);if(max<x){max=x;}}printf("%lld",max);/* Enter your code here. Read input from STDIN. Print output to STDOUT */return0;}

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?

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

This does not work for the current version of this problem. The prompt is asking for the solution of a method with two args, one n for the size ofthe array and a queries array of arrays with start index, end index, and value. There should be no need for gets.chomp().

I believe what he's trying to say is this:
There are two approaches here -
1. The difference array approach (the one every one is praising as being more efficient)
2. The intuitive approach - i.e., just going through each group of a,b,k values and incrementing elements located between a and b in the array, then finally searching through for a max)

The reason approach 1 is more efficient is because the operation for the difference array only requires a maximum 2 adjustments per transformation (you increment the value at the start index by k, and decrement the value after the end index by k).
Contrast this with approach 2, where actually going through the array and incrementing every value within the specified 'a-b' range could result in N operations.

So approach 2 could take a max of O(N * M) time- where 'M' is the number of operations, and N is the size of the array
And approach 1 could take a max of O(2 * M) time, which is considered equivalent to O(M)

Does that make sense? Someone correct me if I'm wrong! Cheers :)

the best way to understand it is form a simple example.

say there are 4 of us in a line: 1. me 2. you 3. bob 4. sue
and we all start out with zero points.

Thcan be represented as (where my points are in the first index, your in the second, bob's in the third, sue's in fourth):

0 0 0 0

Furthermore, we go through rounds, where in each round a contiguous block of us can receive some set amount of points.

So in round one, say 2 points are awarded to anything in the range of start index = 1, and end index = 2. This means that you and bob, who are in the range, get 2 points.

But rather than write the current score as:
0 2 2 0

We instead want to write the score as:

0 2 0 -2

Because we want each value to represent how much greater/less than it is from the previous-index value. Doing this allows us to only ever need to change two elements in the list for a given round.

Now say we play one more round, and 1 point is awarded to all people in range of index = 0 to index = 1. This gives you

1 2 -1 -2

All I did was add the point value to the start index, and subtract it from the "end index + 1".

Then calculating the max is simply a matter of going through that list, adding each element to an accumulator variable (as this summing process reveals the actual value of an element at any given point - e.g., you would have 3 points at the end because your score is the result of 1 + 2), and having a variable which keeps track of the running max.

Can some one please help as to why my solution gives a segmentation fault?

include

include

include

include

int main() {

unsigned long long int n,m,l,b,k,i,val=0;
scanf("%llu%llu",&n,&m);
unsigned long long int a[n+1];
for(i=1;i<=n;i++)
{
a[i]=0;
}
while(m--)
{
scanf("%llu%llu%llu",&l,&b,&k);
for(i=l;i<=b;i++)
{
a[i]+=k;
if(a[i]>val)
{
val=a[i];
}
}
}
printf("%llu",val);
return 0;

Maximum array size has to be 10^7 which is not possible in case of C. I tried Dynamic memory allocation (malloc) which worked but got TLE for bigger test cases

fromitertoolsimportaccumulaten,m=map(int,input().split(' '))dx=[0]*(n+1)# allow run past endfor_inrange(m):a,b,c=map(int,input().split(' '))dx[a-1]+=cdx[b]-=cprint(max(accumulate(dx)))

The question asks for a 1 indexed list and the a,b values read in are read in starting from 1 not 0. If you do not use (n+1)if b happens to be the last number of your list it will go out of bounds.

The 0 index value will always be 0 so it doesn't affect your answer when you sum for max difference.

Just improved your code a bit.
- split() is slightly faster than split("")
- an if was not needed as always true
- variables names fit those used in the exercise

I took the ideas explained here to put also into python in a bit more spelled-out way to help make sense of this more abstract work-around.

def arrayManipulation(n, queries):
# Big O (N)
res = [0]*(n+1) # we only really need one terminal row, since we're applying each pass to all rows below
# loop through all the queries and apply the increments/decrements for each
# Big O (M) (size of queires)
for row in range(len(queries)):
a = queries[row][0]
b = queries[row][1]
k = queries[row][2]
res[a-1] += k # increment the starting position
# this is where a loop would increment everything else between a & b by k
# but instead of taking b-a steps, we take a constant 2 steps, saving huge on time
res[b] -= k # decrement the position AFTER the ending position
# now loop through res one time - Big O (N) (size of res)
sm = 0 # running sum
mx = 0 # maximum value found so far
for i in range(len(res)):
sm += res[i]
if sm > mx:
mx = sm
# total run time is Big O (2*N + M) >> Big O(N)
return mx

The key concepts in my opinion here are:

1) we don't need to build the full aray, since it's impossible for any row but the last to have the max value. This is impossible because we apply the adjustments to every subsequent row of the resulting 2-D array.

2) we don't need to actually increment each value for indices 'a' through 'b'. While that's the most straight-forward way, that also requires x many (a minus b) steps for each pass of the loop. By noting instead where to start incrementing and where to stop incrementing (noted by decrementing after what would be the final increment), we can note the adjustments to apply without having to take every step each time. We can then run a separate single loop to go over each of the increments and keep a running sum of all the overlapping increments. The decrement allows us to know when that range where the increment applied is over by reducing the running sum by that number - in other words when that range is ended, we would have to look at overlapping increments excluding that one that just ended going forward to see if anything is bigger.

Someone else in here gave an image of a stair/hill which I found extremely helpful in visualizing and understanding this concept. The basic idea here is that instead of actually applying each increment, we can just note what the increment and range is and one by one go through each place and apply all the compounded increments at once. Loop 1 saves the increments in a different format, Loop 2 checks the overlap. And by using two separate loops we have basically Big O (N) rather than Big O (N^2) - or more specifically Big O (2N + M) instead of Big O (NM + N), where N is the size of the resulting array and M is the size of the queries array.

def arrayManipulation(n, queries):
arr=[0]*n
for _ in queries:
start=[0]-1
end=[1]-1
val=_[2]
topVal=end+1
for i in range(start,topVal):
arr[i]+=val
return max(arr)

m = input().split()

n = int(nm[0])

m = int(nm[1])

queries = []

for _ in range(m):
queries.append(list(map(int, input().rstrip().split())))

can the same be written like this:
def arrayManipulation(n, queries):
arr_n=[0]*n
for i in range(len(queries)):
n1=queries[i][0]
n2=queries[i][1]
for j in range(n1-1,n2):
arr_n[j]=arr_n[j]+queries[i][2]
return max(arr_n)
This is giving me a tiemout error while submitting.
can u assist here?

yeah,at the beginning, l got the same problem as well. This algorithm's complexity could be o(n). Try to learn something about prefix sum array.I hope this can help.

I still have some doubt if anyone could explain it. I understand that it is making use of difference array to keep track of the difference between items rather than updating every item.

However as I understand, size of difference array is one less than total items in the actual array.

However the logic used seems to be a variant of difference array that I am not able to understand. It would be great if someone could help me connect the dots from this difference array to the actual working solution of this problem. Thanks.

so finally, 1st col is always the real value, and others are accumlated of previous values and it self.
so actual values are 100 200 200 200 100, max is 200

As i have understood
(5 , 3) 0 0 0 0 0
(1 , 2) 100 100 0 0 0 -> first and second places i.e a=1,b=2 , k=100, now a+k = 0+100 = 100, b+K = 0+100 = 100.
(2 , 5) now from 2 to 5 i.e 2,3,4,5 are added with K i.e 100.
already 2=100 now 2 becomes 100+100 =200, simialrly 3 = 0+100=100,4=0+100=100,5=0+100=100.
(3 , 4) now 3 and 4 are added with 100.
ie 3 value is 100 it becomes 100+100=200, 4 becomes 100+100=200.

you aren't allocating space for a that way. He uses new to create an array on the heap. You are trying to declare it on the stack, but you can't do that with a dynamic value like 'n'

If you have a problem understanding dynamic memory then make use of vector . It allocates memory dynamically wherein the user doesn't have to deal with pointers .

vector arr(n); declares an array of long int of length n.

Here ,I add all the positive values of the difference array to get the maximum element . But , the answer comes out to be wrong for all the test cases except sample one ...

what do u mean by previous element?
is it a[p-1]for a[p] or the previous state of a[p] before the current updation operation?
difference is betweentwo succesive elements or in the same element before and after one query is executed?

It is a[p-1] for a[p] ie. the difference between two successive elements.

Well ,now ,i understood my mistake . I was just adding the positive differences.
But the problem requires maximum element in an array , so there must be a comparison while adding the differences.

Your Explanation is wrong and misleading.Logic behind @
amansbhandari algorithm is at any index p he is storing by how much this value is more than previous value, subsequently if value from p to q is 100(to be exact 100 more than other values) q+1 should be 100 less than values between p and q.That is why we subtract 100 at q+1 index of array.

That's what I understand this theory.
We can try to understand this logic like we imagine Supermario walking on a N width horiz line. a and b is the
point on the line, k is the mushroom Mario like to eat.
When Mario go to the point at a,he eat the k size mushroom and become taller,after he have walked through point b,
his height reverse to the origin height before he eat the mushroom.
eg.
1. When Mario is walking to a, he eat a k size mushroom, and become k bigger
2. Then Mario is walking to a', he eat a k' size mush, and become k' bigger, now Mario's height is (k + k')
3. If Mario have walked to b, so he pooped out the mushroom and become k smaller, the only way that he can
become larger is to meet a new (a,b) point and eat a new k size mushroom
4. The rest can be done in the same manner.

What we need to do is tracing the Mario's biggest height when walking through that muliple query's a and b point.

awesome explanation..
btw i wanted to ask if this is what we call segment tree..and if we can use this method to solve questions with the segment tree tags..
P.S. : I have a very little knowledge about the segment trees.

here we are adding value only in a[p] but we have to add value from a[p] to a[q] .and what is the requirement of a[q+1] here?????
plz clear my doubt ...

Why is my code not working on the same approach ?
Please help Can't find anything wrong !

include

include

using namespace std;

int main(){

int N,M,a,b,c;
cin>>N>>M;
long int *arr=new long int[N+1];
for(int i=0;i<M;i++){
cin>>a>>b>>c;
arr[a]+=c;
if(b+1<=N){
arr[b+1]-=c;
}
}
int x=0,ans=0;
for(int i=1;i<=N;i++){
x+=arr[i];
ans=max(ans,x);
}
cout<<ans;

We can try to understand this logic like we imagine Supermario walking on a N width horiz line. a and b is the
point on the line, k is the mushroom Mario always like to eat.
When Mario go to the point at a,he eat the k size mushroom and become taller,after he have walked through point b,
his height reverse to the origin height before he eat the mushroom.
eg.
1. When Mario is walking to a, he eat a k size mushroom, and become k bigger
2. Then Mario is walking to a', he eat a k' size mush, and become k' bigger, now Mario's height is (k + k')
3. If Mario have walked to b, so he pooped out the mushroom and become k smaller, the only way that he can
become larger is to meet a new (a,b) point and eat a new k size mushroom
4. The rest can be done in the same manner.

What we need to do is tracing the Mario's biggest height when walking through that muliple query's a and b point.

here we are taking the difference of highest number and lowest number that is the loging has been implemented here. you could see in the peice of code to finding max value at each iteration adding the next element to the value (x=x + a[i]).

It took me a while to understand as well, but its pretty brilliant actually.
First let me explain why this approach is good: You have k operations acting on a range of [a,b], for each of these k operations, a could be 1 and b = n , that makes a normal (add sum to 'a' through 'b') solution O(k * n ).

In this solution for each of the k operations, you make exactly 2 operations, so its constant time for each k operation. At the end, you go through the entire n length array and get the largest. That makes it a O(k) + O(n) operation ==> much cheaper

Now, on to the solution itself, assume the array size, n = 10
lets take operations to be(lowerIndex upperIndex sumToBeAdded):
oper1: 1 5 3 oper2: 4 8 7 oper3: 6 9 1

initially your array looks like (array of size n + 1): 00000000000

after 1 5 3 : 0 3 0 0 0 0 -3 0 0 0 0

after 4 8 7 : 0 3 0 0 7 0 -3 0 0 -7 0

after 6 9 1 : 0 3 0 0 7 0 -2 0 0 -7 -1

so, that is O(k) where we processed the array, now for the magic... as we iterate through the n elements, keep adding a running sum, the running sum at each index will give you the final value that was supposed to be at that index (had you added the oper's sum to 'a' through 'b' for each of the k operations...)

on filling all elements of array[n+1] with the running sum and noting the largest, the array transforms to : 0 3 3 3 10 10 8 8 8 1 0 , and this happends in O(n) time

You can also visualize this by thinking that a[p] denotes the starting point of an uprising in value and a[q+1] denotes the end point. In this case, traverse through the array is like climbing a mountain, and the sum we keep denotes the elevation.

I too tried Lazy Propagation but got segmentation fault after 6 test cases, even the Question Setter in the editorial says that Lazy Propagation can not pass all test cases. Please show the code you wrote which passed all the test cases.

I got AC using Segment tree with lazy propagation. http://ideone.com/DzZlW7. Just keep on updating the tree, and at each node store the maximum of its left and right child. And after all the k updates, apply Range maximum query.

because 'n' is too large to allocate for static array.
(the maximum size of static array is different by complier).
so we allocate dynamic array of size 'n+1'.

you should create a generator because when the test it have big number of queries your program delay too much.

len_array,queries=map(int,raw_input().strip().split())array=[0]*len_arraydefgenerator_queries(queries):init=0index=0whileindex<queries:yieldmap(int,raw_input().strip().split())index+=1fora,b,kingenerator_queries(queries):foriinxrange(a-1,b):# another generatorarray[i]+=k# maybe use threads hereprintmax(array)

def algoCrush():
try:
listSize, opsCount = map(int, raw_input().split())
except:
return None
#constraint 1 and 2
if not all([listSize >=3, listSize <= 10**7, opsCount >= 1, opsCount <= 2*10**5]):
return None
crushList = [0]*listSize
for _ in range(opsCount):
try:
start, end, addnum = map(int, raw_input().split())
except:
return None
#constraint 3 and 4
if not all([start >= 1, start <= end, end <= listSize, addnum >= 0, addnum <= 10**9]):
return None
crushList[start-1] += addnum
if end <= (listSize -1):
crushList[end] -= addnum
prev = high = 0
for i in range(listSize):
prev += crushList[i]
if high < prev:
high = prev
print high
algoCrush()
For instance, when list size less than 3, it should not return any thing.
2 3
1 2 3
1 2 3
1 2 3
9 -----> should have failed.
Likewise, when there are strings in numbers.
2 3
1 2 3
1 2 3
1 2 str
Traceback (most recent call last):
File "a.py", line 4, in <module>
a, b, k = [int(n) for n in raw_input().split() ]
ValueError: invalid literal for int() with base 10: 'str'

Not exactly slower, if we look at the constants behind O-s. Say, we sort events, there are 4e5 of them, so we get log(4e5)*4e5/log(2)=7.44e6, the difference became not so drastic. And sort at any step uses conditional operations that, when incorrectely predicted, break the CPU conveyer. That costs about 10 ticks each time. And they would be incorrectely predicted in about 50% cases, that is expensive. The proposed approach is straightforward, the only conditional is "if ( max < x ) max = x" that probably would be saturated fast, that is in most cases it would not be taken, and CPU would be able to predict that.
About numbers: my sorting approach runs in 0.01-0.02s, this approach in my implementation runs in 0.03-0.04s on strong testcases. That is probably because we have to use quite a lot of (random access) memory, 80MB instead of 3.2MB in the sorting approach, and it leads to cache misses and TLB trashing. HugeTLB could help a bit, had it been turned on on the testing server.

Surely that's O(N) space. There's no need to store the array itself. Just record the update boundaries along with the k value (-k for the end boundary), sort them by location (then by value if at the same location), then scan over them with a running total.

I experience the same issue. If I run test case 13 locally, my code passes, but if I try the same code remotely on HR, cases 7 -> 13 all fail. Out of memory ?

Wanna know something! Is there any classic name of this approach? Can anyone give some links to other problems which is similar to this problem? I think, I've seen this type of problem before, but can't remember where and couldn't solve then also!

This code finds the maximum possible subarray sum.
and the maximum sum is the answer.
This means that we assume that atleast 1 element in the array will be 0. Is that necessary??

Wouldnt have came up with the idea, I was using partitions..., although I didnt actually see code the explanations below were enough to make a light bulb pop!

I came out with the same approach in java, but code is ridiculously larger :P

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
/**
* Created by juanmf on 08/02/17.
*/
public class AlgorihmicCrush {
public static void main(String[] args) {
/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
Scanner s = new Scanner(System.in);
int N = s.nextInt();
int M = s.nextInt();
//int[] operations = new int[N + 1];
List<Long>[] operations = new List[N + 1];
while (s.hasNextInt()) {
int from = s.nextInt();
int to = s.nextInt();
long sum = s.nextLong();
addOperation(operations, from, to, sum);
}
System.out.println(copmileOperations(operations));
}
private static long copmileOperations(List<Long>[] operations) {
long crawler = 0;
long max = Integer.MIN_VALUE;
for (List<Long> ops : operations) {
if (null == ops) {
continue;
}
for (Long op : ops) {
crawler += op;
}
if (max < crawler) {
max = crawler;
}
}
return max;
}
private static void addOperation(List<Long>[] operations, int from, int to, long sum) {
if (null == operations[from]) {
operations[from] = new ArrayList<Long>();
}
operations[from].add(sum);
to++;
if (to >= operations.length) {
return;
}
if (null == operations[to]) {
operations[to] = new ArrayList<Long>();
}
operations[to].add(-sum);
}
}

I also did it on Java. At first, it only passed up to test 3, due some precision loss, having int k instead of long k. This may be obvious to many here, but I still thought it was interesting to see how such a small detail changes it all. Here is the code (in comments, the code with int, which fails after test 3).

public static void main(String[] args) {
int N, M, a, b;
long k; // int k;
Scanner in = new Scanner(System.in);
N = in.nextInt();
M = in.nextInt();
long[] differenceArray = new long[N+1]; // int[] ...
for (int i=0; i<M; i++)
{
in.nextLine();
a = in.nextInt();
b = in.nextInt();
k = in.nextLong(); // in.nextInt();
differenceArray[a] += k;
if (b+1<=N)
differenceArray [b+1] -= k;
}
long max = 0, addedDifference = 0; // int
for (int i=1; i<=N; i++)
{
addedDifference = addedDifference + differenceArray[i];
if (max < addedDifference)
max = addedDifference;
}
System.out.println(max);
in.close();
}

Let's view the array as a list of histograms. Each position in the array has a histogram with a certain variable heigth. It would be cumbersome to keep track of the heigth of every single histogram. Instead, you could just keep track of how much the height of a given histogram differs from the one preceding it (in a continuous setting, this would mean to keep track of the derivative of a function, not the function itself).

Here, we know there is an increment of k for the height of the histogram in position a (a positive slope of k from a-1 to a), but then the height remains constant at positions a+1, a+2,...,b. Then again, we know that position b was the last position where histograms were incremented by k, so there is a decrement of -k at position b+1 (negative slope of -k from b to b+1).

Nice algorithm. However I'd prefer if you described your approach, rather than posting your code. (This would also avoid people asking "can you explain your logic".) Leave the coding as an excercise for the reader :)

I ended up using a TreeMap. Since there can only be 400K inflection points max, it seemed wasteful to create an array of 10M values and then traverse the 10M values to compute a result. So this results in a time of O(M log M). As others have mentioned, the additional constant time is much higher than long[], so it's hard to estimate the actual performance difference. This would really win if M was small (and N large), and is time/space independent of N. (The code reads and discards N.)

Your solution is O(n+m) runtime and O(n) space complexity, which is slower than what you mentioned in your post, but is still great. The O(n+m) is a result of the fact that m may be larger than n. The space complexity is due to you creating an array of size n.

The runtime complexity is O(N) because M upper bound (2 * 10^5) is lower than N upper bound and even if it was equal (M upper bound = N upper bound), it would be O(N+N), which is O(2N), which could be reduced to O(N).

I usually analyze runtimes assuming variables are unbounded. I find it to be more useful that way since HackerRank usually creates arbitrary bounds for variables.

In the bounded case, you are correct, you can consider it to be O(N).

Sorry, but this is just bruteforce. Your code runs in O(n), but the input is O(M). By creating the array in code (which is not part of the input) you are using exponential memory and runtime (because the length of N is logarithmic compared to the actual length of the array).

See my anwser for a better idea about the solution.

I like how this comment correctly points out the insufficiencies of the original post using actual theoretical arguments, yet still gets downvoted massively.

If the problem statement is exactly the same, and you were asked to find the minimum, you simply loop through the array using Math.min() instead of the Math.max() in the last loop in this solution.

The resulting array will have all M operations performed on it. We can find the max/min/mean/median/mode, whatever we want, since it's just an array of final values. I can take a look at your code (if you want to alter this solution to see why it didn't work.

I could understand that we are tracking start(a) and end(b) points and in between them all are sum of K.
But i couldn't understand the last loop.
Can anyone please explain why summing the array will work for our solution?

## Array Manipulation

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

Guys, below is the code in O(n) time complexity and O(1) Auxiliary space

Your approach is brilliant. Hats off

can you please explain the logic behind that.?

see, you are adding sum to a[p] and adding negative sum at a[q+1]. which make sure that when you add element from a[p] to a[q] sum is added only once and it should be subtracted at a[q+1] as this sum span from p to q only. Rest array element are either 0 or some other input sum. max of addition will be output. refer to above code for p, q, and sum.

Instead of storing the actual values in the array, you store the difference between the current element and the previous element. So you add sum to a[p] showing that a[p] is greater than its previous element by sum. You subtract sum from a[q+1] to show that a[q+1] is less than a[q] by sum (since a[q] was the last element that was added to sum). By the end of all this, you have an array that shows the difference between every successive element. By adding all the positive differences, you get the value of the maximum element

Important points to note in this solution.

1)the first element of array a will always remain zero since 1<= a <=b <=n; 2

2)the second element of array a is the second element of the array after m operations.

Same solution translated in python -

And the same approach in ruby -- I claim no credit for working this out -- I wrote this after reading the comments and code posted here.

Just thought I'd add a ruby solution for anyone looking for one.

Same solution in C

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

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

*(a+c)+=g; if(d+1<=n){ *(a+d+1)-=g; }

could you please explain me the logic?

pls explain logic

This does not work for the current version of this problem. The prompt is asking for the solution of a method with two args, one n for the size ofthe array and a queries array of arrays with start index, end index, and value. There should be no need for gets.chomp().

This worked, but I'm still trying to understand why this was the correct answer.

Because it takes less time to execute. Otherwise solution execution got time outed

You are not answering the question.

I believe what he's trying to say is this: There are two approaches here - 1. The difference array approach (the one every one is praising as being more efficient) 2. The intuitive approach - i.e., just going through each group of a,b,k values and incrementing elements located between a and b in the array, then finally searching through for a max)

The reason approach 1 is more efficient is because the operation for the difference array only requires a maximum 2 adjustments per transformation (you increment the value at the start index by k, and decrement the value after the end index by k). Contrast this with approach 2, where actually going through the array and incrementing every value within the specified 'a-b' range could result in N operations.

So approach 2 could take a max of O(N * M) time- where 'M' is the number of operations, and N is the size of the array And approach 1 could take a max of O(2 * M) time, which is considered equivalent to O(M)

Does that make sense? Someone correct me if I'm wrong! Cheers :)

Yeah, if we went with the brute force solution with two nested for loops, we will get a graph as below for the array if we used the data below

but if we used the second method which is adding at the first index and subtracting at the index afer the last we get this graph

and then we can get the maximum out of summing the results as below

but I can't understand the logic of least step ( summing step )

the best way to understand it is form a simple example.

say there are 4 of us in a line: 1. me 2. you 3. bob 4. sue and we all start out with zero points.

Thcan be represented as (where my points are in the first index, your in the second, bob's in the third, sue's in fourth):

0 0 0 0

Furthermore, we go through rounds, where in each round a contiguous block of us can receive some set amount of points.

So in round one, say 2 points are awarded to anything in the range of start index = 1, and end index = 2. This means that you and bob, who are in the range, get 2 points.

But rather than write the current score as: 0 2 2 0

We instead want to write the score as:

0 2 0 -2

Because we want each value to represent how much greater/less than it is from the previous-index value. Doing this allows us to only ever need to change two elements in the list for a given round.

Now say we play one more round, and 1 point is awarded to all people in range of index = 0 to index = 1. This gives you

1 2 -1 -2

All I did was add the point value to the start index, and subtract it from the "end index + 1".

Then calculating the max is simply a matter of going through that list, adding each element to an accumulator variable (as this summing process reveals the actual value of an element at any given point - e.g., you would have 3 points at the end because your score is the result of 1 + 2), and having a variable which keeps track of the running max.

Thank you for your detailed explanation. It helped!

This is the best explanation of the difference array I have read in these discussions -- thank you for making it click in my head.

I would not suggest eclipsing

`list`

Can some one please help as to why my solution gives a segmentation fault?

## include

## include

## include

## include

int main() {

}

Maximum array size has to be 10^7 which is not possible in case of C. I tried Dynamic memory allocation (malloc) which worked but got TLE for bigger test cases

yeah it is getting a tle. We need to use a different algorithm. I wanted to know what the problem in my code was so i posted my solution.

use long instead of int.

Hi Vineet could u explain what logic have you followed?

Same solution but optimized:

That's so good! You are awesome!

can you explain why it's (n+1) and not (n)?

The question asks for a 1 indexed list and the a,b values read in are read in starting from 1 not 0. If you do not use (n+1)if b happens to be the last number of your list it will go out of bounds.

The 0 index value will always be 0 so it doesn't affect your answer when you sum for max difference.

why are you subtracting dx[b] -= c ?????

Walk through the array it may help.

Query 1 -> [1, 2, 100] Array 1 -> [0, 100, 0, -100, 0, 0, 0] Query 2 -> [2, 5, 100] Array 2 -> [0, 100, 100, -100, 0, 0, -100] Query 3 -> [3, 4, 100] Array 3 -> [0, 100, 100, 0, 0, -100, -100] Array Accumulated -> [0, 100, 200, 200, 200, 100, 0] Result -> 200

The use of accumulate is so brilliant!

Nice

How does that bottom for list return the maximum value in the list? Could you explain the logic to me please?

Why are you checking if "y" is <= len(list) ? This is given by the problem, right?

Really liked this solution! One question, shouldn't it be max=-float('inf')?

P.S - Talking about the python version

Just improved your code a bit. - split() is slightly faster than split("") - an if was not needed as always true - variables names fit those used in the exercise

I took the ideas explained here to put also into python in a bit more spelled-out way to help make sense of this more abstract work-around.

The key concepts in my opinion here are:

1) we don't need to build the full aray, since it's impossible for any row but the last to have the max value. This is impossible because we apply the adjustments to every subsequent row of the resulting 2-D array.

2) we don't need to actually increment each value for indices 'a' through 'b'. While that's the most straight-forward way, that also requires x many (a minus b) steps for each pass of the loop. By noting instead where to start incrementing and where to stop incrementing (noted by decrementing after what would be the final increment), we can note the adjustments to apply without having to take every step each time. We can then run a separate single loop to go over each of the increments and keep a running sum of all the overlapping increments. The decrement allows us to know when that range where the increment applied is over by reducing the running sum by that number - in other words when that range is ended, we would have to look at overlapping increments excluding that one that just ended going forward to see if anything is bigger.

Someone else in here gave an image of a stair/hill which I found extremely helpful in visualizing and understanding this concept. The basic idea here is that instead of actually applying each increment, we can just note what the increment and range is and one by one go through each place and apply all the compounded increments at once. Loop 1 saves the increments in a different format, Loop 2 checks the overlap. And by using two separate loops we have basically Big O (N) rather than Big O (N^2) - or more specifically Big O (2N + M) instead of Big O (NM + N), where N is the size of the resulting array and M is the size of the queries array.

def arrayManipulation(n, queries): arr=[0]*n for _ in queries: start=

[0]-1 end=[1]-1 val=_[2] topVal=end+1 for i in range(start,topVal): arr[i]+=val return max(arr)m = input().split()

n = int(nm[0])

m = int(nm[1])

queries = []

for _ in range(m): queries.append(list(map(int, input().rstrip().split())))

result=arrayManipulation(n, queries)

not sure why, but when I run your code as it is I get an error: if((y)<=len(list)): list[y] -= incr; IndexError: list index out of range

but when I do run that line like this:

if((y)<=len(list)): list[y-1] -= incr;

that works

A bit less efficient, but more readable

Python 3 more clear code

can you explain your logic ??

Thank you. This is clear.

You could also find the max using:

`max(accumulate(my_array))`

See below:

However, I have not understood the theory behind the

difference array algorithm, why it works the way it works and how to derive it.Brilliant man, mine was working for initial test cases but getting timeout for rest.

Thanks , max(list) wil be simpler

can the same be written like this: def arrayManipulation(n, queries): arr_n=[0]*n for i in range(len(queries)): n1=queries[i][0] n2=queries[i][1] for j in range(n1-1,n2): arr_n[j]=arr_n[j]+queries[i][2] return max(arr_n) This is giving me a tiemout error while submitting. can u assist here?

yeah,at the beginning, l got the same problem as well. This algorithm's complexity could be o(n). Try to learn something about prefix sum array.I hope this can help.

I still have some doubt if anyone could explain it. I understand that it is making use of difference array to keep track of the difference between items rather than updating every item.

However as I understand, size of difference array is one less than total items in the actual array.

So as per the demo program given,

However the logic used seems to be a variant of difference array that I am not able to understand. It would be great if someone could help me connect the dots from this difference array to the actual working solution of this problem. Thanks.

Hello, I don't really get your DIFF representation, but here is the deal:

you need to keep in mind that at the end of queries to get the real value of i we need to sum the values of A[0]->A[i].

for a query (l, r, x) if we add x to A[l] then we're sure later for every k in [l, r] sums(0->k) will include x.

the problem is that every k > r will also include that x, therefore we'll decrement l[r+1] by x.

Now the sum through 0 -> k will include x only if k >= l and will exclude it only if k > r which is equivalent to:

sum(0->k) will consider x only if k is in [l, r]

I think the DIFF matrix should be:

then x is 100+100+100-100-100 = 200

still don't quite get it though

I think the Diff should like this

so finally, 1st col is always the real value, and others are accumlated of previous values and it self. so actual values are 100 200 200 200 100, max is 200

Thanks this helps me to understand how it works.

@julie_larson

100+100+100-100-100 = 100 still not 200 I've been banging my head still not able to understand this solution.

The final diff array should be like this:

100 100 0 0 -100 (straight foward from the code)

So when you iterate over it to get the accumalated sum you'll get this:

The maximum value of the accumulated sum is 200.

They're always checking the sum against the count, so when the sum is less than the count (which is the greatest sum so far) the count doesn't update.

As i have understood (5 , 3) 0 0 0 0 0 (1 , 2) 100 100 0 0 0 -> first and second places i.e a=1,b=2 , k=100, now a+k = 0+100 = 100, b+K = 0+100 = 100. (2 , 5) now from 2 to 5 i.e 2,3,4,5 are added with K i.e 100. already 2=100 now 2 becomes 100+100 =200, simialrly 3 = 0+100=100,4=0+100=100,5=0+100=100. (3 , 4) now 3 and 4 are added with 100. ie 3 value is 100 it becomes 100+100=200, 4 becomes 100+100=200.

among these 200 is max value.

instead of writing long int *a=long int[n+1] if I write long int a[n+1]; It shows segmentation fault after test case 7. why? Explain please.

yes ,the same with you, i am confused

you aren't allocating space for

athat way. He usesnewto create an array on the heap. You are trying to declare it on the stack, but you can't do that with a dynamic value like 'n'As per my knowledge, u can create an array to size upto 10^6 in stack and for size above it we need to create in heap so we do it dynamically. https://discuss.codechef.com/questions/28604/maximum-size-of-an-array refer this

Thanks @ami3443

for me the best explanation for the dynamic allocation was:-here!

Nice explanation.

If you have a problem understanding dynamic memory then make use of vector . It allocates memory dynamically wherein the user doesn't have to deal with pointers .

vector arr(n); declares an array of long int of length n.

Thanks for explaining the logic behind this.

Here ,I add all the positive values of the difference array to get the maximum element . But , the answer comes out to be wrong for all the test cases except sample one ...

Use long int in place of int.

what do u mean by previous element? is it a[p-1]for a[p] or the previous state of a[p] before the current updation operation? difference is betweentwo succesive elements or in the same element before and after one query is executed?

It is a[p-1] for a[p] ie. the difference between two successive elements.

Well ,now ,i understood my mistake . I was just adding the positive differences. But the problem requires maximum element in an array , so there must be a comparison while adding the differences.

Well thanks!

wonderful explaination...Thanks a lot

Hi gabriel

how is element at b+1 the previous element?

Your Explanation is wrong and misleading.Logic behind @ amansbhandari algorithm is at any index p he is storing by how much this value is more than previous value, subsequently if value from p to q is 100(to be exact 100 more than other values) q+1 should be 100 less than values between p and q.That is why we subtract 100 at q+1 index of array.

That's it. Thanks for a simpler explanation.

The solution works, but how did you came to this theory ?

That's what I understand this theory. We can try to understand this logic like we imagine Supermario walking on a N width horiz line. a and b is the point on the line, k is the mushroom Mario like to eat. When Mario go to the point at a,he eat the k size mushroom and become taller,after he have walked through point b, his height reverse to the origin height before he eat the mushroom. eg. 1. When Mario is walking to a, he eat a k size mushroom, and become k bigger 2. Then Mario is walking to a', he eat a k' size mush, and become k' bigger, now Mario's height is (k + k') 3. If Mario have walked to b, so he pooped out the mushroom and become k smaller, the only way that he can become larger is to meet a new (a,b) point and eat a new k size mushroom 4. The rest can be done in the same manner.

awesome explanation.. btw i wanted to ask if this is what we call segment tree..and if we can use this method to solve questions with the segment tree tags.. P.S. : I have a very little knowledge about the segment trees.

Thanks in advance.

you can refer top coder or either gog to understand the concept of segment tree. ;)

acha bhai :D

haha.. ;)

This is literally the only reason I actually was able to understand the logic of the code. Thank you for that, seriously.

Very nice explanation. The explanation in the question does misleading on how to implement the solution.

Thanks a lot for your explanation, it really simplified the problem. :)

ahaha great explanation, thanks so much!

The only explanation I understood

i dont get why did you subtract from q+1th element?

sorry dear ,I dont get it .Plz tell me, how do you think about this logicc....

Check your code with this inputs

i/p:7 2 1 5 100 2 3 500here we are adding value only in a[p] but we have to add value from a[p] to a[q] .and what is the requirement of a[q+1] here????? plz clear my doubt ...

how you thought this ?????

why are we substracting from q+1? anyway how one can think to this level?

Why is my code not working on the same approach ? Please help Can't find anything wrong !

## include

## include

using namespace std;

int main(){

return 0; }

keep an eye on edges.

Still No Clue!

Try to change

to

That Made it Worse

I got the catch! I wasn't declaring x and ans long long instead they were of type INT and overflowing Thanks for Help Anyway :)

We can try to understand this logic like we imagine Supermario walking on a N width horiz line. a and b is the point on the line, k is the mushroom Mario always like to eat. When Mario go to the point at a,he eat the k size mushroom and become taller,after he have walked through point b, his height reverse to the origin height before he eat the mushroom. eg. 1. When Mario is walking to a, he eat a k size mushroom, and become k bigger 2. Then Mario is walking to a', he eat a k' size mush, and become k' bigger, now Mario's height is (k + k') 3. If Mario have walked to b, so he pooped out the mushroom and become k smaller, the only way that he can become larger is to meet a new (a,b) point and eat a new k size mushroom 4. The rest can be done in the same manner.

Best explanation, thanks.

thanks a lot bro this is best explanation i found of this problem.

here we are taking the difference of highest number and lowest number that is the loging has been implemented here. you could see in the peice of code to finding max value at each iteration adding the next element to the value (x=x + a[i]).

It took me a while to understand as well, but its pretty brilliant actually. First let me explain why this approach is good: You have k operations acting on a range of [a,b], for each of these k operations, a could be 1 and b = n , that makes a normal (add sum to 'a' through 'b') solution O(k * n ).

In this solution for each of the k operations, you make exactly 2 operations, so its constant time for each k operation. At the end, you go through the entire n length array and get the largest. That makes it a O(k) + O(n) operation ==> much cheaper

Now, on to the solution itself, assume the array size, n = 10 lets take operations to be(lowerIndex upperIndex sumToBeAdded): oper1: 1 5 3 oper2: 4 8 7 oper3: 6 9 1

initially your array looks like (array of size n + 1): 00000000000

after 1 5 3 : 0 3 0 0 0 0 -3 0 0 0 0

after 4 8 7 : 0 3 0 0 7 0 -3 0 0 -7 0

after 6 9 1 : 0 3 0 0 7 0 -2 0 0 -7 -1

so, that is O(k) where we processed the array, now for the magic... as we iterate through the n elements, keep adding a running sum, the running sum at each index will give you the final value that was supposed to be at that index (had you added the oper's sum to 'a' through 'b' for each of the k operations...)

on filling all elements of array[n+1] with the running sum and noting the largest, the array transforms to : 0 3 3 3 10 10 8 8 8 1 0 , and this happends in O(n) time

and the largest value at any index is 10

Hope this makes it easier to understand...

Best explanation. Thank you!

Good Explanation

But i have doubt..

consider a logic where you add value to all elements from p to q

after 1 5 3: 0 3 3 3 3 3 0 0 0 0 after 4 8 7: 0 3 3 3 10 10 10 10 10 0

At this step, largest element is 10 But as per your logic largest element is 7

can you explain please?

I understand this works but I didn't get "that makes a normal (add sum to 'a' through 'b') solution O(k * n )."

It would be of immense help If you could help

You can also visualize this by thinking that

`a[p]`

denotes the starting point of an uprising in value and`a[q+1]`

denotes the end point. In this case, traverse through the array is like climbing a mountain, and the sum we keep denotes the elevation.Agree. Although I used segmented tree, it was no need to know max on each step. Amansbhandari in fact used dirac delta and theta functions instead.

Does using segment tree worked?

Did you get all AC?

I usedlazy propogation , worked fine.

I too tried Lazy Propagation but got segmentation fault after 6 test cases, even the Question Setter in the editorial says that Lazy Propagation can not pass all test cases. Please show the code you wrote which passed all the test cases.

https://github.com/MJjainam/CodeJam/blob/master/Crush/crush.java

Thank you.

I got AC using Segment tree with lazy propagation. http://ideone.com/DzZlW7. Just keep on updating the tree, and at each node store the maximum of its left and right child. And after all the k updates, apply Range maximum query.

Just noticed your comment. I came to the same conclusion here

brilliant mind ....

thanks

thanks

instead of long int *a=long int[n+1] if we write long int a[n+1]; It shows segmentation fault.why?

because 'n' is too large to allocate for static array. (the maximum size of static array is different by complier). so we allocate dynamic array of size 'n+1'.

What a approach. Not easy to think this kind of approach.

Please explain it to me in the simplest form you can

you mean O(n+k). nice solving

any comments on to improve this pthon code to use greedy algorithm I time out for the later cases. Thanks

N, M = map(int,raw_input().split()) lst = [0]*N

for _ in range(M): a, b, k = [int(n) for n in raw_input().split(" ")]

print max(lst)

you should create a generator because when the test it have big number of queries your program delay too much.

I tried this, but it still could not make it past Test 5, the rest timed out

A generator doesn't buy anything. Test 7 - end still fail due to timeout.

This will do the same thing and still fail due to timeout.

Implementing the C++ solution from the top level comment in Python 2.7 can be done as this ( changing out a few bits that don't make sense ):

Same logic (thanks!) with constraits addressed.

I do not understand this approach... could you please elaborate.

pure genius!

Truely!

There is nothing greedy about this algorithm.

BTW O(n) is slower here as compared to O(MlogM). N = 1e7 (worse), M = (log(2e5)*2e5)/log(2) ~ 3.5e6 :P

Not exactly slower, if we look at the constants behind O-s. Say, we sort events, there are 4e5 of them, so we get log(4e5)*4e5/log(2)=7.44e6, the difference became not so drastic. And sort at any step uses conditional operations that, when incorrectely predicted, break the CPU conveyer. That costs about 10 ticks each time. And they would be incorrectely predicted in about 50% cases, that is expensive. The proposed approach is straightforward, the only conditional is "if ( max < x ) max = x" that probably would be saturated fast, that is in most cases it would not be taken, and CPU would be able to predict that.

About numbers: my sorting approach runs in 0.01-0.02s, this approach in my implementation runs in 0.03-0.04s on strong testcases. That is probably because we have to use quite a lot of (random access) memory, 80MB instead of 3.2MB in the sorting approach, and it leads to cache misses and TLB trashing. HugeTLB could help a bit, had it been turned on on the testing server.

Seriously Brilliant approach. Really appreciate it.

awesome.........

Great solution!

I don't think I could ever have come up with something like that!

Is this considered a greedy solution?

One thing I did change was to make the array size N+2 and skipped the bounds check.

Yes, N+2 is required, otherwise gives an out of bounds error!

Surely that's O(N) space. There's no need to store the array itself. Just record the update boundaries along with the k value (-k for the end boundary), sort them by location (then by value if at the same location), then scan over them with a running total.

Yes, that makes more sense and saves on memory and running time. Using a defaultdict in Python:

it is great that we don't have to store every key.

The above code is showing runtime error for test case 7 onwards. please suggest the reason?

I experience the same issue. If I run test case 13 locally, my code passes, but if I try the same code remotely on HR, cases 7 -> 13 all fail. Out of memory ?

why deleted :(

I too tried the same approach. Yes, It's giving runtime error.

Brilliant. It seems like the runtime error has since been fixed.

That is awesome man!

Great Approach, man! :D

Wanna know something! Is there any classic name of this approach? Can anyone give some links to other problems which is similar to this problem? I think, I've seen this type of problem before, but can't remember where and couldn't solve then also!

Very elegant ! I am totally speechless. Thank you. For those who are still confused or not quite understand, please the link http://codereview.stackexchange.com/questions/95755/algorithmic-crush-problem-hitting-timeout-errors

This code finds the maximum possible subarray sum. and the maximum sum is the answer. This means that we assume that atleast 1 element in the array will be 0. Is that necessary??

awesome!!

Can any one explain why static allocation gives segmentation fault in some cases?

Wouldnt have came up with the idea, I was using partitions..., although I didnt actually see code the explanations below were enough to make a light bulb pop!

I tried using an integer vector with the same approach. The only difference being vector int a(n+1); instead of long int *a=new long intN+1;

It did not work. Wrong answer on TCs 5 to last. The same happened on using long int vector instead of int. Could somebody enlighten me as to why?

int vs long int?, overflow then

No, I used vectors of both int and long int and they both didn't work. The dynamic array worked.

Yeah,the same happened to me. Dint get it.

wrong logic maybe, the answer at the top doesnt let things grow too big if possible though

No, the logic couldn't have been the problem since I changed nothing in the code but that line and it immediately worked.

did u figure it out?

great one.I never comment but this code and your approach made me do so.Really was awsomely done..

Very very nice code. I wrote a low efficient segment tree and get time limit for some test cases. Your solution just enlighten me a lot.

Simply amazing..... Your answer put the Editorial's to shame......

Absolute Awesomeness.

Did it pass all test cases?

you can try it, it passes.

I came out with the same approach in java, but code is ridiculously larger :P

You might want to try replacing

`List<Long>[]`

with`long[]`

. There's no reason to build all of those arraylists and aggregate them later.sounds good, thx

I also did it on Java. At first, it only passed up to test 3, due some precision loss, having int k instead of long k. This may be obvious to many here, but I still thought it was interesting to see how such a small detail changes it all. Here is the code (in comments, the code with int, which fails after test 3).

import java.io.

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

}

Can you explain this line

differenceArray[a] += k; if (b+1<=N) differenceArray [b+1] -= k; }

Why are you adding k to only differenceArray[a]??

Let's view the array as a list of histograms. Each position in the array has a histogram with a certain variable heigth. It would be cumbersome to keep track of the heigth of every single histogram. Instead, you could just keep track of how much the height of a given histogram differs from the one preceding it (in a continuous setting, this would mean to keep track of the derivative of a function, not the function itself).

Here, we know there is an increment of k for the height of the histogram in position a (a positive slope of k from a-1 to a), but then the height remains constant at positions a+1, a+2,...,b. Then again, we know that position b was the last position where histograms were incremented by k, so there is a decrement of -k at position b+1 (negative slope of -k from b to b+1).

Hope this helps.

you can check it out in the assumptions area. if int values can be more than 2**30 or you can have many accumulated in one int. etc..

urgh! finally I was able to understand this damned problem! thanks for your explanation @hl2kerg!

Thank you so much, I too was stuck for that small reason for hours together!! Thaks allot;)

nice

same thing happened to me ..using int instead of long

Awesome solution, but it's worth pointing out that this is O(n) auxillary space, not O(1)

Nice algorithm. However I'd prefer if you described your approach, rather than posting your code. (This would also avoid people asking "can you explain your logic".) Leave the coding as an excercise for the reader :)

I ended up using a TreeMap. Since there can only be 400K inflection points max, it seemed wasteful to create an array of 10M values and then traverse the 10M values to compute a result. So this results in a time of O(M log M). As others have mentioned, the additional constant time is much higher than

`long[]`

, so it's hard to estimate the actual performance difference. This would really win if M was small (and N large), and is time/space independent of N. (The code reads and discards N.)Your solution is O(n+m) runtime and O(n) space complexity, which is slower than what you mentioned in your post, but is still great. The O(n+m) is a result of the fact that

mmay be larger thann. The space complexity is due to you creating an array of sizen.I do the same in my efficient Java solution.

HackerRank solutions.

The runtime complexity is O(N) because M upper bound (2 * 10^5) is lower than N upper bound and even if it was equal (M upper bound = N upper bound), it would be O(N+N), which is O(2N), which could be reduced to O(N).

I usually analyze runtimes assuming variables are unbounded. I find it to be more useful that way since HackerRank usually creates arbitrary bounds for variables.

In the bounded case, you are correct, you can consider it to be O(N).

HackerRank solutions.

Only O(M) space is needed. The question was tagged "sparse arrays" but this is a brute-force, dense array.

`if((q+1)<=N)`

is unnecessary because`[N+1]`

space is allocated.Sorry, but this is just bruteforce. Your code runs in O(n), but the input is O(M). By creating the array in code (which is not part of the input) you are using exponential memory and runtime (because the length of N is logarithmic compared to the actual length of the array).

See my anwser for a better idea about the solution.

I like how this comment correctly points out the insufficiencies of the original post using actual theoretical arguments, yet still gets downvoted massively.

Amazing solution @amansbhandari great work.

moron we are'nt suppossed to discuss solutions!

Brilliant!

Amazing! Hats off.

If the problem statement is exactly the same, and you were asked to find the minimum, you simply loop through the array using Math.min() instead of the Math.max() in the last loop in this solution.

HackerRank solutions.

The resulting array will have all M operations performed on it. We can find the max/min/mean/median/mode, whatever we want, since it's just an array of final values. I can take a look at your code (if you want to alter this solution to see why it didn't work.

HackerRank solutions.

great approach. i don't understand the logic but still approach is outstanding in terms of complexity.

Hi. Here's a detailed explanation of the logic that I wrote. My solution uses the same concept as above. Hope this helps.

HackerRank solutions.

Excellent dear. i was F***N stuck with for loops and not getting out

its genius!

Will this for case if range given is 1 5 500 1 3 500

I could understand that we are tracking start(a) and end(b) points and in between them all are sum of K. But i couldn't understand the last loop. Can anyone please explain why summing the array will work for our solution?