• + 346 comments

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

    #include <cmath>
    #include <cstdio>
    #include <vector>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    
    
    int main() {
        long int N,K,p,q,sum,i,j,max=0,x=0;
    
        cin>>N>>K;
        long int *a=new long int[N+1]();
    
        for(i=0;i<K;i++)
        {
            cin>>p>>q>>sum;
            a[p]+=sum;
            if((q+1)<=N) a[q+1]-=sum;
        }
    
        for(i=1;i<=N;i++)
        {
           x=x+a[i];
           if(max<x) max=x;
    
        }
    
        cout<<max;
        return 0;
    }
    
    • + 12 comments

      Your approach is brilliant. Hats off

      • + 11 comments

        can you please explain the logic behind that.?

        • + 15 comments

          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.

          • + 2 comments
            [deleted]
            • + 0 comments

              here is problem solution in java python c++ and c programming language. https://solution.programmingoneonone.com/2020/07/hackerrank-array-manipulation-solution.html

            • + 0 comments

              Once you understand the logic. The question will look very easy.

              Here's how I solved it in python.

              Hackerrank - Array Manipulation Solution

              My answer is O(m log m) and it is faster than O(n)

              The maximum value of n is 10**7 whereas m log m is 5*10**5

          • + 13 comments

            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

            • + 3 comments

              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.

              • + 32 comments

                Same solution translated in python -

                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)
                
                • + 4 comments

                  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 + 1
                  arr = Array.new(N + 1, 0)
                  
                  M.times do
                      # cycle through and get the inputs
                      start, finish, value = gets.chomp.split(' ').map(&:to_i)
                  
                      # increment value at start of sequence
                      arr[start - 1] += value
                  
                      # decrement value at first position after sequence
                      arr[finish] -= value
                  end
                  
                  tmp = 0
                  max = 0
                  
                  arr.each do |value|
                      # step through summing array
                      tmp += value
                  
                      # capture the max value of tmp
                      max = tmp if max < tmp
                  end
                  
                  puts max
                  
                  • + 13 comments

                    Same solution in C

                    int main() {
                        long long int n,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++){
                            long long int c,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 */
                        return 0;
                    }
                    

                    Edit 1: I had used pointers so much because I was learning about pointers at that time

                    Edit 2: Many were asking about the logic, I will try to give you the intuition The basic idea is doing lazy update,i.e., not doing actual update of range every time and instead store the net update somwhere so that it can be easily done in one go

                    Suppose we have an array 3,2,4,5,7,9,4 and we want to make update, from 0 to 2 increase value by 1 We create update arr of equal size filled with 0 . For first update, update[0]+=1 and update[3]-=1. We add where the interval begins, we subtract just after the interval ends which just helps in excluding all indices from 3 and after that from being incremented. How so? When we have to do final update, we actually sum values from left. After suming values from left(update[i]+=update[i-1]) and filling update array you would get, update = [1,1,1,0,0,0,0]. Notice that we succesfully excluded all indices from 3 and after. If we hadn't subtracted at position 3, the whole update array would have been filled with 1. Similarly we can make more range updates using same logic. Sum at each index gives the net value to be updated. Hope this helps!

                    • + 11 comments

                      Same solution in C#

                      using System;
                      using System.Collections.Generic;
                      using System.IO;
                      class Solution {
                          
                          static void Main(String[] args) {
                              
                              string[] inString = Console.ReadLine().Split(' ');
                              uint[] initParams = Array.ConvertAll(inString, UInt32.Parse);
                              uint n = initParams[0];
                              uint m = initParams[1];
                              
                              long[] numList = new long[n+1];
                              
                              for(int i=0; i<m; i++)
                              {
                                  string[] opString = Console.ReadLine().Split(' ');
                                  uint a = UInt32.Parse(opString[0]);
                                  uint b = UInt32.Parse(opString[1]);
                                  long k = long.Parse(opString[2]);
                                  
                                  numList[a] += k;
                                  if(b+1 <= n) numList[b+1] -= k;
                              }
                              
                              long tempMax = 0;
                              long max = 0;
                              for(int i=1; i<=n; i++)
                              {
                                  tempMax += numList[i]; 
                                  if(tempMax > max) max = tempMax;
                              }
                              
                              Console.WriteLine(max.ToString());
                          }
                      }
                      
                      • + 24 comments

                        Same solution in Java

                        Scanner scan = new Scanner(System.in);
                        int n = scan.nextInt();
                        int m = 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 = new long[n];
                                
                        int lower;
                        int upper;
                        long sum;
                        
                        for(int i=0;i<n;i++) arr[i]=0;
                        
                        for(int i=0;i<m;i++){
                            lower=scan.nextInt();
                            upper=scan.nextInt();
                            sum=scan.nextInt();
                            arr[lower-1]+=sum;
                            if(upper<n) arr[upper]-=sum; 
                        }
                                
                        long max=0;
                        long temp=0;
                        
                        for(int i=0;i<n;i++){
                            temp += arr[i];
                            if(temp> max) max=temp;
                        }
                        
                        System.out.println(max);
                        
                        • + 1 comment
                          [deleted]
                          • + 1 comment

                            It is the same logic as mentioned above.

                            • + 4 comments

                              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?

                              • + 3 comments

                                You can try to visualize the array as steps / stairs

                                We are just noting down the bump ups and bump downs

                                • + 3 comments

                                  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.

                                  • + 2 comments

                                    me netheir, I am looking for the maths here, I am pretty sure the solution has a math method. Somebody here wrote "Prefix sum".

                                    • + 0 comments

                                      I tried an answer in the spirit of digital signal processing here.

                                    • [deleted]
                                      + 11 comments

                                      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.

                                      • + 2 comments

                                        check it out here, you will get all your doubts solved https://www.geeksforgeeks.org/difference-array-range-update-query-o1/

                                        • + 2 comments

                                          Below link will also help to understand theory behind it. https://www.geeksforgeeks.org/constant-time-range-add-operation-array/

                                          • + 10 comments

                                            Same solution in Javascript

                                                var arr = [];
                                                var max = 0;
                                                // init each element of arr to 0
                                                for (let l = 0; l < n; l++) {
                                                    arr[l] = 0;
                                                }
                                                // for each sum operation in queries
                                                for (let i = 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 complexity
                                                    arr[queries[i][0]-1] += queries[i][2];
                                                    if (queries[i][1] < arr.length) {
                                                        arr[queries[i][1]] -= queries[i][2];
                                                    }
                                                }
                                                for (let j = 1; j < n; j++) {
                                                    arr[j] += arr[j-1];
                                                }
                                                for (let k = 0; k < arr.length; k++) {
                                                    max = Math.max(max, arr[k]);
                                                }
                                                //max = Math.max(...arr); // not working for big arrays
                                                return max;
                                            
                                            • + 1 comment

                                              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?

                                              • + 0 comments

                                                you could post your code,and we can check it out

                                            • + 3 comments

                                              simpler in es6:

                                              function arrayManipulation(n, queries) { let arr = new Array(2*n).fill(0); let max = 0;

                                              queries.forEach((item) => {
                                                  arr[item[0]] += item[2];
                                                  arr[item[1] + 1] -= item[2];
                                              });
                                              
                                              arr.reduce((prev, curr, idx) => {
                                                  const sum = prev + curr;
                                                  if (sum > max) {
                                                      max = sum;
                                                  }
                                              
                                                  return sum;
                                              })
                                              
                                              return max;
                                              

                                              }

                                              • + 1 comment

                                                I did something pretty similar, just with a little bit more readable forEach:

                                                const arr = new Array(n).fill(0);
                                                let result = 0;
                                                
                                                queries.forEach(([a, b, k]) => {
                                                    arr[a - 1] += k;
                                                    if (b < arr.length) {
                                                        arr[b] -= k;
                                                    }
                                                });
                                                
                                                arr.reduce((a, b) => {
                                                    const acc = a + b;
                                                    result = Math.max(result, acc);
                                                    return acc;
                                                }, 0);
                                                
                                                return result;
                                                
                                                • + 3 comments

                                                  This produces wrong answer in some of the tests.

                                                  • + 2 comments

                                                    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.

                                                    • + 1 comment

                                                      It is a good video. I understood the algorithm clearly.

                                                      • + 1 comment

                                                        thanks @chandraprabha90.

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

                                                        • + 2 comments

                                                          Could you add subtitles? I tried watching it but couldn't quite understand your accent through the audio

                                                          • + 0 comments

                                                            Hi Grozny,

                                                            I appologize for my bad sound quality but i am trying to improve it. but it will be very difficult to add subtitle for this video because its around half an hour which explains all the concepts in deep.

                                                            Making this long video took lot of effort and time now adding a subtitle will be very tedious without any support.

                                                            Will suggest you to try automatic transcribe feature from youtube to translate it.

                                                            Anyway thanks for watching.

                                                          • + 0 comments

                                                            Hi Grozny,

                                                            I have added subtitle for this tutorial and I hope it will you to understand logic with more clarity.

                                                    • + 1 comment
                                                      [deleted]
                                                      • + 0 comments

                                                        Nice approach you got there!

                                                  • + 0 comments

                                                    I had the same issue. my mistake was decrementing lower and upper. you don't decrement upper, the difference array needs to show it went down AFTER then last index, not within.

                                              • + 0 comments

                                                Thought to myself ....no js solutions here? then I find 3 of them, Js, ES6, readable wow.

                                            • + 0 comments

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

                                            • + 0 comments

                                              Added some ES6 syntax suger...

                                              const arrayManipulation2 = (n, queries) => {
                                                const arr = new Array(n).fill(0);
                                                let max = 0;
                                                for (let i = queries.length - 1; i >= 0; i--) {
                                                  const [a, b, k] = queries[i];
                                                  arr[a - 1] += k;
                                                  if (b < arr.length) {
                                                    arr[b] -= k;
                                                  }
                                                }
                                                for (let j = 1; j < n; j++) {
                                                  arr[j] += arr[j - 1];
                                                }
                                                for (let k = arr.length - 1; k >= 0; k--) {
                                                  max = Math.max(max, arr[k]);
                                                }
                                                return max;
                                              };
                                              
                                            • + 0 comments

                                              Got stuck because of this

                                              max = Math.max(...arr); // not working for big arrays

                                              Thanks man!

                                            • + 0 comments

                                              You could simplify your code a smidge, and save a little processing power, by removing your final for loop, and putting in an if check in the second to last loop, like this:

                                              for (let j = 1; j < n; j++) {
                                              	arr[j] += arr[j-1];
                                              	
                                              	if (arr[i] > biggest) {
                                              		biggest = arr[i];
                                              	}
                                              }
                                              
                                            • + 1 comment
                                              [deleted]
                                              • + 0 comments

                                                Perfect! Could you please explain me the thought process behind the solution?

                                            • + 0 comments

                                              My js solution ran out of time for a few test cases

                                              function arrayManipulation(n, queries) { let a = new Array(n).fill(0); for(let j = 0; j < queries.length; j++) { let temp = queries[j] let k = temp[0]; while(k <= temp[1]) { a[k-1] += temp[2]; k++; }

                                              } return Math.max.apply(Math, a); }

                                          • + 0 comments

                                            this one is the one that finally made it click for me...crazy how many different explanations are "whoosh" until the right person finds the "right" explanations.

                                            But let's keep doing standardized testing in schools /s

                                        • + 0 comments

                                          Thanks for the post, it really made me understand the logic clearly

                                      • + 0 comments

                                        Thank you @Kemal_caymaz for the explanation, I have found this very useful.

                                      • + 0 comments

                                        Thank you!

                                      • + 0 comments

                                        thnx

                                      • + 1 comment

                                        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.

                                        • + 2 comments

                                          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.

                                          • + 1 comment

                                            fantastic video, thank you!

                                            • + 0 comments

                                              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.

                                          • + 0 comments

                                            impressive ...

                                      • + 0 comments

                                        thanks bro..

                                      • + 0 comments

                                        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.

                                      • + 1 comment

                                        Thanks a lot budy for your fantastic explanation ! Your thinking is really amazing like you . Good job.

                                        • + 0 comments

                                          most welcome. It would be great, if you can provide your feedback like, dislike , comment etc. on my video. It motivate me to do more for you all

                                      • + 1 comment

                                        hey used this logic its failing for 10 test cases with large inputs

                                        • + 0 comments

                                          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.

                                      • + 0 comments

                                        Thanks, your explanation is very helpful

                                      • + 0 comments

                                        Thank you so much for clearly explaining this.

                                  • + 1 comment

                                    did you got it?

                                    • + 0 comments

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

                                  • + 0 comments

                                    How can you implement the logic with ease without understanding the logic? Copy and pasting is not the same as "implementing"

                                • + 0 comments

                                  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/

                                • + 0 comments

                                  Like piling up blocks? Adding a number -> going up one step and subtracting -> down . Finally, we count how high we can go.

                              • + 2 comments

                                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.

                                • + 0 comments

                                  you add up all the numbers > 0 in the final list, which is 100 + 100 = 200

                                • + 1 comment
                                  [deleted]
                                  • + 0 comments

                                    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.

                              • + 1 comment

                                One insight that might help is that we're keeping track of the change in values rather than the values themselves at each index. Therefore, by adding the k at a and subtracting it after b, we are saying that at a the total value increases by k compared to the previous element, and after b the total value decreases by k compared to b. Hope that helps!

                                • + 0 comments

                                  Here's the same solution in swift in case anyone needs it :).

                                  func arrayManipulation(n: Int, queries: [[Int]]) -> Int { var sums = Int: Int for query in queries { sums[query[0]] = (sums[query[0]] ?? 0) + query[2] sums[query[1] + 1] = (sums[query[1] + 1] ?? 0) - query[2] }

                                  var currentmax = 0
                                  var sum = 0
                                  sums.sorted{ `$0.0 < $`1.0 }.
                                      compactMap{ `$0.1; sum += $`0.1; currentmax = sum > currentmax ? sum : currentmax}
                                  return currentmax
                                  

                                  }

                              • + 0 comments

                                refer to prefix sum algorithm.....you'll be clear!

                        • + 1 comment

                          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 ?

                          • + 0 comments

                            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

                        • + 0 comments

                          You don't have to do this:

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

                          because long by default is 0

                        • + 2 comments

                          could you please explain me the working of the code?

                          • + 0 comments

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

                          • + 1 comment

                            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.

                            • + 0 comments

                              tnks @kanahaiya

                        • + 0 comments

                          no need to init array elements to 0 in Java

                        • + 1 comment

                          Hi, your solution works but I am not convinced!

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

                          • arr[lower-1]+=sum; This only increments the lower element by sum.
                          • if(upper
                          • arr[upper]-=sum; I don't understand why are you substructing sum!

                          Can you please explain? Thanks.

                          • + 1 comment

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

                            • + 0 comments

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

                        • + 1 comment

                          Using Java 8 syntaxis:

                          public static void main(String[] args) {
                           Scanner in = new Scanner(System.in);
                           int n = in.nextInt();
                           int m = in.nextInt();
                           long[] output = new long[n];
                           IntStream.range(0,m).forEach(i -> { int a = in.nextInt()-1;
                                                              int b = in.nextInt();
                                                              int k = in.nextInt();
                                                              output[a] += k;
                                                              if(b < n) output[b] -= k; });
                           AtomicLong sum = new AtomicLong(0);
                           System.out.print(LongStream.of(output).map(sum::addAndGet)
                                                                 .max().getAsLong());
                           in.close();
                          }
                          
                          • + 2 comments

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

                            • + 0 comments

                              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.

                            • + 1 comment

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

                              • + 0 comments

                                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.

                        • + 0 comments

                          why temp += arr[i];

                        • + 0 comments

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

                        • + 0 comments

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

                        • + 0 comments

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

                        • + 0 comments

                          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.

                        • + 0 comments

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

                        • + 2 comments

                          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.
                          static long arrayManipulation(int n, int[][] queries) {
                          
                          // initialize array with 0's of size n
                          long arr[] = new long[n];
                          
                          // each successive element contains the difference between itself and previous element
                          
                          for (int i = 0; i < queries.length; i++) {
                          // when checking query, subtract 1 from both a and b since 0 indexed array
                          int a = queries[i][0] - 1;
                          int b = queries[i][1] - 1;
                          int k = queries[i][2];
                          
                          arr[a] += k;
                          if (b+1 < n) {
                          arr[b+1] -= k;  
                          }
                          }
                          
                          // track highest val seen so far as we go
                          long max = Long.MIN_VALUE;
                          for (int i = 1; i < arr.length; i++) {
                          arr[i] += arr[i-1];
                          max = Math.max(arr[i], max);
                          }
                          
                          return max;
                          }
                          
                          • + 0 comments

                            Probably just for readability.

                          • + 0 comments

                            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.

                        • + 1 comment

                          Same solution in Golang

                          func arrayManipulation(n int32, qs [][]int32) int64 {
                          	a := make([]int64, n + 1)
                          	qLen := len(qs)
                          	for i:=0; i<qLen; i++ {
                          		p := int(qs[i][0])
                          		q := qs[i][1]
                          		sum := int64(qs[i][2])
                          		a[p] += sum
                          		if((q + 1) <= n) {
                          			a[q + 1] -= sum
                          		}
                          	}
                          
                          	var x, max int64 = 0, 0
                          	for i:=1; i<=int(n); i++ {
                          		x += a[i]
                          		if max < x {
                          			max = x
                          		}
                          	}
                          
                          	return max
                          }
                          

                          Clever solution!

                          • + 2 comments

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

                            func arrayManipulation(n int32, queries [][]int32) int64 {
                                a := make([]int64, n + 1)
                                qLen := len(qs)
                                for i:=0; i<qLen; i++ {
                                    p := int(qs[i][0])
                                    q := qs[i][1]
                                    sum := int64(qs[i][2])
                                    a[p] += sum
                                    if((q + 1) <= n) {
                                        a[q + 1] -= sum
                                    }
                                }
                            
                                var x, max int64 = 0, 0
                                for i:=1; i<=int(n); i++ {
                                    x += a[i]
                                    if max < x {
                                        max = x
                                    }
                                }
                            
                                return max
                            
                            }
                            
                            • + 0 comments

                              Wrong name in first line:

                              func arrayManipulation(n int32, queries [][]int32) int64 {

                              }

                            • + 0 comments

                              why it is a[q + 1] -= sum, it should be a[q + 1] += sum, right????

                        • + 3 comments

                          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 {

                          // Complete the arrayManipulation function below.
                          static long arrayManipulation(int n, int[][] queries) {
                            int[] arr = new int[n];
                            for(int i=0;i<n;i++){
                              arr[i] = 0;
                            }
                            int m = queries.length;
                            for(int i=0;i<m;i++){
                              for(int j=queries[i][0]-1;j<queries[i][1];j++){
                                arr[j] += queries[i][2];
                              }
                            }
                            int max = arr[0];
                            for(int i=1;i<n;i++){
                              if(arr[i]>max){
                                max = arr[i];
                              }
                            }
                            return(max);
                          
                          
                          
                          
                          
                          
                          
                          
                          }
                          
                          private static final Scanner scanner = new Scanner(System.in);
                          
                          public static void main(String[] args) throws IOException {
                              BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
                          
                              String[] nm = scanner.nextLine().split(" ");
                          
                              int n = Integer.parseInt(nm[0]);
                          
                              int m = Integer.parseInt(nm[1]);
                          
                              int[][] queries = new int[m][3];
                          
                              for (int i = 0; i < m; i++) {
                                  String[] queriesRowItems = scanner.nextLine().split(" ");
                                  scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
                          
                                  for (int j = 0; j < 3; j++) {
                                      int queriesItem = Integer.parseInt(queriesRowItems[j]);
                                      queries[i][j] = queriesItem;
                                  }
                              }
                          
                              long result = arrayManipulation(n, queries);
                          
                              bufferedWriter.write(String.valueOf(result));
                              bufferedWriter.newLine();
                          
                              bufferedWriter.close();
                          
                              scanner.close();
                          }
                          

                          }

                          What is wrong with this code. Please help.

                          • + 0 comments

                            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

                          • + 2 comments

                            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.

                            • + 1 comment

                              your video is helpful

                              • + 1 comment

                                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.

                                • + 1 comment

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

                                  • + 0 comments

                                    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.

                            • + 0 comments

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

                          • + 0 comments

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

                        • + 0 comments

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

                        • + 0 comments

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

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

                        • + 0 comments

                          Thanks for the enlightenment.

                          Here is the same solution in Swift:

                          func arrayManipulation(n: Int, queries: [[Int]]) -> Int {
                          
                              var numbers = Array(repeating: 0, count: n + 1)
                              var ans = 0
                          
                              for i in 0 ..< queries.count {
                                  var a = queries[i][0]
                                  var b1 = queries[i][1] + 1
                                  var k = queries[i][2]
                          
                                  numbers[a] += k
                                  
                                  if b1 <= n {
                                      numbers[b1] -= k
                                  }
                              }
                          
                              for i in 1...n {
                                  numbers[i] += numbers[i - 1]
                          				
                                  if numbers[i] > ans {
                                      ans = numbers[i]
                                  }
                              }
                          		
                              return ans
                          }
                          
                        • + 0 comments

                          I think

                          for(int i=0;i

                          is not needed.

                        • + 1 comment
                          [deleted]
                      • + 2 comments

                        Same solution in javascript

                        function main() {
                            let n_temp = readLine().split(' ');
                            let n = parseInt(n_temp[0]);
                            let m = parseInt(n_temp[1]);
                            let res = [];
                            let sum = 0;
                            let max = 0;
                        
                            for (let i = 0; i<n; i++) {
                                res[i] = 0;
                            }
                            
                            for(var a0 = 0; a0 < m; a0++){
                                var a_temp = readLine().split(' ');
                                var a = parseInt(a_temp[0]);
                                var b = parseInt(a_temp[1]);
                                var k = parseInt(a_temp[2]);
                        
                                res[a-1] += k;
                                if (b<n) res[b]-=k;
                            }
                          
                            for (let i=0; i<n; i++) {
                                sum += res[i];
                                if (max < sum) max = sum;
                            }
                           
                            console.log(max);
                        }
                        
                        • + 4 comments

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

                          Compilation Successful
                          Input (stdin)
                          5 1
                          1 2 100
                          Your Output (stdout)
                          Slope List [ 100, 0, -100, 0, 0 ]
                          Actual List[100,100,0,0,0]
                          
                          Compilation Successful
                          Input (stdin)
                          5 2
                          1 2 100
                          2 5 100
                          Your Output (stdout)
                          Slope List [ 100, 100, -100, 0, 0 ]
                          Actual List[100,200,100,100,100]
                          
                          
                          Compilation Successful
                          Input (stdin)
                          5 3
                          1 2 100
                          2 5 100
                          3 4 100
                          Your Output (stdout)
                          Slope List [ 100, 100, 0, 0, -100 ]
                          Actual List[100,200,200,200,100]
                          
                          • + 2 comments
                            process.stdin.resume();
                            process.stdin.setEncoding('ascii');
                            
                            var input_stdin = "";
                            var input_stdin_array = "";
                            var input_currentline = 0;
                            
                            process.stdin.on('data', function (data) {
                                input_stdin += data;
                            });
                            
                            process.stdin.on('end', function () {
                                input_stdin_array = input_stdin.split("\n");
                                main();
                            });
                            
                            function readLine() {
                                return input_stdin_array[input_currentline++];
                            }
                            
                            /////////////// ignore above this line ////////////////////
                            
                            function main() {
                                var n_temp = readLine().split(' ');
                                var listSize = parseInt(n_temp[0]);
                                var lineNumber = parseInt(n_temp[1]);
                                let slopList = new Array();
                                for(let i = 0;i < listSize;i++){
                                    slopList.push(0);
                                }
                            
                                for(var a0 = 0; a0 < lineNumber; a0++){
                                    var a_temp = readLine().split(' ');
                            
                                    const beginElementPos = parseInt(a_temp[0]);
                                    const endElementPos = parseInt(a_temp[1]);
                                    const addValue = parseInt(a_temp[2]);
                                    slopList[beginElementPos-1] += addValue;
                                    if (endElementPos<listSize){
                                      slopList[endElementPos]-=addValue;
                                    }
                                }
                                let actualList = new Array();
                                let sum = 0;
                                for (let i=0; i<listSize; i++) {
                                    sum += slopList[i];
                                    actualList.push(sum);
                                }
                            
                               let max =  actualList.reduce((acc,val)=>{
                            
                                    return (acc>val)?acc:val;
                                },0);
                                console.log(max);
                            
                            }
                            
                            • + 5 comments

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

                              image

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

                              • + 1 comment
                                [deleted]
                              • + 0 comments

                                Thanks a lot!!That really helped!

                              • + 2 comments

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

                                • + 0 comments

                                  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.

                                • + 1 comment

                                  Hi,

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

                                  https://youtu.be/hDhf04AJIRs

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

                                  • + 1 comment

                                    I've add it to my playlist

                                    • + 0 comments

                                      haha..thank you.

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

                              • + 3 comments

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

                                • + 0 comments

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

                                • + 0 comments

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

                                • + 0 comments

                                  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.

                              • + 1 comment

                                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.

                                • + 0 comments

                                  can you explain ? :)

                            • + 0 comments

                              Very well explained (Y)

                          • + 0 comments

                            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

                          • + 0 comments

                            brilliant idea!

                          • + 1 comment

                            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.

                            • + 0 comments

                              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.

                        • + 0 comments

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

                      • + 3 comments

                        How is your method faster than the following?

                        using System;
                        using System.Collections.Generic;
                        using System.IO;
                        using System.Linq;
                        using System.Numerics;
                        
                        class Solution {
                        
                            static void Main(String[] args) {
                                string[] tokens_n = Console.ReadLine().Split(' ');
                                int n = Convert.ToInt32(tokens_n[0]);
                                int m = Convert.ToInt32(tokens_n[1]);
                                
                                // Instantiate and populate an array of size N
                                BigInteger[] arr = new BigInteger[n];
                                for(int i = 0; i < n; i++)
                                    arr[i] = 0; 
                                
                                for(int a0 = 0; a0 < m; a0++){
                                    string[] tokens_a = Console.ReadLine().Split(' ');
                                    int a = Convert.ToInt32(tokens_a[0]);
                                    int b = Convert.ToInt32(tokens_a[1]);
                                    int k = Convert.ToInt32(tokens_a[2]);
                                    
                                    // Apply operation
                                    for(int j = a-1; j < b; j++)
                                        arr[j] += k; 
                                }
                                
                                Console.WriteLine(arr.Max(i=>i));
                            }
                        }
                        
                        • + 0 comments

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

                        • + 1 comment

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

                          • + 0 comments

                            your database is int? some tests data is too big

                        • + 1 comment

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

                          • + 1 comment

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

                            • + 1 comment

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

                              • + 0 comments

                                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.

                      • + 0 comments

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

                        Why we are substracting?

                      • + 0 comments

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

                      • + 0 comments

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

                      • + 0 comments
                        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()
                        
                      • + 0 comments

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

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

                        In the last for, i should be initialized to 0, not 1

                    • + 1 comment

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

                          please explain what's going on here.
                      
                      • + 0 comments

                        This is a very elegant and beautiful solution.

                    • + 1 comment

                      could you please explain me the logic?

                      • + 1 comment

                        Hi,

                        Most of the peope solved this problem but time complexity of your 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. 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.

                        • + 0 comments

                          Thanks, that helped understanding the optimization.

                    • + 1 comment

                      pls explain logic

                      • + 0 comments

                        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.

                    • + 1 comment
                      [deleted]
                      • + 0 comments

                        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 passed all test cases.

                        https://youtu.be/hDhf04AJIRs

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

                    • + 0 comments

                      Will fail if max result is negative

                    • + 1 comment

                      i cant pass some test cases, those with very long inputs, i dont know what to do! here is my code: -

                      long arrayManipulation(long long int n, vector> queries) {

                      vector<long long int> v;
                      vector<long long int>v2;
                      long long int max;
                      
                      for(long long int i=0;i<n;i++){
                          v.push_back(0);
                      }
                      for(long long int i=0;i<queries.size();i++){
                      
                          for(long long int j=0;j<queries[i].size();j++){
                              v2.push_back(queries[i][j]);
                          }
                      
                         for(long long int k=(v2[0]-1);k<v2[1];k++){
                             if(v[k]!=0){
                                 v[k]+=v2[2];
                             }
                             else{
                                 v[k]=v2[2];
                             }
                          }
                          v2.pop_back();
                          v2.pop_back();
                          v2.pop_back();
                      }
                      
                      max=*max_element(v.begin(), v.end());
                      return max;
                      

                      }

                      • + 0 comments

                        hi,

                        I am sure this comment will definately help you.

                        https://www.hackerrank.com/challenges/crush/forum/comments/570284

                    • + 0 comments

                      No need to explicitly assign 0 to every item in the array. malloc() does that automatically.

                    • + 1 comment

                      calloc would be faster i guess instead of malloc + zeroing the mem

                      • + 1 comment

                        Could you explain more, please?

                        • + 1 comment

                          in the code there are two steps to acquire a new array filled with zeroes:

                          1. At first step the allocation itself: int *a=(int )malloc(sizeof(int)(n+1));
                          2. Second step is to propagate zero values using for-loop upon newly created array.

                          In my opinion, we can do the same with single call of "calloc". It supposed to be faster in theory, cause calloc is hardware dependent and probably we don't have to loop over N items again just for get them zero valued, since calloc could know is it actually required or not, so on some harware it could be already zeroes or hardware knows better how to zero during allocation faster

                          • + 0 comments

                            okay thanks for the information!

                    • + 0 comments

                      Can you please explain this code to me

                  • + 0 comments

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

                  • + 0 comments

                    And you can easily make solution "sparse" to conserve memory on big arrays, just replace

                    arr = Array.new(N + 1, 0)

                    with

                    arr = Hash.new(0)

                    and

                    arr.each do |value|

                    with

                    1.upto(N) do |n| value = arr[n]

                  • + 0 comments

                    Here, an easiest way to understand in ruby, at least for me.

                    def arrayManipulation(n, queries)
                        arr = Array.new(n + 1, 0)
                        queries.each do |q|
                            arr[q.first - 1] += q.last
                            arr[q[1]] -= q.last
                        end
                        tmp = 0
                        max = 0
                        arr.each do |n|
                            tmp += n
                            max = tmp if tmp > max
                        end
                        max
                    end
                    
                • + 1 comment

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

                  • + 1 comment

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

                    • + 1 comment

                      You are not answering the question.

                      • + 1 comment

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

                        • + 1 comment

                          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

                          arrayManipulation(40,[[19, 28, 419],
                          [4, 23, 680],
                          [5, 6, 907],
                          [19, 33, 582],
                          [5, 9, 880],
                          [10, 13, 438],
                          [21, 39, 294],
                          [13, 18, 678],
                          [12, 26, 528],
                          [15, 30, 261],
                          [8, 9, 48],
                          [21, 23, 131],
                          [20, 21, 7],
                          [13, 40, 65],
                          [13, 23, 901],
                          [15, 15, 914],
                          [14, 35, 704],
                          [20, 39, 522],
                          [10, 18, 379],
                          [16, 27, 8],
                          [25, 40, 536],
                          [5, 9, 190],
                          [17, 20, 809],
                          [8, 20, 453],
                          [22, 37, 298],
                          [19, 37, 112],
                          [2, 5, 186],
                          [21, 29, 184],
                          [23, 30, 625],
                          [2, 8, 960]])
                          

                          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

                          • + 2 comments

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

                            • + 2 comments

                              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.

                              • + 0 comments

                                Thank you for your detailed explanation. It helped!

                              • + 0 comments

                                Because we want each value to represent how much greater/less than it is from the previous-index value.

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

                            • + 0 comments

                              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.

                • + 1 comment

                  I would not suggest eclipsing list

                  • + 2 comments

                    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;
                    

                    }

                    • + 1 comment

                      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

                      • + 0 comments

                        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.

                    • + 0 comments

                      use long instead of int.

                • + 1 comment

                  Hi Vineet could u explain what logic have you followed?

                  • + 0 comments

                    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.

                • + 5 comments

                  Same solution but optimized:

                  from itertools import accumulate
                  
                  n, m = map(int, input().split(' '))
                  dx = [0] * (n + 1) # allow run past end
                  
                  for _ in range(m):
                      a, b, c = map(int, input().split(' '))
                      dx[a - 1] += c
                      dx[b] -= c
                  
                  print(max(accumulate(dx)))
                  
                  • + 0 comments

                    That's so good! You are awesome!

                  • + 1 comment

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

                    • + 0 comments

                      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.

                  • + 1 comment

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

                    • + 0 comments

                      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

                  • + 0 comments

                    The use of accumulate is so brilliant!

                  • + 0 comments

                    Nice

                • + 0 comments

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

                • + 0 comments

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

                • + 0 comments

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

                  P.S - Talking about the python version

                • + 0 comments

                  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

                  if __name__ == "__main__":
                      n, m = [int(n) for n in input().split()]
                      l = [0]*(n+1)
                      for _ in range(m):
                          a, b, k = [int(n) for n in input().split()]
                          l[a-1] += k
                          l[b] -= k;
                      max = a = 0
                      for i in l:
                         a+=i;
                         if max<a:
                              max=a;
                      print(max)
                  
                • + 0 comments

                  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.

                • + 0 comments

                  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)

                • + 0 comments

                  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

                • + 0 comments

                  A bit less efficient, but more readable

                  def arrayManipulation(n, queries):
                      a = [0] * (n + 1)
                      for q in queries:
                          a[q[0] - 1] += q[2]
                          a[q[1]] -= q[2]
                  
                      for i in range(1, len(a)):
                          a[i] += a[i-1]
                  
                      return max(a)
                  
                • + 3 comments

                  Python 3 more clear code

                  def arrayManipulation(n, queries):
                      
                      my_array = [0] * (n+1)
                      count = 0
                      temp = 0
                      for first,last,value in queries:
                          
                          my_array[first-1] += value
                          my_array[last] -= value
                      
                      for item in my_array:
                          count += item
                          if count > temp:
                              temp = count
                         
                      return temp
                  
                  • + 2 comments

                    can you explain your logic ??

                    • + 0 comments

                      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.

                  • + 0 comments

                    Thank you. This is clear.

                    You could also find the max using: max(accumulate(my_array))

                    See below:

                    def arrayManipulation(n, queries):
                        # initialise list
                        arr = [0] * (n + 1)
                    
                        # update
                        for a, b, k in queries:
                            arr[a - 1] += k
                            arr[b] -= k
                        
                        # accumulate values
                        return max(accumulate(arr))
                    

                    However, I have not understood the theory behind the difference array algorithm, why it works the way it works and how to derive it.

                  • + 1 comment

                    can anyone debug this program

                • + 1 comment

                  Brilliant man, mine was working for initial test cases but getting timeout for rest.

                  def arrayManipulation(n, queries):
                      a = [0]*(n +1)
                      z=[]
                      for i in queries:
                          z.append(i)
                      for i in range(len(z)):
                          for j in range(int(z[i][0]),int( z[i][1])+1):
                              a[j] = a[j]+int ( z[i][2])
                      return max(a)
                  
                  • + 0 comments

                    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.

                • + 0 comments

                  Thanks , max(list) wil be simpler

                • + 1 comment

                  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?

                  • + 0 comments

                    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.

                • + 0 comments

                  But when y=len(list), list(y) will throw an error right? out of index error?

                • + 1 comment

                  Another python translation:

                  def arrayManipulation(n, queries):
                      arr = [0]*(n+2)
                      for a, b, k in queries:
                          arr[a]+=k
                          arr[b+1]-=k
                      result = acc = 0
                      for x in arr:
                          acc+=x
                          result = max(result, acc)
                      return result
                  
                  • + 0 comments

                    Brilliant!

                • + 1 comment

                  can u explain why we are subracting i dont understand the if statement ......

                  • + 0 comments

                    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 passed all test cases.

                    https://youtu.be/hDhf04AJIRs

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

                • + 0 comments

                  This breaks when y == n. The if when decrementing list[y] should be if y < len(list): list[y] -= incr. Overall great solution! Thanks for doing it in python!

                • + 0 comments

                  Excellent, but why you are using this step.. list[y] -= incr; and that "if" condition is always correct, right..! Can you explain please...

                • + 0 comments

                  for some test cases its showing teminated due to timeout what can i do

                  def arrayManipulation(n, queries):
                      a=[]
                      for i in range(n):
                          a.append(0)
                      for j in queries:
                          for k in range(j[0],j[1]+1):
                              a[k-1]=a[k-1]+j[2]
                      return (max(a))
                  
                • + 1 comment

                  these solutions give runtime error

                  • + 1 comment

                    yup for 7 testcase its showing time out what should I do??

                    • + 0 comments

                      hi,

                      I am sure this comment will definately help you to solve your problem.

                      https://www.hackerrank.com/challenges/crush/forum/comments/570284

                • + 0 comments

                  okay its great but why you using if((y)<=len(list)):

                • + 0 comments

                  Hi, I have an even simpler solution. But, I am still getting a run time error. Can anyone please help me with this. Here is my code in Python 3:

                  def arrayManipulation(arr, query): a, b, k = query[0], query[1], query[2] arr[a - 1 : b] = [arr[i] + k for i in range(a - 1, b)] return arr

                • + 0 comments

                  tq

                • + 0 comments

                  The condition check

                  if((y)<=len(list)) will always return true since len(list)==n+1 to start with and hence redundant. This condition makes more sense if len(list)==n. This code will work perfectly fine though, just pointing out in case someone is confused regarding why this condition check is there.

                • + 0 comments

                  I replaced this part of your code :

                  max = x = 0 for i in list: x=x+i; if(max

                  by this:

                  max=list1[0] for j in range(1,n): list1[j]=list1[j]+list1[j-1] if max

                  here list1 is prefix sum array why did my code failed few test cases? here's my entire code : def arrayManipulation(n, queries): list1=[0]*(n+1)

                  for i in range(len(queries)):
                      list1[queries[i][0]-1]+=queries[i][2]
                      list1[queries[i][1]]+=-queries[i][2]
                  """prefix sum"""
                  max=list1[0]
                  for j in range(1,n):
                      list1[j]=list1[j]+list1[j-1]
                      if max<list1[j]:
                          max=list1[j]
                  return(max)
                  
                  
                  
                  
                  
                  
                      if max<list1[j]:
                          max=list1[j]
                  
              • + 3 comments

                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,

                      	  ARR						DIFF
                (5,3)  0    0    0    0    0		0    0     0    0
                (1,2)  100  100  0    0    0		0    -100  0    0
                (2,5)  100  200  100  100  100		100  -100  0    0
                (3,4)  100  200  200  200  100		100  0     0    -100
                

                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.

                • + 1 comment

                  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]

                • + 3 comments

                  I think the DIFF matrix should be:

                  0    0    0    0    0
                  100  0    0    -100 0
                  0    100  0    0    0
                  0    0    100  0    -100
                  

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

                  still don't quite get it though

                  • + 1 comment

                    I think the Diff should like this

                      0   0   0   0   0 
                      100  0  -100  0    0  <--- 1 2 100, 3rd col is 100 less than 2nd col 
                      100  100 -100 0    0  <--- 2 5 100, 2nd col is 100 more than 1st col
                      100  100  0  0  -100   <--- 3 4 100, now 3rd is equal to 2nd, and 5th is 100 less than 4th col
                    

                    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

                    • + 0 comments

                      Thanks this helps me to understand how it works.

                  • + 2 comments

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

                    • + 0 comments

                      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:

                      iteration		value of x	accumulated sum
                      0			0		0
                      1			100		100
                      2			100		200	
                      3			0		200
                      4			0		200
                      5			-100		100
                      

                      The maximum value of the accumulated sum is 200.

                    • + 0 comments

                      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.

                • + 0 comments

                  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.

              • + 4 comments

                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.

                • + 0 comments

                  yes ,the same with you, i am confused

                • + 0 comments

                  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'

                • + 2 comments

                  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

                  • + 0 comments

                    Thanks @ami3443

                  • + 1 comment

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

                    • + 0 comments

                      Nice explanation.

                • + 0 comments

                  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.

            • + 0 comments

              Thanks for explaining the logic behind this.

            • + 1 comment

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

              image

              • + 0 comments

                Use long int in place of int.

            • + 1 comment

              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?

              • + 0 comments

                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!

            • + 0 comments

              wonderful explaination...Thanks a lot

            • + 0 comments

              Hi gabriel

            • + 0 comments

              how is element at b+1 the previous element?

            • + 0 comments

              Thank you ! Good to see this better way to store the difference only , so array size = n+1 only !

            • + 0 comments

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

          • + 1 comment

            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.

            • + 0 comments

              That's it. Thanks for a simpler explanation.

          • + 2 comments

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

            • + 6 comments

              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.
              
              • + 1 comment

                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.

                • + 1 comment

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

                  • + 1 comment

                    acha bhai :D

                    • + 0 comments

                      haha.. ;)

              • + 0 comments

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

              • + 0 comments

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

              • + 0 comments

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

              • + 0 comments

                ahaha great explanation, thanks so much!

              • + 0 comments

                The only explanation I understood

            • + 0 comments

              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.

          • + 0 comments

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

          • + 0 comments

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

          • + 0 comments

            Check your code with this inputs

            i/p: 7 2 1 5 100 2 3 500

          • [deleted]
            + 0 comments

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

          • + 0 comments

            how you thought this ?????

          • + 0 comments

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

          • + 0 comments

            This is really interesting! Basically the array shows the derivative of this operation by only storing the change between each value. When we sum over all the values we're effectively doing the integral of the array.

          • + 0 comments

            Way to restate what his code did without explaining anything

          • + 0 comments

            Hats off man ..for your logic !!!

        • + 14 comments

          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;
          

          return 0; }

          • + 1 comment

            keep an eye on edges.

            • + 1 comment

              Still No Clue!

              • + 1 comment

                Try to change

                for(int i=1;i<=N;i++){
                

                to

                for(int i=0;i<=N;i++){
                
                • + 1 comment

                  That Made it Worse

                  • + 2 comments

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

                    • + 0 comments

                      def arrayManipulation(n, queries):

                          a = [0]*n
                      for x in queries:
                          for i in range(x[0]-1,x[1]): a[i]+=x[2]
                      return max(a)
                      

                      I used same approach in python but it says time limit exceeded

                    • + 0 comments

                      Very useful comment. Tore my head into thinking what is hoing wrong!

          • + 0 comments

            use long x=0, ans=0 ;

          • + 0 comments

            Your variables x and ans needs to be long instead of int.

          • + 2 comments

            Change int x and ans to long

            • + 0 comments

              yeah, I get it, but the point is that as it is given in the problem, all numbers are positive so there is no reason to keep negative numbers but with this method we have to reserve extra space for sign so its not really n + constant space its n + n bits space. But I am nitpicking, this is the best solution I have seen. But if we needed unsigned long for numbers in the array because they were very large, we'd have to keep track whether number is negative or positive when we do arr[q + 1] -= sum which is not constant space

            • [deleted]
              + 0 comments

              ok thanku

          • + 1 comment

            memset your array to 0 will work

            • + 0 comments

              yes for sure

          • + 0 comments

            can you please check problem in my code too. it is giving segmentation fault in some of the test cases.

            long arrayManipulation(int n, vector> queries) { long a[n]={0};

            for(int i=0;i<queries.size();i++)
            {
                a[queries[i][0]-1]+=queries[i][2];
                if(queries[i][1]<n)
                a[queries[i][1]]-=queries[i][2];
            }
            long ans=a[0];
            for(int i=1;i<n;i++)
            {
                a[i]+=a[i-1];
                ans=max(ans,a[i]);
            }
            return ans;
            

            }

          • + 0 comments

            Convert Data Type Of Your x,ans variable to Long.

          • + 0 comments

            you have taken x,ans in int take them in long int my frnd

          • + 0 comments

            you are using integer for some variable, where the values will not fit into an integer, you need to use long for all variables.

          • + 0 comments

            I guess array's element have some default initial value other than zero and when you are adding the element to it, some wrong values get stored. You must intilialize the elements of array to zero first.

          • + 0 comments

            u need to change the data type of ans to long long and so of x as numbers are big

        • + 17 comments

          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.
          
          • + 0 comments

            Best explanation, thanks.

          • + 0 comments

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

          • + 1 comment

            This is the best explanation ever. Thank you.

          • + 0 comments

            Hi,

            I have created a video tutorial for 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.

          • + 0 comments

            That explanation was genius!

          • + 0 comments

            Perfect explanation.

          • + 0 comments

            very welll explained bro.

          • + 0 comments

            its a best imagination dude..awesome

          • + 0 comments

            That's a wonderful analogy!

          • + 0 comments

            Yes this problem looks exactly similar like given one

          • + 0 comments

            Beautifully explained.

          • + 0 comments

            hah, I love this

          • + 0 comments

            Good explanation. Easy to understand and resolve this problem. I wonder how do you can imagine that one? =))

          • + 0 comments

            Hi! I really appreciate your explanation, it is very nice :) My doubt is, do you mean by height: "number of queries that Mario ate the mushroom for a given point?", and if it yes, then, in my opinion, not only the height matters but also the size of the mushroom(k), isn't? So, what happens if Mario ate 3 mushrooms of size (k=1, k=1, k=1) on a given point but 2 mushrooms of an other point but sizes(k=10, k=15)? Thanks!

          • + 1 comment

            K is the mushroom Mario always like to eat. And he likes mushrooms a lot. Hmmm… how could I say that? Mushrooms are so varied and bright https://pychedelichigh.com! The taste is different with each one, but they are all delicious!

            • + 0 comments

              Mushrooms are so varied and bright https://santameds.com/! The taste is different with each one, but they are all delicious!

          • + 0 comments

            The best answer plus the example is superb! Thanks a lot...

        • + 0 comments

          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]).

        • + 3 comments

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

          • + 0 comments

            Best explanation. Thank you!

          • + 0 comments

            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?

          • + 0 comments

            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

        • + 0 comments

          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.

        • + 0 comments

          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.

        • + 0 comments

          I always like to refer to your page photo retouching services india. Because it always helps me to find the best information that I need for me. The interview preparation becomes very good with the help of this page and I can find all the details that I want on the problem section.

        • + 0 comments

          You can watch this video : https://youtu.be/JtJKn_c9lB4 Really short video of 7 mins and explained awesome

        • + 0 comments

          I think its best explained as a bunch of blocks being stacked upon eachother, sometimes a block will be heavier than others, othertimes it wont stack on another block. By caching WHERE the blocks start and end and how high they are at that point, you can find the maximum value of the graph. This doesn't mean you'd know exactly where the maximum is, making it a much simpler problem that can be solved O(n * rows)

      • + 4 comments

        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.

        • + 2 comments

          Does using segment tree worked?

          Did you get all AC?

          • + 1 comment

            I usedlazy propogation , worked fine.

            • + 4 comments

              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.

              • + 1 comment

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

                • + 0 comments

                  Thank you.

              • + 0 comments

                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.

              • + 0 comments

                my solution with segment tree https://www.hackerrank.com/challenges/crush/forum/comments/1132259

          • + 0 comments

            my solution with segment tree https://www.hackerrank.com/challenges/crush/forum/comments/1132259

        • + 0 comments

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

        • + 2 comments

          Once you understand the logic. The question will look very easy.

          Here's the solution in Python. Java,C++

          Hackerrank - Array Manipulation Solution

          My answer is O(m log m) and it is faster than O(n)

          The maximum value of n is 10**7 whereas m log m is 5*10**5

        • + 1 comment

          i also want to know , did you get all testcases pass using segment tree? . If yes may you please share your solution applying segment tree

          • + 1 comment

            I did not use segment tree, sorry. I have never used segment tree, at least not by that name :-) I hope this makes sense and that you were asking me. This is a good site, but the comments are hard to follow,

            • + 0 comments

              i am not asking to you! my brother

      • + 1 comment

        brilliant mind ....

        • + 1 comment

          here is problem solution in java python c++ c and javascript programming. https://programs.programmingoneonone.com/2021/03/hackerrank-array-manipulation-solution.html

          • + 0 comments

            easy python solution with explanation https://hacker-rank-dsa-python.blogspot.com/2022/05/array-manipulation.html

      • + 0 comments

        thanks

      • + 0 comments

        thanks

      • + 1 comment

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

        • + 0 comments

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

      • + 0 comments

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

      • + 0 comments

        Please explain it to me in the simplest form you can

      • + 1 comment

        could you please describe the logic ??

        • + 0 comments

          well the process goes like this, the question is to add the values to the array in between 2 indexes, instead what we do is, at the start index, we add the number and after the end index we subtract the number. and finally we loop it to make the sum of all elements in the array, we find the maximum sum possible. and the logic is, here key is to find the maximum sum, but not generating the array, so when we add a number at start index, all the consecutive sums have the number in it's sum and when we subtract it we are actually removing the number so it does not exists outside the end index. by looping and finding the sum gives the maximum number. Hope my explination helped...

      • + 0 comments

        Yes, Your approach is brilliant.

      • + 0 comments

        I spent the night managing linked lists, and a headache! Your solution is so simple and so clear. Here is my small addition:

        // credit amansbhandari for his crystal clear solution in C++
        // The beauty of JavaScript Object/Set/Arrays is an improvement
        // space = O(k)  time = O(k)
        function arrayManipulation(n, queries) {
          let arro = {}
          let a,b,k,i,x=0,imax=0
          for(i=0;i<queries.length;i++) {
              a = queries[i][0]
              b = queries[i][1]
              k = queries[i][2]
              arro[a] = (arro[a]) ? arro[a]+k : k
              arro[b+1] = (arro[b+1]) ? arro[b+1]-k : 0-k
          }
          for(i in arro) {
            x += arro[i]
            if(x > imax) imax = x
          }
          return imax
        }
        
    • + 1 comment

      you mean O(n+k). nice solving

      • + 3 comments

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

        for i in range(a-1,b): 
            lst[i] += k
        

        print max(lst)

        • + 6 comments

          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_array
          def generator_queries(queries):
              init = 0
              index = 0
              while index <  queries:
                  yield map(int, raw_input().strip().split())
                  index += 1
                  
          for a, b, k in generator_queries(queries):
              for i in xrange(a-1,b): # another generator
                  array[i] += k # maybe use threads here
          print max(array)
          
          • + 1 comment

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

          • + 2 comments

            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.

            N, M = [ int(input) for input in  raw_input().strip().split() ]
            arr = [0] * N
            for _ in range( M ):
                a, b, k = [ int(input) for input in  raw_input().strip().split() ]
                for x in xrange( a-1, b ):
                    arr[x] +=k 
            print max( arr )
            

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

            N, M = [int(n) for n in raw_input().split()]
            arr = [0]*N
            for _ in range( M ):
                a, b, k = [int(n) for n in raw_input().split() ]
                arr[a-1] += k
                if b <= ( N - 1 ):
                    arr[b] -= k
            my_max = x = 0
            for i in range( N ):
                x += arr[i]
                if my_max < x:
                    my_max = x
            print( my_max )
            
            • + 0 comments

              Same logic (thanks!) with constraits addressed.

              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'
              
            • + 0 comments

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

          • + 0 comments

            static long arrayManipulation(int n, int[][] queries) { int element[]=new int[n];

            int size=queries.length; for(int i=0;i

            } int max=0; for(int i=0;i

            }
            

            } return max; }

          • [deleted]
            + 0 comments

            Why so many down Votes?? is this a bad method ??

        • + 0 comments

          did the same thing, but the time-limit's exceeding in half the cases :')

        • + 0 comments

          Same problem in my case

    • + 2 comments

      pure genius!

      • + 0 comments

        Truely!

      • + 3 comments

        Yes! This is a cool solution. Take a look here https://writemyessay4me.org/blog/scholarship-essay for a scholarship essay examples!

        • + 0 comments

          AGWQSG

    • + 0 comments

      There is nothing greedy about this algorithm.

    • + 1 comment

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

      • + 0 comments

        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.

    • + 0 comments

      Seriously Brilliant approach. Really appreciate it.

    • + 0 comments

      awesome.........

    • + 1 comment

      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.

      • + 0 comments

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

    • + 1 comment

      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.

      • + 3 comments

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

        from collections import defaultdict
        
        sums = defaultdict(int)
        _, n_ranges = (int(x) for x in input().split())
        
        for _ in range(n_ranges):
            start, stop, value = (int(x) for x in input().split())
            sums[start] += value
            sums[stop+1] -= value
        
        max_val = running_val = 0
        for _, val in sorted(sums.items()):
            running_val += val
            max_val = max(max_val, running_val)
        
        print(max_val)
        
        • + 0 comments

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

        • + 2 comments
          n, m = input().strip().split(' ')
          n, m = [int(n), int(m)]
          l = [0] * (n+1)
          for a0 in range(m):
              a, b, k = input().strip().split(' ')
              a, b, k = [int(a), int(b), int(k)]
              l[a:b+1] = list(map(lambda x:x+k,l[a:b+1]))
          print(max(l))
          

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

          • + 2 comments

            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 ?

            • + 1 comment
              [deleted]
              • + 0 comments

                why deleted :(

            • + 1 comment

              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.

              • + 0 comments
                // Complete the arrayManipulation function below.
                static long arrayManipulation(int n, int[][] queries , int jj) {
                
                    long[] a = new long[n+1];
                    long max=0;
                    int i=0;
                    int start = queries[i][0];
                    int end = queries[i][1];
                    int sum = queries[i][2];
                    while(i<jj){
                        // System.out.println(jj+"=jj"+i);
                        System.out.println("s"+start+"e"+end+"sum"+sum+"i"+i);
                        if(start<=end){
                            a[start]=a[start]+sum;
                            if(a[start]>max){
                                max=a[start];
                            }
                            System.out.println("start"+start);
                            start++;
                        }else{
                            i++;
                            if(i<jj){
                            System.out.println("i"+i);
                            start = queries[i][0];
                            end = queries[i][1];
                            sum = queries[i][2];
                            }
                        }
                        // for(int l=1;l<a.length;l++){
                        //   System.out.print(a[l]+"\t");
                
                                    Complexity is only O(n) here , right
                        // }
                        // System.out.println("");
                    }
                    return max;
                }
                
          • + 0 comments

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

        • + 0 comments

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

    • + 0 comments

      That is awesome man!

    • + 0 comments

      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!

    • + 0 comments

      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

    • + 0 comments

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

    • + 0 comments

      awesome!!

    • + 0 comments

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

    • + 0 comments

      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!

    • + 2 comments

      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?

      • + 1 comment

        int vs long int?, overflow then

        • + 2 comments

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

          • + 0 comments

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

          • + 1 comment

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

            • + 0 comments

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

      • + 0 comments

        did u figure it out?

    • + 0 comments

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

    • + 0 comments

      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.

    • + 0 comments

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

    • + 0 comments

      Absolute Awesomeness.

    • + 1 comment

      Did it pass all test cases?

      • + 0 comments

        you can try it, it passes.

    • + 2 comments

      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);
          }
      }
      
      • + 1 comment

        You might want to try replacing List<Long>[] with long[]. There's no reason to build all of those arraylists and aggregate them later.

        • + 0 comments

          sounds good, thx

      • + 6 comments

        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 {

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

        }

        • + 1 comment

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

          • + 0 comments

            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.

        • + 0 comments

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

        • + 0 comments

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

        • + 0 comments

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

        • + 0 comments

          nice

        • + 0 comments

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

    • + 0 comments

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

    • + 1 comment

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

      • + 0 comments

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

    • + 1 comment

      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.

      I do the same in my efficient Java solution.

      HackerRank solutions.

      • + 1 comment

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

        • + 0 comments

          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.

    • + 0 comments

      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.

    • + 1 comment

      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.

      • + 0 comments

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

    • + 0 comments

      Amazing solution @amansbhandari great work.

    • + 0 comments

      moron we are'nt suppossed to discuss solutions!

    • + 0 comments

      Brilliant!

    • + 0 comments

      Amazing! Hats off.

    • + 1 comment
      [deleted]
      • + 1 comment

        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.

        • + 1 comment
          [deleted]
          • + 3 comments

            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.

    • + 1 comment

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

      • + 0 comments

        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.

    • + 0 comments

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

    • + 0 comments

      its genius!

    • + 0 comments

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

    • + 0 comments

      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?

    • + 0 comments

      chapeau

    • + 0 comments

      hatts of indeed but huge spoiler :/

    • + 0 comments

      From your solution,I turely konw that I love coding! How amazing it is!

    • + 3 comments

      I hope this explanation helps you to understand algorithm.

      If we draw a[]'s value into 'line graph', then the graph will looks like a mountain. (each a[n]'s value will indicate the height.)

      Imagine the mountain tracking from left to right, and 'max' stores the maximum height.

      starting point 'p' means go up / end point 'q+1' means go down. then, just adding p and q+1, we can know the current height(which is 'x'). and what we need to do is just find the maximum height. image

      (oh, this website's image upload is very bad..)

      • + 0 comments

        thank you so much.I want to be a skillfull man like you!

      • + 0 comments

        This is a very helpful picture - thanks!

      • + 0 comments

        Best explanation so far.

    • + 0 comments

      How do people think of this shit

    • + 0 comments

      My solution, O(M*log(M)):

      #include <cstdint>
      #include <map>
      #include <iostream>
      
      int main()
      {
        std::uint64_t N;
        std::uint64_t M;
        std::cin >> N;
        std::cin >> M;
        std::int64_t max = 0;
        
        std::uint64_t A;
        std::uint64_t B;
        std::uint64_t k;
          
        std::map<std::uint64_t, std::int64_t> points;
      
        for (std::uint64_t i = 0; i < M; ++i) {
          std::cin >> A;
          std::cin >> B;
          std::cin >> k;
          
          points[A] += k;
          points[B + 1] -= k;
        }
      
        std::int64_t value = 0;
        for (auto it = points.begin(); it != points.end(); ++it) {
          value += it->second;
          if (value > max) {
            max = value;
          }
        }
        std::cout << max;
        return 0;
      }
      

      It is not necessery to store full array. It is sufficient to store only begins and ends of all intervals (A and B). For example, if you have 10^7 elements and one operation, you need only 2 points, not 10^7. But in some languages (for example pure C) you will need to implement someone ordered container with fast insert operation, for example ordered List.

    • + 0 comments

      Great...!!!

    • + 2 comments

      Here is the PHP code of this solution. Teached me a lot. Thanks.

      <?php
      $_fp = fopen("php://stdin", "r");
      /* Enter your code here. Read input from STDIN. Print output to STDOUT */
      fscanf($_fp, "%d %d", $size, $operations);
      $array = [];
      
      $max = PHP_INT_MIN;
      
      for($i=0; $i<$operations; $i++){
          fscanf($_fp, "%d %d %d", $start, $end, $value);
          $negativeValue = $value * -1;
          if(!isset($array[$start])) $array[$start] = $value;
          else $array[$start] += $value;
          if($end+1<=$size){
              if(!isset($array[$end+1])) $array[$end+1] = $negativeValue;
              else $array[$end+1] -= $value;
          }
      }
      ksort($array);
      
      $sum = 0;
      foreach($array as $amount){
          $sum += $amount;
          if($sum>$max) $max=$sum;
      }
      
      echo $max;
      ?>
      
      • + 1 comment

        New on this site and having hard time with this task. Luckily found your comment and found my mistake. here's my short version of yours

        <?php
        $_fp = fopen("php://stdin", "r");
        $_fp2 = fopen('php://stdout', 'w');
        /* Enter your code here. Read input from STDIN. Print output to STDOUT */
        
        fscanf($_fp, "%d %d", $n, $m);
        
        $r = [];
        
        for($i=0; $i<$m; $i++){
            fscanf($_fp, '%d %d %d', $a, $b, $k);
        
            $r[$a] += $k;
            $r[$b+1] -= $k;   
        }
        ksort($r);
        
        $max = $sum = 0;
        
        foreach ($r as $val) {
            $sum += $val;
            if ($sum > $max) {
                $max = $sum;
            }
        }
        
        fwrite($_fp2, $max);  
        ?>
        
        • + 1 comment

          ksort is the key

          • + 0 comments

            If I'm thinking about the same thing as you, then yes, it can be used. But I'm not sure if it's available in Java.

      • + 1 comment

        I think a little cleaner PHP solution:

        <?php
        
        fscanf(STDIN, '%d %d', $n, $m);
        
        $list = [];
        for ($i = 0; $i < $m; $i++) {
            list($a, $b, $k) = explode(' ', trim(fgets(STDIN)), 3);
        
            $list[$a-1] = ($list[$a-1] ?? 0) + $k;
            $list[$b] = ($list[$b] ?? 0) - $k;
        }
        
        ksort($list);
        
        $running_total = 0;
        $max = 0;
        foreach ($list as $value) {
            $running_total += $value;
            $max = max($max, $running_total);
        }
        
        print $max;
        
        • + 2 comments

          My Solution is the similar, but it can not pass testcases 7-13, because "Runtime Error".

          I downloaded input\output data for 7th testcase and it's pass locally.

          What is wrong?

          $handle = fopen ("php://stdin", "r");
          fscanf($handle, "%i %i", $n, $m);
          
          $h = array_fill_keys(range(0, $n), 0);
          for($a0 = 0; $a0 < $m; $a0++){
              fscanf($handle, "%i %i %i", $a, $b, $k); 
              $h[$a-1] += $k;
              $h[$b] -=$k;     
          }
          $prev = 0;
          $max = PHP_INT_MIN;
           foreach($h as $value){
               $prev += $value;
               if($prev > $max) $max = $prev;
           }
          echo $max;
          
          • + 1 comment

            You fill the whole array, probably it's not enough memory

            • + 1 comment

              Easy to understand: don't update the array to overflow memory, just use some var for last_val

              • + 0 comments

                why is the foreach loop faster than a for loop here at the end when determining the max?

          • + 0 comments

            ksort

    • + 0 comments

      How did u think of this!! Saying its brilliant is understating it. Its genius!

    • + 0 comments

      Unused variable j.

    • + 0 comments

      out of box thinking..hats off..

    • + 0 comments

      While I appreciate the elegance of your solution, the fact that the solution is posted in the very first comment is rather disappointing.

      The purpose of these exercises is not to copy and paste someone else's solution, but rather to get to the answer on your own. To that end, these discussions shouldn't just be code that you copy and paste.

    • + 0 comments

      can you explain me please i m having problem to understand why did you do this ???

    • + 0 comments

      Superb...... Same I implemented in JS

      function processData(input) {
          let arr = input.split('\n');
          const NM = arr[0].split(' ').map(Number);
          const N = NM[0];
          const M = NM[1];
          let obj = {};
          for (let i = 1; i <= M; i++) {
              const abk = arr[i].split(' ').map(Number);
              const a = abk[0]; const b = abk[1]; const k = abk[2];
              obj[a] = obj[a] ? obj[a] + k : k;
              obj[b+1] = obj[b+1] ? obj[b+1] - k : (k*-1);
          }
          delete(obj[N+1]);
          let MAX = 0; let X = 0;
          for (const key in obj) {
              X += obj[key];
              if (MAX < X) MAX = X;
          }
          console.log(MAX);
      }
      
    • + 0 comments

      Hats of Sir... maja aa gaya

    • + 0 comments

      Someone's probably mentioned, but to avoid using O(n) space, you can use a sparse data structure like a map.

      import qualified Data.Map.Strict as M
      import Data.List (foldl')
      
      main = do
          getLine -- skip the first line, we won't use N or M
          input <- map readWords . lines <$> getContents -- lazily read operations
          let ops = foldl' insertOperation M.empty input
          print $ findMax ops
      
      readWords = map read . words
      
      insertOperation m [a, b, k] = (M.insertWith (+) a k) . (M.insertWith (+) (b+1) (-k)) $ m
      
      findMax :: M.Map Int Int -> Int -- Result is >= 0
      findMax m = snd $ M.foldl' update (0, 0) m
          where update = \(cur, peak) x -> let next = cur + x in (next, max peak next)
      
    • + 0 comments

      Brilliant approach

    • + 0 comments

      Awesome approach....!

    • + 0 comments

      seriously brilliant approach!!!!!!!!

    • + 0 comments

      perfect man,you are awesome......

    • + 0 comments

      If you make the "a" array longer by 1, you can get rid of the "if" in the inner loop.

    • + 1 comment

      Oh that is clever. Very very clever. I was brute-forcing it (running every operation in full on every element from a to b) and every test from Test 5 onward was timing out.

      Here's my Python 3 implementation of your solution:

      n,m = map(int, input().split()))
      numbers = [0] * n
      value, maxval = 0,0
      for _ in range(m):
          a, b, k = map(int, input().split())
          numbers[a-1] += k
          if b < n: numbers[b] -= k
      for number in numbers:
          value += number
          if value > maxval: maxval = value
      print(maxval)
      
      • + 0 comments

        can you explain your code ? , please

    • + 0 comments

      Your solution is simply amazing!!! I spent an whole hour scratching my head thinking about disjoint sets!! Here I what wrote it in C++ using map better allocation.

      define ll long long int

      using namespace std;

      int main() { ll n,m,a,b,k; cin>>n>>m; map arr; while(m--){ cin>>a>>b>>k; if(arr.find(a)==arr.end()) arr[a]=0; arr[a]+=k; if(arr.find(b)==arr.end()) arr[b]=0; arr[b+1]-=k; } ll max=0,x=0; map::iterator i; for(i=arr.begin();i!=arr.end();i++){ x+=i->second; if(x>max){ max=x; } } cout<

      Thanks man!! I was thinking to quit but your answer gave me spirit to keep continuing.

    • + 0 comments

      This method is also known as "Prefix sum method"

    • + 1 comment

      Your solution is elegant:-In java:-

      import java.util.*;
      public class AlgorithmicCrush {
      	public static void main(String[] args) {
      		int n,m,a,b,k;
      		Scanner in=new Scanner(System.in);
      		n=in.nextInt();
      		m=in.nextInt();
      		long arr[]=new long[n];
      		long max=0,x=0;
      		for(int i=0;i<m;i++) {
      			a=in.nextInt();
      			b=in.nextInt();
      			k=in.nextInt();
      			arr[a-1]+=k;
      			if(b<=n-1)
      				arr[b]-=k;
      		}
      		for(int i=0;i<n;i++) {
      			x+=arr[i];
      			if(max<x)
      				max=x;
      		}
      		
      		System.out.print(max);
      	}
      
      }
      

      PS:-I really liked that your indexing goes from 1 to n in the array of size n+1.It's intuitive.Maybe that's a norm.Anyways,gonna learn more. :)

      • + 0 comments

        does not pass test cases

    • + 0 comments

      A java version:

      public static void main(String[] args)
      {
          Scanner in = new Scanner(System.in);
              
          int N = in.nextInt();
          int M = in.nextInt();
              
          int[] arr = new int[N];
              
          int a;
          int b;
          int k;
          while (M-- > 0)
          {
              a = in.nextInt() - 1;
              b = in.nextInt();
              k = in.nextInt();
                  
              arr[a] += k;
              if (b < N) arr[b] -= k;
          }
          in.close();
              
          long max = Long.MIN_VALUE;
          long sum = 0;
          for (int value : arr)
          {
              sum += value;
              if (sum > max)
              {
                  max = sum;
              }
          }
              
          System.out.println(max);
      }
      
    • + 0 comments

      My machine (local) is giving me 2147473274 but the expected answer is 2497169732. Any idea why this is happening?

    • + 0 comments

      Interesting. For anyone who doesn't understand, let's assume that we know a maximum is at position i in the list. We know that the intervals that don't include i will not contribute to the calculation of i. If we add a spike at the start of a interval, and subtract the spike from right after the interval, then when you add the two spikes together, you will get zero, which is what we want to happen if i is not in that interval. As intervals overlap, there will be multiple positive spikes followed by multiple negative spikes. When you add the positive spikes together, you find a local maximum, and then when you add the negative spikes, you descend from that maximum. The global maximum can thus be found by traveling along the spikes and comparing local maximums. It's almost like you're adding the impulse response of each interval. This solution is not obvious.

    • + 0 comments

      Thank you so much

    • + 0 comments

      hats off, how did u come up with such a speachless solution, can u point out some books or fileds i can learn, thanks.

    • + 0 comments
      if((q+1)<=N) a[q+1]-=sum;
      

      why are you doing this can someone explain this to me?

    • + 0 comments

      How is it in O(1) Auxiliary space althoug you initialize array of n+1 long ints here

      long int *a=new long int[N+1]();
      

      you may use dictionary to shrink the used space.

    • + 0 comments

      brilliant approach... just used simple data structuring approach

    • + 0 comments

      I think that your space complexity is not O(1) but O(n) because you are creating an array of size n which is not given in the input. So, you are basically creating an array for solving your question, so the auxilliary time complexity is O(n). Please correct me if I am wrong!

    • + 0 comments

      Yes, that's indeed an anwser, the test is about your observation and math. Now I understand what those company want.

    • + 0 comments
      long int *a=new long int[N+1]();
      

      Q.1 What is the use of simple brackets? Q.2 How to intialize a all with zeroes? Q.3 How to create an empty sequence a?

    • + 0 comments

      Actually, we can only store the edge elements to reduce memory cost from O(n) to O(m). In Java, we can use SortedMap (e.g. TreeMap) to do that (java8)

      import java.io.*;
      import java.util.*;
      import java.util.Map.Entry;
      import java.text.*;
      import java.math.*;
      import java.util.regex.*;
      
      public class Solution {
      
      	public static void main(String[] args) {
      		Scanner in = new Scanner(System.in);
      		int n = in.nextInt();
      		int m = in.nextInt();
      
      		TreeMap<Integer, Integer> map = new TreeMap<>();
      		for (int a0 = 0; a0 < m; a0++) {
      			int a = in.nextInt();
      			int b = in.nextInt();
      			int k = in.nextInt();
       
      			map.put(a, map.getOrDefault(a, 0) + k);
      			if (b + 1 <= n) {
      				map.put(b + 1, map.getOrDefault(b + 1, 0) - k);
      			}
      		}
      		in.close();
      
      		long max = map.firstEntry().getValue();
      		long sum = 0;
      		for (Entry<Integer, Integer> e : map.entrySet()) {
      			sum += e.getValue();
      			if (sum > max) {
      				max = sum;
      			}
      		}
      
      		System.out.println(max);
      	}
      }
      
    • + 0 comments

      brilliant solution.......... bt in [if((q+1)<=N)] y "<=N" ??? shdt it be N+1 ????

    • + 0 comments

      What is the name of this algorithm?

    • + 0 comments

      Can yo please tell the name of this approach so that i can read about it in further depth?

    • + 0 comments

      i see. it works, although im surprised doing it the dumb way, which is what i did fails the tests. how big could their test case be?

    • + 1 comment

      What happen if q == N, will this solution still work?

      • + 0 comments

        Yep. F

    • + 0 comments

      awesome solution <3

    • + 0 comments

      "long int " is fine why not "int is working here ?

    • + 6 comments

      Explanation:

      A straight forward implementation would start with an array for and perform modifications, where the elements for are getting the value added.

      This would need

      operations, so it is . The constraints require to handle up to and resulting in about operations, which is outside the given resources.

      The above solution manages to requires setup steps and a final integration step visiting not more than array elements, so it is . For the constraints not more than about steps are needed, which is possible to compute with the given resources.

      In Detail:

      Let us start with the continuous case:

      We start with a constant function and then add the modifications, going through a sequence of modified functions .

      Given and adding the value for all times , this results into the modified function

      where is the characteristic function of set and is the Heaviside distribution
      The derivative is
      where is the Dirac distribution.

      For the discrete case this seems to turn into

      with

      So the modeling of the derivative is very efficient, only recording the changes at the interval borders.

      After modifications of the constant null function we get:

      Finally is reconstructed by summing up (integrating) over :

      where we used as smallest value.

      • + 0 comments

        holy .... awesome explanation! It took me a couple hours to remember some math definitions. Thank you so much.

      • + 0 comments

        Great article ! Thanks. A small suggestion, logical explanation would be better rather than mathematical, since it is confusing to understand the equation and its representation.

      • + 0 comments

        This was soooo helpful! Thank you.

      • + 1 comment

        Really nice and clean! One thing I wonder, though. What prompted @mvanwoerkom to take the derivative? I understand it makes everything easier, but it would never occur to me, as a logical step, to take the derivative and integrate at the end.

        • + 0 comments

          I think this is a common computing strategy if it's less taxing to calculate than the original functions because you can work backwards to get the same number at the end

      • + 1 comment

        wodo stuff this is how you make 5 minute solution wodo. overcomplification. need better solution which work in real world not on therotical basis. it is in dream. By the way good copy paste.

        • + 0 comments

          Totally agreed

      • + 0 comments

        Thanks! This what I was expecting in Discussion

    • + 0 comments

      Really great!!

    • + 0 comments

      Brilliant man!!

    • + 0 comments

      Brilliant! Is there a resource which can teach how to come up with such solutions? Or is it just practice?

    • + 0 comments

      how you guys think this kind of logic!

    • + 0 comments

      The same solution in Scala

      object Solution {
          def main(args: Array[String]) = {
          val scan = new java.util.Scanner(System.in)
          val n  = scan.nextInt()
          val m = scan.nextInt()
      
          val arr:Array[Long] = Array.fill(n)(0)
      
          var  lower: Int =0
          var upper:Int =0
          var sum:Long=0
          for{
            i <- 0 until m
          }{
                  lower=scan.nextInt()
                  upper=scan.nextInt()
                  sum=scan.nextInt()
                  arr.update(lower-1,arr(lower-1)+sum)
                  if(upper<n)
                    arr.update(upper,(arr(upper)-sum))
          }
      
          var max: Long = 0;
          var temp:  Long = 0;
      
          for{
            i <- 0 until n
          }{
            temp = temp+arr(i)
            if(temp>max) max=temp
          }
      
          System.out.println(max)
        }
      }
      
    • + 0 comments

      This was so beautiful.

    • + 3 comments

      These two places helped me to understand this algorithm more clearly. Prefix_sum_array_and_difference_array Stack Overflow

      If you want a simple and direct explanation: Initial, the array is 0 0 0 0 0

      after the first operation, 1 2 100
      it will become
      seq1: 100 100 0 0 0
      and after second 2 5 100
      seq2: 0 100 100 100 100
      and after 3 4 100
      seq2: 0 0 100 100 0
      

      but when we apply difference array at every step, we will get

      diff seq of seq1: 100 0 -100 0 0
      diff seq of seq2: 0 100 0 0 0 -100
      diff seq of seq3: 0 0 100 0 -100
      

      One important property is the difference sequence of the sum of the sequences is the sum of the difference sequences.

      it will give us,

      100 100 0 0 -100 -100(for clarity purpose only)
      

      or you can add all the sequences as

      seq1+seq2+seq3 = 100 200 200 200 100
      

      and then find the difference seq or the difference array which is 100 100 0 0 -100 and then find the prefix array.

      Why we ignore the first 100??? Read the first article about difference array and prefix sum array!!!!

      and after this, do prefix sum

      100 200 200 200 100 0
      

      Ignore last 0 as the last index we considered is for clarity purpose only.

      so,both these steps find the difference array for us:)

      a[p]+=sum;
      if((q+1)<=N) a[q+1]-=sum;
      
      • + 0 comments

        Your links are not correct, remove the extra protocol prefixes.

      • + 0 comments

        Really useful, thanks.

      • + 0 comments

        From the code at the top I gave custom input as

        10 2 5 7 600 1 4 500

        and i got output as 600

        then my question is when i enter the input for first operation then at a[5]=600 and a[8]=-600 now when i enter the input for second operation then a[1]=500 and a[5] becomes 100 as it was earlier 600(i.e 600-500). can anybody please explain how i got output as 600.

    • + 0 comments

      but in the instructions its given that :you have to add value k to all the elements ranging from index a to b(both inclusive).

    • + 0 comments

      Excellent!!!, I am very curious how did you find out this solution ?

    • + 1 comment

      Why are you taking array of size n+1?

    • + 0 comments

      u r best man

    • + 0 comments

      Brilliant.

    • + 0 comments

      Pure logic and math. Perfect. I can't be this level thinker, never. Regards.

    • + 1 comment

      Here is in Go:

      package main
      
      import (
          "fmt"
          "os"
          "bufio"
      )
      
      const MinInt = -(int(^uint(0) >> 1)  - 1) 
      
      func main() {
          var n, m, a, b, k int
        
          io := bufio.NewReader(os.Stdin)
          fmt.Fscan(io, &n)
          fmt.Fscan(io, &m)
          l := make([]int, n)
          
          for i := 1; i <= m; i++ {
              fmt.Fscan(io, &a)
              fmt.Fscan(io, &b)
              fmt.Fscan(io, &k)
              
              l[a-1] += k
              if b <= n -1 {
                  l[b] -= k
              }
          }
          
          max := MinInt
          sum := 0
          for _,v := range l {
              sum += v
              if sum >= max {
                  max = sum
              }
          }
          fmt.Print(max)  
      }
      
      • + 0 comments

        Very nice. I'd just use math.MinInt64 instead of MinInt.

    • + 0 comments

      Brilliant. One comment - N is bound to 10^7 and M (K in this code) - only to 2*10^5 (for a total of 4*10^5 points, if no duplicates) - more than an order of magnitude less, so a hashmap may be used instead of of an array. This should improve space complexity for exchange of somewhat worse constant factors.

    • + 0 comments

      I gave custom input as

      10 2 5 7 600 1 4 500

      and i got output as 600

      then my question is when i enter the input for first operation then at a[5]=600 and a[8]=-600 now when i enter the input for second operation then a[1]=500 and a[5] becomes 100 as it was earlier 600(i.e 600-500). can anybody please explain how i got output as 600.

    • + 0 comments

      I am new here. I want to know if can I to put my code within the main function?

    • + 1 comment

      what is "n" in O(n) for this problem? can you answer me? thanks

      • + 0 comments

        O(n) in this case is only for the time complexity, it means linear. In the practice is a simple loop, so for example if you have a loop inside another loop the time complexity will be o(n2). This is theory from Big O Notacion.

    • + 0 comments

      is this the better running time that can be achieved?? how can i find out that thanks if you can reply

    • + 0 comments

      add x=arr[0],max=x; before the second loop

    • + 0 comments

      sir, your logic is so good

    • + 0 comments

      Brilliant! thanks a lot...

    • + 0 comments

      very good

    • + 0 comments

      Can you please correct my code... My code

    • + 0 comments

      and in this essentially equates to:

      from which you can immediately write an inefficient algorithm. If you use imperative state to efficiently update the summations, you have something along the lines of what OP has written.

    • + 0 comments

      Excellent solution!

    • + 1 comment

      I used the same approach but I am getting a segmentation fault in test cases 7-12. Can someone please explain me why?

      #include<iostream>
      using namespace std;
      int main()
      {
          long n,m,a,b,k,sum=0,ans=0;
          cin>>n>>m;
          long int arr[n+1]={0};
          for(int i=0;i<m;i++)
          {
              cin>>a>>b>>k;
              arr[a]+=k;
              if(b!=n)
                  arr[b+1]-=k;
          }
          for(int i=1;i<=n;i++)
          {
              sum+=arr[i];
              if(sum>ans)
                  ans=sum;
          }
          cout<<ans<<endl;
      }
      
      • + 0 comments

        can you explain the logic behind

        if(b!=n) arr[b+1]-=k; } for(int i=1;i<=n;i++) { sum+=arr[i]; if(sum>ans) ans=sum; }

    • + 0 comments

      Awesome :)

    • + 0 comments

      So basically what he did in mathematical terms is

      1. He differentiated the function, found the change in array keys like +100, -100 etc. :-

        arr[lower-1]+=sum;
        
        if(upper < n) arr[upper]-=sum; 
        
      2. Then he integrated the derivated function to get the original function value at different points and found the max value:-

             for(int i=0;i<n;i++){
                                 temp += arr[i];
                                    if(temp> max) max=temp;
                        }
        
    • + 0 comments

      Very nice Idea......

    • + 0 comments

      ur algorithm blew my mind . u r genius

    • + 0 comments

      why its a[q+1] not a[q]?

    • + 0 comments

      How is space complexity O(1), can you explain? I think it's O(n) use of memory.

    • + 1 comment

      Wow man how did you even come up with this amazing ass solution! I'm dumbstruck by how out-of-the-box solution this is!

      • + 0 comments

        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.

    • + 0 comments

      Really Thanks

    • + 0 comments

      I am in awe of your approach! Wish I could think like this.

    • + 0 comments

      I have similar solution but it is giving timeout for some cases. why is it so? :

      include

      using namespace std;

      int main() { long int n,m; cin>>n>>m; long int arr[n] = {0}; for(long int i = 0;i>a>>b>>k; arr[a-1]+=k; if(b<=n) arr[b]-=k; } long int max = 0; long int s=0; for(long int i=0;imax) max = s; } cout<

    • + 0 comments

      amazing...

    • [deleted]
      + 0 comments

      That was a sexy approch !!

    • + 0 comments

      woww

    • + 0 comments

      Brilliant approach.

    • + 0 comments

      Very nice approach.

    • + 0 comments

      Nice one. Respect!

    • + 0 comments

      Excellent!! How did this idea strike in your head?? In what way you were thinking for the solution.?

    • [deleted]
      + 0 comments

      Why you said that your solution is O(1) Auxiliary space? You allocate O(N) of auxilary space for array 'a'

    • + 0 comments

      The concept used here is popular by the name "Difference Array" you can google it by "difference array" or check it out here https://www.geeksforgeeks.org/difference-array-range-update-query-o1/ btw the approach is really awesome and will make you learn something new and interesting

    • + 0 comments

      Brilliant!

    • + 0 comments

      I had the same approach. However, wouldn't it be more accurate to call it O(m+n)? The number of queries can exceed the size of the array by a huge factor.

    • + 1 comment

      Same idea in java. Thank you for posting this by the way , helped immensely!

      static long arrayManipulation(int n, int[][] queries) {
          long[] diff = new long[n+2];
          for(int[] query : queries){
              diff[query[0]]+=query[2]; //a,b,k
              diff[query[1]+1]-=query[2];
          }
          long  max =0;
          long current=0; 
          for(long i : diff){
              current+=i;
              if (current >  max )
                  max = current;
          }
          return max;
      }
      
      • + 0 comments

        nice one, thanks man!

    • + 0 comments

      Brilliant approach (claps!!)

    • + 0 comments

      Awesome

    • + 0 comments

      wow

    • + 0 comments

      time = O(n + m), space = O(n)

      or in your algorithm...it's O(N + K) and O(N)

    • + 0 comments

      brilliant :)

    • + 0 comments

      Perfect.

    • + 0 comments

      You sir are brilliant, very clever solution.

    • + 0 comments

      O(n) is actual space complexity, other than that is the correct solution

    • + 0 comments

      Genius!

    • + 0 comments

      You have auxillary space O(n) by allocating the array

    • + 0 comments

      Actually your answer is little bit wrong. You forgot the case that index 0 can be the largest number. test your code with following custom input; 5 4 1 1 500 2 4 100 3 5 200 2 5 100 you will see that output is 400 but it should be 500

    • + 0 comments

      n, m = list(map(int, input().split())) l = [0]*(n+1) for k in range(m): a, b, num = list(map(int, input().split())) l[a-1]+=num l[b]-=num maxa, x = 0,0 for i in l: x+=i if maxa

      made one in python, did not even pass as many testcases, that one with just direct adding did

    • + 0 comments

      O(n+m) actually. O(N+K) in you case

    • + 0 comments

      Your solution is brilliant indeed. You look at all the information precisely once.

      Your variable names? Driving me mad. Curses.

      Anyway, it's really elegant. Thanks ;).

      I think, I should do some yoga now.

    • + 0 comments
          I think You can make a small improvement.
          It was possible to create an array with n + 2 elements instead of n-1 elements and not use the operator "if".
      
          change 
      
          1. "long int *a=new long int[N+1]();" to 
          "long int *a=new long int[N+2]();"
          2. "if((q+1)<=N) a[q+1]-=sum;" to 
                                "a[q+1]-=sum;"
      
    • + 0 comments

      I got one problem, I used the same approach but instead of using long int*a=new long intN+1; I took long int arr[N+1]={0}; This gave segmentation fault for few cases..Can anyone explain me why?

    • + 1 comment

      Too good!

      Same solution in java:

      static long arrayManipulation(int n, int[][] queries) {
          long[] arr = new long[n];
          long max=0;
          int a=0; int b=0; int k=0;
          int m=queries.length;
      
          for (int i=0; i<m; i++){
              a = queries[i][0]-1;
              b = queries[i][1]-1;
              k = queries[i][2];
              arr[a]+=k;
              if(b+1<n)
                  arr[b+1]-=k;
          }
          for (int i=1;i<n;i++ ){
              arr[i]+=arr[i-1];
              if (arr[i]>max)
                  max=arr[i];
          }
      
          return max;
      }
      
      • + 2 comments

        This Programe will Fail if Input is like, 5 3 1 1 500 2 5 100 3 4 100

        • + 0 comments

          WHY IT WOULD FAIL FOR THE GIVEN INPUT

        • + 0 comments

          Input (stdin) 5 3 1 1 500 2 5 100 3 4 100 Your Output (stdout) 500 I HAVE TESTED IT

    • + 0 comments

      Same solution in golang

      func arrayManipulation(n int32, queries [][]int32) int64 {
      	arr := make([]int64, n+1)
      
      	for _, element := range queries {
      		a := int(element[0])
      		b := element[1]
      		k := int64(element[2])
      		arr[a] += k
      		if (b + 1) <= n {
      			arr[b+1] -= k
      		}
      	}
      
      	var x, max int64 = 0, 0
      	for i := 1; i <= int(n); i++ {
      		x += arr[i]
      		if max < x {
      			max = x
      		}
      	}
      	return max
      }
      
    • + 0 comments

      how did you find this one. great job man. awesome algorithm

    • + 0 comments

      How clever you are!!

    • + 0 comments

      Same solution in scala

        def arrayManipulation(n: Int, queries: Array[Array[Int]]): Long = {
          val arr = Array.fill[Int](n)(0)
      
          queries foreach { case Array(a, b, k) =>
            arr(a - 1) = arr(a - 1) + k
            if (b < n) arr(b) = arr(b) - k
          }
      
          val max = 0L
          val sum = 0L
      
          val (result, _) = arr.foldLeft((max, sum)) { case ((currentMax, currentSum), elem) =>
            val newSum = currentSum + elem
            if (newSum > currentMax) (newSum, newSum) else (currentMax, newSum)
          }
      
          result
        }
      
    • + 0 comments

      I think this algorithm has O(N)+O(K) time complexity (not O(N) as the author estimated) and O(N) space complexity (not O(1))

    • + 0 comments

      bhai perfect yrr

    • + 2 comments

      I'm not taking the credit. i waste a lot of time with this one too. my js solution, in case someone interested.

      function arrayManipulation(n, queries) {
          let tmp = {},
              max,
              currentNumber = 0;
          for (let i = queries.length - 1; i >= 0; i -= 1) {
              let [firstElem, lastElement, value] = queries[i];
              tmp[firstElem] = (tmp[firstElem] || 0) + value;
              tmp[lastElement + 1] = (tmp[lastElement + 1] || 0) - value;
          }
          for (let key in tmp) {
              currentNumber += tmp[key];
              if (!max || currentNumber > max) {
                  max = currentNumber;
              }
          }
          return max;
      }
      
      • + 0 comments

        Excellent answer. Can you explain a little bit about your code? How do you came to solution? Thanks

      • + 0 comments

        I am interested Thank you

    • + 2 comments

      Whats the problem with my code? only 7 test cases are showing wrong. Please help me with it.

      #include <cmath>
      #include <cstdio>
      #include <vector>
      #include <iostream>
      #include <algorithm>
      using namespace std;
      int main()
      {
          long int n,m;
          cin>>n>>m;
          long int arr[n];
          long int k;
          int a,b;
          for (long int i=0;i<n;i++)
          arr[i]=0;
          for (long int i=0;i<m;i++)
          {
              cin>>a>>b>>k;
              for (int j=a-1;j<=b-1;j++ )
              {
                  arr[j]+=k;
              }
          }
          long int max=arr[0];
          for (long int k=0;k<n;k++)
          {
              if (arr[k]>max)
              max=arr[k];
          }
          cout<<max;
      
          return 0;
      }
      
      • + 0 comments

        Same solution in c++. I guess it's because of the quadratic time complexity.

      • + 0 comments

        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.

    • + 0 comments

      Same solution in Swift

      func arrayManipulation(n: Int, queries: [[Int]]) -> Int {

      var arr = Array(repeating: 0, count: n+1)
      queries.forEach{
          let a = $0[0]
          let b = $0[1]
          let k = $0[2]
      
          arr[a-1] += k
          arr[b] -= k
      }
      
      let reducedArr = arr.reduce(into: (0,0), { result, number in
          result.0 += number
          result.1 = max(result.1, result.0)
      
      })
      return reducedArr.1
      

      }

    • + 0 comments

      This solution is actually O(n) space: you use actual array of (n+1) elements. And time is O(n+m)

      This task can be solved with O(m log m) time and O(m) space. For this task, it's better.

    • + 0 comments

      Neat!

      That said, this definitely isn't O(1) auxiliary space. You allocate an array of length N

      It's also not O(n). It's O(N+K). If N = 3 and K = 1,000,000,000,000 that first for-loop is still gonna take a mighty long time (by comparison).

    • + 1 comment

      Sorry, we can't accept your submission. The custom input size should not exceed 50Kb.

      I am getting this error even if I am trying using your program...

      Please tell me where I am going wrong...

      Thanks in advance

      • + 0 comments

        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.

    • + 0 comments

      Nailed It Bro

    • + 0 comments

      wow, this is so brilliant, I have learn some great lesson from this. thanks!

    • + 0 comments

      @amansbhandari how much you took to solve this?

    • + 0 comments

      beautifully written

    • + 0 comments

      You don't need to test the end of the array if you make one slot bigger, as we are going for the max and the last extra can only accept decrements, it's safe to leave it there.

    • + 1 comment

      This algorithm doesnt work for all examples, for suppose if the inputs are n=9,m=3 and m inputs are (3,6,3), (5,7,10),(7,9,11). At 6th index we get the maximum 23 as output, but as per by the above algorithm we get the maximum value is 13.

      • + 0 comments

        thanks i got it.

    • + 1 comment

      I completely understand this code and what it is accomplishing.

      What I struggle with is seeing/finding a solution like this. What is your thought process? Can someone explain how one is supposed to just know to implement a solution like this? Is this just one of those problems where you just say "Hm, this smells like a prefix sum type of problem"? I didn't even know what a prefix sum was until doing this problem xD

      I stared at this problem for some time, and I can tell you I would never have figured out this trick to solve the problem.

      Any pointers would be much appreciated :D

      • + 1 comment

        It's just pattern matching, like any other skill.

        Just solve a lot of problems - make sure to really struggle with a problem for a while first before taking a peek at the comments/solutions. Make sure to understand the solution properly. Maybe add some comments to the code stating the invariants, and why they hold true throughout.

        If the solution uses a new technique, read up on it. Search for other problems using the technique and solve those without peeking.

        What we should be aiming at is deliberate practice - don't waste time solving easy problems, solve problems that are just hard enough where it may just be possible to solve it, but only after a lot of struggle

        Almost everyone feels the same way, just with different levels of problems.

        • + 0 comments

          Thank you for the help :)

    • + 0 comments

      But if they ask to print the final array,, you are just manipulating with the edge value and giving answers accordingly

    • + 2 comments

      The memory allocated to a is never freed. It will cause memory leak.

      The memory allocated on the line:

      long int *a=new long intN+1;

      Memory allocated to long int a in never deleted in the main(). It will cause memory leak. Try executing the same program with valgrind, you will find the memory leak.

      Edit: Memory leak explanation.

      • + 1 comment
        [deleted]
        • + 0 comments

          The memory allocated on the line:

          long int *a=new long intN+1;

          Memory allocated to long int a in never deleted in the main(). It will cause memory leak. Try executing the same program with valgrind, you will find the memory leak.

      • + 1 comment

        sorry but, memory allocated to long int a is of the equal size of N (the size we required) so every position will be filled by an element ,, so how there will be a memory leak..

        • + 0 comments

          The "new" statement will allocate the memory from heap and this memory needs to be manually freed.

    • + 0 comments

      Omg you are extremely intelligent. It took so long time for me even understand that. It is so clear way to do it just perfect. Like a mathematical art.

    • + 0 comments

      Hi,

      How come its O(n) complexity ?? do not you think its O(n+m)??

    • + 0 comments

      100 % working code with video explanation -- All Test Case Passed..!!

      Here is the video explanation of my solution -

      https://youtu.be/hDhf04AJIRs

      and you can find most of the hackerrank solutions with video explaination here- https://github.com/Java-aid/Hackerrank-Solutions

      and many more needs to be addeed.

      any feedback or comment would be highly appreciated.

      Regards,

      Kanahaiya Gupta

      Git Hub URL | https://github.com/Java-aid/

    • + 1 comment

      really great approach.

      • + 0 comments

        Thanks a lot.

        but if you dont mind can you please leave the same comment on my video. it motivates me and help others too find the solution over internet.

    • + 1 comment

      hey but i think that index number is still bit confusing ...... here in the problem the frst element represent the 0th element so .....

      • + 0 comments

        correct , in problem first element represent the zeroth element. If you have seen my video without skipping..:) then this doubt should not be there.:)

        Tell me honestly, you watched without skipping right?? :)

        If yes, and still doubt is there you can comment on my video will happly answer your query there.

        Why I am asking you to put your comment on my video because it will help others too who will be having the same doubt in future.

    • + 0 comments

      Awesome, It's a great thought process. Very trikcy though

    • + 2 comments

      a[p]+=sum; if((q+1)<=N) a[q+1]-=sum;

      // not able to understand the above part, can you please explain ?

      • + 1 comment

        watch the above linked video it's easy approach to solve this....

        • + 0 comments

          thanks for recommendation..:)

      • + 0 comments

        Here is the video explanation for the same.

        https://youtu.be/hDhf04AJIRs

    • + 1 comment

      Hey! We did the same solution! This is what i did in Java:

      public static long arrayManipulation(int n, int[][] queries) { long[] array = new long[n];

          for(int[] query : queries) {
              array[query[0] - 1] += query[2];
      
              if(query[1] < n) {
                  array[query[1]] += (query[2] * -1);
              }
      
          }
      
          long max = 0;
          long currentVal = 0;
      
          for(int i = 0; i < n; i++) {
              currentVal += array[i];
              if(currentVal > max) {
                  max = currentVal;
              }
          }
      
          return max;
      }
      

      I spent 2 days to come up with this solution, tho :( I feel so slow, i hope i can improve... I will !

      • + 0 comments

        Good one. Always remember turtle wins the race at the end.:) Keep learning ..keep growing..!!

    • + 0 comments

      Why can't we use "long int a[N+1]={};" instead of "long int *a=new long intN+1;"

    • + 0 comments

      One more optimization can be done: instead of trasversing whole array we could traverse array between indices - lower of left indices and higher of right indices

      A psudo code is as follows:

      
      for (i=0;i<row;i++){
          if (queries[i][0]-1 < low){
              low = queries[i][0]-1;
          }
          if (queries[i][1]-1 > high){
              high = queries[i][1]-1;
          }
      }
      
      for (i=low;i<=high;i++){
                  temp += a[i];
                  if(max < temp){
                      max = temp;
                  }
              }
      return max;
      
      
    • + 0 comments

      But the space complexity is not O(1) but O(n) on any input...

    • + 0 comments

      This is still O(n) space complexity, right? I don't understand why you said it would be constant space complexity.

    • + 0 comments

      this line "a[p]+=sum;" shouldn't it be under a loop?

    • + 1 comment

      what is the need of this?? if((q+1)<=N) { a[q+1]=a[q+1]-sum }

      instead why cant i do like this for(i=0;i>a>>b>>k; for(j=a;j<=b;j++) { arr[j]=arr[j]+k; }

      }

      please help in this??
      
      why there is subtraction ??
      
      • + 0 comments

        hi,

        I hope it will help you. https://www.hackerrank.com/challenges/crush/forum/comments/570284

    • + 0 comments

      Same algorithm in Python:

      def arrayManipulation(n, queries):

      maxVal = -2**32
      arr = [0] * n
      
      for a, b, k in queries:
          arr[a-1] += k
          if(b < n): arr[b] -= k
      
      currSum = 0
      for num in arr:
           currSum += num
           if(currSum > maxVal): maxVal = currSum
      
      return maxVal
      
    • + 0 comments

      For anybody still confused, just think of the array like voltage vs. time and the intervals are a pair of commands that tell when the signal goes up/down.

      So query (p q sum) means:

      raise voltage by sum starting at time p
      
      lower voltage by sum after time q
      

      The question is then asking, what's the peak voltage?

      The auxillary array is the net change in voltage at every point in time. So we can find peak voltage by examining every point in time while summing up all of the change of voltage commands encountered thus far.

    • + 0 comments

      excellent approach sir..

    • + 0 comments

      That works perfectly. I think of it as, the array of overall sum being integration. And what you are doing is placing the differential points by adding sums at p indexes and subtracting sums at q positions. Later I just have to integrate it(the second loop) to get the sums or calculate the max.

    • + 0 comments

      what if both indexes aare same

    • + 0 comments

      That seems to be O(n) in time and O(n) in space - you allocate array of n elements and go through it. Here is a sketch of a solution in O(m log m) time and O(m) space. Essentially what it does is go from left to right but skip cells where nothing changes.

      An Operation consists of 2 numbers: index to add at and value to add. The value can be positive or negative. * For each query (start, end, value) produce 2 operations: (start, +value) and (end + 1, -value). * Sort all operations by index (in O(m log m)) * Create an auxiliary variable holding current sum * Go through all operations from lowest to highest index. Aggregate all operations with equal index and add the sum of their value to current sum, obtaining next sum. * The largest of the sequence of such obtained sums will be the solution.

    • + 1 comment

      i believe i first learned this approach here (lost hackerrank account, sigh..) and used it to solve other problems from other contests (so thanks!) but i also want to note that this does not work well against more frequent queries of max values, or any value.

      • + 0 comments

        I've seen this approach in part 1 of "algorithms" course on coursera. It was used to find intersections between horizontal and vertical line segments on a plane. You're right, with large number of queries the sorting part might be a problem. But it can be improved a bit. When you create operations, do not put them on the list, but in a hash map where the keys are the indices from operation. When next operation is added, and there are already operatons with the same index, you only add the new operation's value to the value of existing operation. Then the number of operations to sort will be limited by n. But still, if the number of operations to sort is sufficiently close to n, the approach with array of length n should be faster.

    • + 0 comments

      Can you please tell me why we have to use pointer to array here, and why not declaring normal long array arr[n+1] won't work?

    • + 0 comments

      creating the array on the heap

      long int* a = new long int[N+1]();

      makes it O(N+1) instead of O(1) auxiliary space. plus there is a nasty bug in your code. you allocate on the heap and you never deallocate it

      delete a;

      So here is a BETTER solution O(log(N)) time complexity, and O(K) space complexity.

      long arrayManipulation(int n, vector<vector<int>> queries) `{

      long max = LONG_MIN;
      map<int, long> range;
      for(auto el: queries)
      {
      
          int a = el[0];
          int b = el[1]+1;
          int k = el[2];
      
          auto p1 = range.insert(make_pair(a,k));
          if(p1.second == false)
              p1.first->second += k;
      
          auto p2 = range.insert(make_pair(b, -k));
          if( p2.second == false)
              p2.first->second -= k;
      }
      long sum = 0;
      for(auto v:range)
      {
      
          sum += v.second;
          if(max<sum)
              max = sum;
      }
      return max;
      

      }`

      In this Approach, you olnly store the boundaries of each range, no need to fill the inbetween zeros, also searching, inserting and deleting and element in map is O(log(size(map)), which makes the worst case scenario O(log(N)).

      any comment or suggestion is welcome.

    • + 0 comments

      Hello sir, Could you please explain how is it that your code only takes O(1) auxiliary space? Thank you, Daniel.

    • + 0 comments

      Well, it's not O(n), it's O(N+K). But it's still top notch!

    • + 0 comments

      Same Solution in Scala

      def arrayManipulation(n: Int, queries: Array[Array[Int]]): Long = {

      val arr = Array.ofDim[Long](n + 1)
      
      for (q <- queries) {
        arr(q(0)) = arr(q(0)) + q(2)
        if (q((1)) + 1 != arr.size)
          arr(q(1) + 1) = arr(q(1) + 1) - q(2)
      
      }
      
      
      for (i <- 1 to arr.length - 1) {
        arr(i) = arr(i) + arr(i - 1)
      }
      arr.max
      

      }

    • + 1 comment

      I came up with the same solution in Javascript. The interesting thing about it is that JS Arrays are actually hashmaps and are sparse, so you don't end up iterating over N items if there are only a few spans. (E.g. if there is an element at arr[1] and another at arr[10000], arr.forEach will only perform two iterations.). For this reason, I'm careful NOT to initialize array elements and to check for undefined before adding the addend in order to minimize the number of elements in the array. After reading the op-ed, I think this is equivalent to their optimal solution.

      (Interestingly, if one prints the array alone with console.log(), it handles sparsness gracefully, but if you concatenate to another string with the + operator, it will print out all of the undefined elements individually.)

      Also note the single loop for adding up the diffs and finding the max without any extra variables outside the loop. (Trying to be functional.)

      I'm new to JS, so be gentle. Style advice for an old Java 2 progammer is welcome.


      function arrayManipulation(n, queries) {
      
          let diffs = [];
      
              queries.forEach((value, index) => {
      
                      const range_start = value[0];
                      const range_end = value[1];
                      const addend = value[2];
      
                      if (!diffs[range_start]) {
                              diffs[range_start] = addend;
                      } else {
                              diffs[range_start] += addend; 
                      }
      
                      if (!diffs[range_end + 1]) {
                              diffs[range_end + 1] = 0 - addend;
                      } else {
                              diffs[range_end + 1] -= addend;
                      }
              });
      
              return diffs.reduce((acc, cur) => {
                      return {
                              running_total: acc.running_total + cur,
                              max: Math.max(acc.max, acc.running_total + cur)
                      };
              }, {running_total: 0, max: 0}).max;
      }
      
      • + 0 comments

        My original solution was:

        function arrayManipulation(n, queries) {
          let array = []
          let maxArrayValue = 0
          let indices = queries
            .reduce((_indices, query) => {
              _indices.start = (_indices.start === undefined)
                ? query[0] - 1
                : (query[0] - 1 < _indices.start)
                  ? query[0] - 1
                  : _indices.start
              _indices.stop = (_indices.stop === undefined)
                ? query[1] - 1
                : (query[0] - 1 > _indices.stop)
                  ? query[1] - 1
                  : _indices.stop
              return _indices
            }, {
              start: undefined,
              stop: undefined,
            })
          for(var i = 0; i <= queries.length; i++) {
            let subArray = []
            for(var j = indices.start; j <= indices.stop; j++) {
              if(i === 0) {
                subArray[j - indices.start] = 0
              } else {
                if(
                  j >= queries[i - 1][0] - 1 &&
                  j <= queries[i - 1][1] - 1
                ) {
                  let additiveValue = queries[i - 1][2]
                  subArray[j - indices.start] = array[j - indices.start] + additiveValue
                } else {
                  subArray[j - indices.start] = array[j - indices.start]
                }
              }
              maxArrayValue = (maxArrayValue < subArray[j - indices.start])
                ? subArray[j - indices.start]
                : maxArrayValue
            }
            array = subArray
          }
          return maxArrayValue
        }
        

        It returns the correct answers, but times out on half of the tests.

        I did not consider that I could form an array with empty entries and populate it with the additive value at start/stop indices. That sped the processing time up enough to pass the timing tests. I ended up studying your solution the producing the same thing after understanding how it works. Thanks!

        With HackerRank solutions there is often an easy-to-read stepped solution that will pass tests with correct answers, but fail on timeouts with large numbers or sets of data. To avoid timeouts it is necessary to author solutions that are more considerate of data regardless of how easy-to-read.

        `

    • + 0 comments

      Superb thought

    • + 0 comments

      Amazing Approach !!

    • + 0 comments

      why did you put ((q+1)<=N) if condition in your code, shouldn't q+1 always be < N

    • + 1 comment

      I used same logic but first test case occurs runtime error: Exception in thread "main" java.lang.NumberFormatException: For input string: "" at java.lang.NumberFormatException.forInputString(NumberFormatException.java:65) at java.lang.Integer.parseInt(Integer.java:592) at java.lang.Integer.parseInt(Integer.java:615) at Solution.main(Solution.java:63)

      What should I do?

      • + 0 comments

        Paste your code.

    • + 0 comments

      Your code is so clean to understand the core logic behind that editorial solution. The editorial solution code is not clean because everything is hidden inside vector operations.

      By the way ı have just started to improve my algorithm skills. Can you give me a starting point or suggestion on it?

      Any firends? Thank you all...

    • + 1 comment

      how does it makes a difference if i first calculated array after all operations by adding to it its previous value and then finding the maximum value of that array in seperate loop, and by simply adding the value and checking it for maximum value ??

      i think both will take o(n).

      • + 0 comments

        hi,

        I am sure this comment will definately help you.

        https://www.hackerrank.com/challenges/crush/forum/comments/570284

    • + 0 comments

      This is the first time I comment in Hackerrank. Your approach is brilliant. Thank you for your sharing.

    • + 0 comments

      can anyone tell me whats wrong with this logic ,it passes 9 test cases but fails in others by saying doesnt execute within limits

      def arrayManipulation(n, q):
      arr = []
      for i in range(n):
          arr.append(0)
      for i in range(m):
          a = q[i][0]
          b = q[i][1]
          c = q[i][2]
          for j in range(a - 1, b):
              arr[j] = arr[j] + c
      print(max(arr))
      
    • + 0 comments

      dosn't work with this input: n=4 k=3

      2 3 603 1 1 286 4 4 882

    • + 0 comments

      just wow, brilliant solution, here is C++14 same code:

      vector arr;long max=numeric_limits::min();int s=queries.size();long j=0; for (unsigned int i=0;i<=n;i++) arr.push_back(0);

      for (unsigned int i=0;imax) max=j; }

      return max;

    • + 1 comment

      I've realized I had to make two sequential loops to avoid timeout for a nested loop (as I did in the first time :) ). But I could not figure out, how to do that - I thought I had to keep track of ALL elements from the very beginning... As the approach above shows, it's enough to mark just the beginning of the 'increasing' interval and 'decreasing' interval at the first stage. Storing negative values was a bit unexpectful to me - I doubt I would figure this out myself. On next stage we fill the rest of elements and at the same time looking for the max element... Smart. But I lost this tour... :(

      • + 0 comments

        Thankyou so much...

    • + 0 comments

      Very Brilliant !

    • + 0 comments

      My solution was similar but taking a bit less space. I think yours is not O(1) it is more like O(N) :-) So you are allocating up to 10MB.. I just used a map instead.

      long arrayManipulation(int n, vector<vector<int>> &queries) {
          map<long,long> changes;
          for (auto &q : queries) {
              changes[q[0]] += q[2];
              changes[q[1]+1] -= q[2];
          }
          long max=0, cur=0;
          for (auto &e : changes) {
              cur += e.second;
              if (cur > max)
                  max = cur;
          }
          return max;
      }
      
    • + 0 comments

      Brilliant

    • + 0 comments

      Hi Aman you can remove even N number of operations from your code. Just store those indicies in an array and perform the add operation.

    • + 0 comments

      I am always following this page in case of some difficulty. The page is very clearly explaining the topic with the help of the proper example and program. I can New York City Tours understand the array manipulation perfectly with the help of this page.

    • + 0 comments

      Brilliant

    • + 0 comments

      slightly more understandable variation of the solution (in python)

      arr = [0] * (n + 1)
      
      for query in queries:
          # where a represents the lower bound of the range,
          # and b represents the upper bound.
          a, b, k = query
          arr[a] += k
          try:
              arr[b+1] -= k
          except IndexError:
              pass
      
      max_val = running_sum = 0
      
      for delta in arr:
          # delta can be either positive or negative,
          # but in any case it is added to the running sum.
          # however max_val always contains the greatest sum so far
          running_sum += delta
          if max_val < running_sum:
              max_val = running_sum
      
      return max_val
      
    • + 0 comments

      thanks, this approach was really something. Best I was able to do this was in O(n2)

    • + 0 comments

      Mindblowing approach. Hats off to you man!!!!!!

    • + 0 comments

      tell me one thing, how does your brain thinks this solution, I thought this is the easiest and coded in 15 minutes, but failed in performance. Now I referred your code, it is mindblowing.

    • + 0 comments

      Awesome

    • + 0 comments

      JS implementation of your algorithm:

      const arr = [0];
      for (let i = 1; i <= n; ++i) arr[i] = 0;
      
      queries.forEach(query => {
          const [a, b, k] = query;
          arr[a] += k;
          if (b + 1 < arr.length) arr[b+1] -= k;
      });
      
      const {x, max} = arr.reduce((acc, current) => {
          acc.x += current;
          acc.max = Math.max(acc.max, acc.x);
          return acc;
      }, {x: 0, max: -Infinity});
      
      return max;
      
    • + 0 comments

      i tried ur soln but it failed most of the hidden test cases

    • + 0 comments

      Great solution! Your runtime is O(n + m) though, not O(n). Since m can be much bigger than n, it does make a difference.

    • + 0 comments

      what an idea bro. what do you eat? should share!!!

    • + 0 comments

      Very Clever!

    • + 0 comments

      hats off to you great approach

    • [deleted]
      + 0 comments

      Mind blown!

    • + 0 comments

      Holy crap.

    • + 0 comments

      Excellent approach. thanks for sharing

    • + 0 comments

      No way! I came up with the exact same solution. Though, I do admit it was on my second attempt. I did it the boring, slow way first and found out it was too slow. So I had to rethink the solution in terms of keeping track of the differences in values instead of trying to keep track of everything in the array. Good job beating me to it!

    • + 0 comments

      Explanation of the code:

      Each operation has to be applied to a range of values, i.e., to the values in array having indices starting from p to q. Here, in the first loop, the value to be added (sum variable) is added to the starting location p in the array, and the sum is subtracted from the ending location + 1, i.e., q + 1. In the second loop, the value added to the starting location gets added to successive locations, i.e., it gets added to p, p+1, p+2, .... until q, because each value that was added in the starting location using first loop, will be added to the variable x and therefore in effect gets added to subequent locations. But once the range ends, i.e., once you reach q+1, the sum that was added at starting location will be subtracted. This will subtract the sum value from the variable x in which the sum value was added at starting location p, meaning the addition of sum will only affect locations p to q.

      Example:

      If n=5 and operations are:-

      1 2 100
      2 5 100
      3 4 100
      

      Initial state of array (starting from index 1 until 5):-

      0 0 0 0 0
      

      Applying first operation

      • Add 100 (sum) at index 1 (p)
      • Subtract 100 (sum) from index 3 (q+1)

      Result

      100 0 -100 0 0
      

      Applying second operation - Add 100 (sum) at index 2 (p) - Do NOT subtract 100 (sum) from index 6 (q+1) since 6 is not lesser or equal to N (refer to code)

      Result

      100 100 -100 0 0
      

      Applying third operation - Add 100 (sum) at index 3 (p) - Subtract 100 (sum) from index 5 (q+1)

      Result

      100 100 0 0 -100
      

      If you start adding values from this array to a variable x, the point at which x is maximum is the answer because that is the point which will have the maximum value after applying the operations.

    • + 0 comments

      could you please differentiate between long int *a=new long intN+2; **and** long int a[N+2]={0}; ? 7 test cases are not passing using latter but passing when former is used.

    • + 0 comments

      could you please explain difference between long int *a=new long intN+2; and long int a[N+2]; ? 7 test cases are not passing when latter is used.

    • + 0 comments

      i am getting segmentation error for testcases 7,8,9,10,11,12,13. i ahve also implemented in same way.

    • + 0 comments

      Great approach bro. really thankful to know this

    • + 0 comments

      Absolutely brilliant!

    • + 0 comments

      I've tried my code, kept on getting timeout. Your solution, on the other hand, is the most brilliant one I've ever saw.

    • + 0 comments

      How this is O(1) space complexity ? You use additional array of size N+1

    • + 0 comments

      only 6 test cases are getting passed by this method

    • + 0 comments

      amansbhandari - thanks for the solution. It is elegant and works really fast:)

    • + 0 comments

      That's really wooowww

    • + 0 comments

      Your solution was really smart, but i have to undertand why you added the negative K (a[q+1]-=sum;) at the end of the interval and i have to mitigate the execution time finding the real range from n array and, at the moment of adding, avoid all the cero elements to performe the add (x=x+a[i]) and max comparation.

    • + 0 comments

      This solution was given long ago. But still , I find this logic amazing. so easy yet tricky. Thank you.

    • + 0 comments

      Brilliant dude to you.amzing algorithm.

    • + 0 comments

      You give me an excellent insight. Thank you

    • + 0 comments

      Python Code

      #### I Hope it Helps

      def arrayManipulation(n, queries):
          a = [0]*n
          maxx = 0
          x = 0
          for init, final, k in queries:
              if(k == 0):
                  continue
              a[init-1] += k
              if(final < n):
                  a[final] -= k
          for element in a:
              x += element
              if(maxx < x):
                  maxx = x
          return maxx
      
    • + 0 comments

      i tried same code in java but it is giving wrong answers for large values of n

    • + 0 comments

      Simply awesome !!!

    • + 0 comments

      Just another minor optimization that could be also done is post doing sum and negate , instead of running loop from 1 to N , by this time we would know min_index and max_index of queries , can run loop only for the same

    • + 0 comments

      This solution works like a charm! But what is the intuition behind it?

    • + 0 comments

      Amazing solution.

    • + 0 comments

      Can you plz name this algorithm, if any??? By the way, nice approach :)

    • + 0 comments

      wow brilliant but shouldn't it be a[p+1]+=sum; since a is 1-indexed array as per the question

    • + 0 comments

      This was helpful and a new concept for me. I just learned another way of thinking about the problem! Thanks dude!

    • + 0 comments

      Your solution is brilliant! Here is the same code in python :-

      def arrayManipulation(n, queries):

      temp=[0]*(n+1)
      
      for x in queries:
      
          temp[x[0]] += x[2]
          if((x[1]+1)<=n):
              temp[x[1]+1]-=x[2]
          print(temp)
      
      maxl =0
      x=0
      for i in range(n+1):
          x=x+temp[i];
          if(maxl<x):
              maxl=x
      
      return maxl
      
    • + 0 comments

      You are kidding about O(1) space right? Allocating O(N) space for this problem is completely unnecessary. Up to O(2 * m) is enough.

      It's like saying that you can sort any sequence of non-repeating numbers in O(N) time by "only" using O(MaxValue) space. Yes you can, but is it worth allocating Gigabytes for sorting 100 numbers?

    • + 0 comments

      f*king genius

    • + 0 comments

      This is very clever. I wasn't able to figure it out before I saw your solution. Hats off! Here is a solution in Python 3 which should do better for space and time complexity with the listed input constraints. I believe. I'm definitely welcome to disagreement! :D

      (n,m),D = map(int,input().split()),{}
      for _ in range(m):
          a, b, k = map(int,input().split())
          D[a-1] = D[a-1]+k if a-1 in D else k
          D[b] = D[b]-k if b in D else -k
      high = acc = 0
      for key in sorted(D.keys()):
         acc += D[key]
         high = max(high,acc)
      print(high)
      
    • + 0 comments

      nice approach sir , thanks a lot

    • + 0 comments

      Best solution right here. I was able to brute force it but a few test cases were failing. I implemented your aglorithm in Go and it works great. All test cases passing.

      func arrayManipulation(n int32, queries [][]int32) int64 {
          var max int64
          var arr = make([]int64, n)
          
          for _, q := range queries {
              a, b, k := q[0], q[1], int64(q[2])
      
              arr[a-1] += k
              if b < n { arr[b] -= k }
          }
      
          var sum int64
          for _, n := range arr {
              sum = sum + n
              if sum > max { max = sum }
          }
      
          return max
      }
      
    • + 0 comments

      Smart approach ! But its confusing why you took the array size as N+1, when N could do the job.

    • + 0 comments

      Can anyone help me if I use brute force method i get time complexity errors, but i modifiy the above code to c Test case 0 doesnt pass...

                          #include<stdio.h>
                          #include<stdlib.h>
      
      long int arrAddition(long a,long b, long k, long *arr)
      {
      
      long int max=-1000;
      for(long int i=a-1;i<b;i++)
      {
          arr[i]= arr[i]+k;
          if(max<arr[i])
          {
              max=arr[i];
          }
      }
      return max;
      }
      
      
      int main()
      {
              long long int n,m,x=0;
              long long int a,b,k;
              scanf("%lld %lld",&n,&m);
              long int *arr=(long*)malloc(n* sizeof(long));
              long int *arr1=(long*)malloc(m* sizeof(long));
              long int max1=0;
      
      
      for(long long int i=0;i<m;i++)
      {
          scanf("%lld", &a);
          scanf("%lld", &b);
          scanf("%lld", &k);
          //arr1[i]=arrAddition(a,b,k,arr);
      
          arr[a]+=k;
          if((b+1)<=n)
          {
              arr[b+1]-=k;
          }
      }
      for(long long int i=1;i<=n;i++)
      {
          x=x+arr[i];
          if(max1<x)
          {
              max1=x;
          }
      }
      
      /*
      for(long long int i=0;i<m;i++)
      {
          if(max1<arr1[i])
          {
              max1=arr1[i];
          }
      }
      */
      printf("%ld",max1);
      

      }

    • + 0 comments

      Sick Where I am And where you are I'm even feeling shame as a programmer.

    • + 0 comments

      Is this not O(n+k) time and O(n) aux space? Maybe I'm just not understanding C but doesn't this allocate an O(n) array:

      long int *a=new long int[N+1]();

    • + 0 comments

      This will not work for negative numbers

    • + 0 comments

      Great solution. Helped me solve my time issue. I had to make adjustments to the array size. If you have issues with 4 test cases after using this advice. Try doing:

      long int *a=new long int[N+2]()

      I am not sure where, but the array had some memory breaches even though it provided correct answer.

    • + 0 comments

      O(1) auxiliary space !!! wtf dude What about that "N" sized array you are creating dynamically???

      I don't think this question should need more than O(m) complexity (either space or time wise) Here's my approach:-

      long arrayManipulation(int n, vector> queries) {

      map<int, long> m;
      for(vector<int> i:queries)
      {
          int a=i[0], b=i[1];
          m[a]+=i[2];
          m[b+1]-=i[2];
      }
      long val=0, ans=0;
      for(pair<int, long> p : m)
      {
          val+=p.second;
          ans=max(ans, val);
      }
      return ans;
      

      }

    • + 0 comments

      But this isn't really O(1) auxilary space since you have to make in the array integers signed, which is the same as using n additional bits for sign

    • [deleted]
      + 0 comments

      Great logic .....

    • + 0 comments

      Instead of using letters (p,q,N, etc.) it's good to use meaningful variable names.

    • + 0 comments

      Your logic is really good. I programmed it in form of array and was getting segmentation fault but I'm not getting it when declaring array with new long int [n+1]. Can anyone tell the reason?

    • + 1 comment

      This is actually a very clever solution. Kudos.

      • + 0 comments

        thanks kevin for such a nice comment

    • + 1 comment

      amazing solution!!

      PS: Dont forget to delete the allocated memory on the heap by using delete[] at the end of the code....

      • + 0 comments

        for sure

    • + 0 comments

      Wow. Amazing Dude

    • + 0 comments

      my approach is also similar but i am getting segmentation fault in some test cases. please tell the problem.

      long arrayManipulation(int n, vector> queries) {

        long a[n]={0};
      for(int i=0;i<queries.size();i++)
      {
          a[queries[i][0]-1]+=queries[i][2];
          if(queries[i][1]<n)
          a[queries[i][1]]-=queries[i][2];
      }
      long ans=a[0];
      for(int i=1;i<n;i++)
      {
          a[i]+=a[i-1];
          ans=max(ans,a[i]);
      }
      return ans;
      

      }

    • + 0 comments

      i did the same thing, only difference was declaring the array as static and it gave segmentation fault while by using dynamic allocation it got passed. What's the reason?

    • + 0 comments

      It took me a minute to understand your approach. Basically your solution takes into account the fact the sections of the array where queries make the most additions will influence the output the most. There is no need to add a query to all elements in its range. It just needs to be added once at the start of its range. The array maximum value can be found among the elements where most of the queries made an addition or at an element with the largest added value.

    • + 0 comments

      brilliant logic

    • + 0 comments

      Pretty good, but one test case failed. Changing

      if((q+1)<=N) a[q+1]-=sum;

      to

      if((q+1)<=N + 1) a[q+1]-=sum;

      gets passed test case 1.

    • + 1 comment

      I tried to clone your solution in PHP but I get 8/16 on the test cases. Runtime error on the failed scenarios. I tested the same code on my pc and it goes smoothly, checked unlocking a failed test case and it succed. any hint? Here's my code:

      // Complete the arrayManipulation function below. function arrayManipulation(queries) { max = 0; n, 0); //$stderr = fopen("php://stderr", "w");

      foreach(`$queries as $`i => $query){
          `$a = $`query[0];
          `$b = $`query[1];
          `$k = $`query[2];
          if($a-1>=0){
              `$result_array[$`a-1] += $k;
          }
          else{
              var_dump(" a - 1 is negative! ".$a);
          }
          if(`$b < $`n){
              `$result_array[$`b] -= $k;
          }
          else{
              var_dump(" b is too big! ".$b);
          }
          //echo implode(" ", $result_array)."\n";
          //fwrite(`$stderr, implode(" ", $`result_array)."\n");
      }
      
      foreach(`$result_array as $`value){
          `$sum += $`value;
          `$max = max($`sum, $max);
      }
      //echo($max);
      //fwrite(`$stderr, $`max);
      //fclose($stderr);
      
      return $max;
      

      }

      $fptr = fopen(getenv("OUTPUT_PATH"), "w");

      $stdin = fopen("php://stdin", "r");

      fscanf(nm_temp); nm_temp);

      nm[0]);

      nm[1]);

      $queries = array();

      for (i < i++) { fscanf(queries_temp); queries_temp, -1, PREG_SPLIT_NO_EMPTY)); }

      n, $queries);

      fwrite(result . "\n");

      fclose(fptr);

      • + 0 comments

        they give you a and b. I chose to ignore the 1-based, 0-based issues and that was ok. for instance result_array[2] is just 2, not 2-1 or 2+1 to compensate for going back and forth between 0-based and 1-based. It passed all the tests, even though I hated doing it that way. The only other thing is, they give you a start index and an end index (a and b) and you need to consider: ADD at the start index and SUBTRACT just after the end index. so result_array[b+1] -= k. -- hope that helps.

    • + 0 comments

      Brilliant !!!!

    • + 0 comments

      Amazing approach and mind. To be able to add the slopes to get to a maximum in such a simple way of looking at it......after you had thought of it first. Now that I've viewed your solution I can't believe that I didn't think about that. Bravo!

    • + 0 comments

      Logic is Really very great. Thankyou so much sir

    • + 0 comments

      wow you are nuts

    • + 0 comments

      great!

    • + 0 comments

      Great solution. Instead of finding the maximum of the array, you found the maximum of addition and handled the range by subtracting the "sum" after the range is over. Brilliant thinking. Hats off!

    • + 0 comments

      amazing!!

      Python implimentation of this logic:

      def optimised(n, queries):
          intial = []
          _max = 0
          x = 0
          
          for _ in range(1, n+1):
              intial.append(0)
              
          for query in queries:
              intial[query[0]] += query[2]
              if query[1]+1 <= len(intial) - 1: intial[query[1]+1] -= query[2]
          
          for i in intial:
              x += i
              _max = max(x, _max)
          return _max
      
    • + 0 comments

      Great solution. Isn't the space complexity O(n)? Since you create an array of n elements how is the space complexity O(1)?

    • + 0 comments

      I think auxiliary space is O(K).

    • + 0 comments

      Beautiful

      , and thank you! It really broaden my perspective

    • + 0 comments

      Thanks for sharing the code. I would not have figured it otherwise.

    • + 0 comments

      How can this be O(1) space complexity if you allocate new array. This is O(n) space

    • + 0 comments

      This is a godly solution.

    • + 0 comments

      Sir, if u still using hackerrank and seeing my comment................ plssssssss tell how u came up with such an outstanding approach....... plsssssssssss telllll

    • + 0 comments

      Awesome!

    • + 0 comments

      Great work.

      Just to add (probably someone in comments whould have already done) Space Complexity is O(n) here.

    • + 0 comments

      I used the same method but instead of pointer I used array. I am getting 7 testcases failed but when i used pointer all testcases passed. Can anyone explain me what is the mistake or logic behind this.

    • + 0 comments

      if k<0, that is =, if k is negative, then will this same logic hold true?

    • + 0 comments

      The magic thing about this is that it's all about prefix-sum... Seriously, when i understood the logic i tought how funny and simple is that solution... That's why algorithms is so amazing to me.

      PS: To avoid the if in the q + 1 <= N just add 2 to the size of the array instead of 1.

    • + 0 comments

      Genius

    • + 1 comment
      [deleted]
      • + 0 comments

        thanks for the logic:

        long arrayManipulation(int n, vector<vector<int>> queries) {
        // the boundary extended by 2 since 0 th position is not used.
        vector<long int> map_vector (n+2,0); 
        long int max_value = 0, moving_sum = 0;
        for(auto rows : queries)
        {
            map_vector[rows[0]] += rows[2];
            map_vector[rows[1]+1] -= rows[2];
        }
        for(auto iter: map_vector)
        {
            moving_sum += iter;
            if(max_value < moving_sum)
                max_value = moving_sum; 
        }
        return max_value;
        }
        
    • + 0 comments

      We can imagine this solution as a climbing many mountains and finding the tallest mountain by climbing where more energy is needed to climb than downclimb. We need to sum height at every level of a mountain while only climbing. And in real we don't need to add while downclimbing(that is subtracted) till next mountain arrives. Real life problems are related to such problems. It may be the old technique to calculate heights of mountains. If you want to visualize as I say then create a bar chart for the A of the nxn solution.

    • + 0 comments

      Even though this is the optimal solution but this post fails to explain why this solution worked in the first place. I find below post helpful to understand the logic behind this solution: https://stackoverflow.com/a/48162313/1352962

    • + 0 comments

      Your approach is best for solving this question.....

    • + 0 comments

      Cool Honestly, I hardly figure that out. At least not in a single day.

      This is my JS version:

      function arrayManipulation(n, queries) {
          let arr = [], max = 0, x = 0
          arr.length = n+1
          arr.fill(0)
          for (let i = 0; i < queries.length; i++) {
              const a = queries[i][0]
              const b = queries[i][1]
              const k = queries[i][2]
              arr[a] +=k
              if ((b+1)<=n) arr[b+1]-=k;
          }
          for (let i = 1; i <= n; i++ ) {
              x = x + arr[i]
              if (x > max) max = x
          }
          return max
      }
      
    • + 0 comments

      That was seriously extraordinay to think that way!Respect++

    • + 0 comments

      You're a genius man

    • + 0 comments

      Your code works like a charm. But still unable to understand the logic behind it.

      specially the last part.

      If I do sum of only posive numbers of array then it fails most of the cases. But I do through for loop which I think is doing the same task passes all test.

    • + 0 comments

      I wasn't aware that new long[n+1]() will value initialise the array. Thanks.

    • + 0 comments

      Wow very good approach !!

    • + 0 comments

      where you have implimented this code and how much points did you got for this submission.

    • + 0 comments

      Awesome approach, thank you helping others learn and understand different approaches!

    • + 0 comments

      This is brilliant!!

    • + 0 comments

      I solved with same approch but it says time exceeded for some test cases. I could not understand.