# Array Manipulation

# Array Manipulation

+ 0 comments In cpp -:

# include

using namespace std;

const int N = 1e7+10; long long arr[N];

int main(){ int n,m; cin>>n>>m;

`while(m--){ int a,b,c; cin>>a>>b>>c; // prefix sum concept arr[a] += c; arr[b+1] -=c; } for(int i =1;i<=n;i++){ arr[i] += arr[i-1]; } long long max = -1; for(int i =1;i<=n;i++){ if(max<arr[i]){ max = arr[i]; } } cout<<max<<endl; return 0;`

}

+ 0 comments def arrayManipulation(n, queries): lst = [0 for i in range(n)] for x in queries: r1 = x[0]-1 r2 =x[1] val = x[2] for x in range(r1,r2): lst[x] += val return max(lst)

+ 0 comments def arrayManipulation(n, queries): arr = [0 for _ in range(n)] for a,b,k in queries: arr[a-1] +=k if b!=n: arr[b] -=k for i in range(1,n): arr[i]+=arr[i-1] return max(arr)

can anyone please help me find my error ??

+ 0 comments Python 3: I watched this : https://www.youtube.com/watch?v=4wqDE1zNUwc

from itertools import accumulate def arrayManipulation(n, queries): # Write your code here arr = [0 for _ in range(n)] for a, b, k in queries: arr[a-1] += k if b != n: arr[b] -= k return max(accumulate(arr))

+ 1 comment Logic for the original (get all the a,b,k values loop through updating for k, then repeat for other a,b,k values) makes sense and is my go to instinct, but as you can see nested for loops mean its O(N^2).

The refined took some figuring out the logic being that A,B,K mean A through B have all the same values (an increase of K). Therefore you do not need to loop to update through every single value. Instead you can use 1 loop to update the specific values A and B (adjusted for 1-index). A is an increase as once you start that range of indices you gain K. B is a decrease as after you leave taht range of indices you lose K in the indices after. Then a separate loop (not nested) to do a running sum to find the max value.

Refined Working

function arrayManipulation(n, queries) { let arr = new Array(n).fill(0); for(let query of queries) { let [a, b, k] = query; arr[a - 1] += k; arr[b] -= k; } let max = 0; let sum = 0; for(let elem of arr) { sum += elem; if(sum > max) { max = sum; } } return max; }

Original not working time complexity, nested for loops O(N^2)

function arrayManipulation(n, queries) { let arr = new Array(n).fill(0); for(let query of queries) { let [a, b, k] = query; for(let i = a - 1; i < b; i++) { arr[i] += k; } } return Math.max(...arr); }

Sort 2230 Discussions, By:

Please Login in order to post a comment