We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Loading...
  • Practice
  • Compete
  • Jobs
  • Leaderboard
  • Hiring developers?
  1. Practice
  2. Data Structures
  3. Arrays
  4. Array Manipulation
  5. Discussions

Array Manipulation

  • Problem
  • Submissions
  • Leaderboard
  • Discussions
  • Editorial

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

  • Jeff_Chung123 2 years ago+ 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);
    
    }
    
    0|
    ParentPermalink
    • ali_sid_jobs 2 years ago+ 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

      38|
      ParentPermalink
      • mvanwoerkom 2 years ago+ 1 comment
        [deleted]
        1|
        ParentPermalink
        • mvanwoerkom 2 years ago+ 0 comments
          [deleted]
          0|
          ParentPermalink
      • smaaash 2 years ago+ 0 comments

        Thanks a lot!!That really helped!

        0|
        ParentPermalink
      • agarwal_akshara9 2 years ago+ 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|
        ParentPermalink
        • Kanahaiya 8 months ago+ 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|
          ParentPermalink
        • Kanahaiya 8 months ago+ 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.

          0|
          ParentPermalink
          • ckybonist 8 months ago+ 1 comment

            I've add it to my playlist

            -1|
            ParentPermalink
            • Kanahaiya 8 months ago+ 0 comments

              haha..thank you.

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

              0|
              ParentPermalink
      • ozgur24 2 years ago+ 3 comments

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

        0|
        ParentPermalink
        • hn5624 2 years ago+ 0 comments

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

          0|
          ParentPermalink
        • rohitshende16 2 years ago+ 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|
          ParentPermalink
        • Kanahaiya 8 months ago+ 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|
          ParentPermalink
      • hn5624 2 years ago+ 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.

        20|
        ParentPermalink
        • blunderblunder67 1 year ago+ 0 comments

          can you explain ? :)

          0|
          ParentPermalink
    • asimparvez91 1 year ago+ 0 comments

      Very well explained (Y)

      0|
      ParentPermalink
  • Contest Calendar
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature