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...
  1. Practice
  2. Data Structures
  3. Arrays
  4. Array Manipulation
  5. Discussions

Array Manipulation

  • jricaldi + 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".

    • mvanwoerkom + 0 comments

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

    • kemal_caymaz + 7 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.

      • krishnna + 1 comment

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

        • tejaspatil + 1 comment

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

          • codam + 7 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;
            • kamnijais + 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?

              • h1017691668 + 0 comments

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

            • mevtew + 1 comment

              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;

              }

              • Rockyfive + 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;
                • susahin80 + 1 comment

                  This produces wrong answer in some of the tests.

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

            • jpeavey451 + 0 comments

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

            • lyons_mr + 0 comments
              [deleted]
            • tyler_e_austin + 0 comments
              [deleted]
            • tyler_e_austin + 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;
};
            • shubhanksrivast1 + 0 comments

              Got stuck because of this

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

              Thanks man!

      • dawar_dhawal + 0 comments

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

      • VE5T1GE + 0 comments

        Thank you!

      • prashant_kumar_3 + 0 comments

        thnx

      • rohanmehta0077 + 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.

        • Kanahaiya + 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.

          • marwan_daar + 1 comment

            fantastic video, thank you!

            • Kanahaiya + 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.

          • naimulhaquesagar + 0 comments

            impressive ...

      • bhavyseth + 0 comments

        thanks bro..

      • Kanahaiya + 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.