# Array Manipulation

# Array Manipulation

+ 0 comments Python 3: You can solve this problem efficiently by using a technique called "prefix sum" or "cumulative sum

def arrayManipulation(n, queries): arr = [0] * (n + 1) for query in queries: a, b, k = query arr[a - 1] += k arr[b] -= k max_value = 0 current_sum = 0 for value in arr: current_sum += value max_value = max(max_value, current_sum) return max_value

+ 0 comments Java solution I just copied on what the idea from others as my solution is slow. After studying and understanding here's what I understand on this solution.

1 public static long arrayManipulation(int n, List<List<Integer>> queries) { 2 long[] arr = new long[n + 2]; 3 for(int i = 0; i < queries.size(); i++){ 4 int startIndex = queries.get(i).get(0); 5 int endIndex = queries.get(i).get(1); 6 int value = queries.get(i).get(2); 7 8 arr[startIndex - 1] += value; 9 arr[endIndex] -= value; 10 } 11 long currentNumber = 0; 12 long max = 0; 13 for(int i = 0; i < arr.length; i++){ 14 currentNumber += arr[i]; 15 max = currentNumber > max ? currentNumber : max; 16 } 17 return max; 18 }

Idea and Concept: 1. Just like the common and longer solution, still create an array to determine the highest number. 2. Instead of looping through the start and end indexes, we approach a different method using the start and end only leaving the middle indices 0 3. Let's explain the concept of why

`arr`

plays a significant role:To fully understand let's follow the given values similar to case 0: n = 5 queries = [[1, 2, 1], [2, 5, 5], [4, 5, 10]]

before the first loop, the arr would be like this:

arr = [0, 0, 0, 0, 0, 0, 0];// [n + 2] = 7

After first loop what happens will be like this:

arr = [1, 0, -1, 0, 0, 0, 0];

since what we does is get the

`a`

then make it as base-0 array that's why`arr[startIndex - 1]`

The question is why is there a negative value and on top of it it's supposed to be on the first and second index (

`[1, 2, 1]`

), I'll explain later. Let's wrap up the final value of`arr`

after the whole loop, which would look like thisarr = [1, 5, -1, 10, 0, -15, 0];

For the second part, this is where everything makes sense, the idea is like this:

There should be a variable (

`currentNumber`

) that will scan over each element and the purpose of it is to determine and add together the numberes and determine the highest number. First element is`1`

now ```currentNumber``` will remember that starting this part of the array, there is always a value of ```1``` Second element is ```5```

base on the query there is

`1`

and`5`

in this element and that is the purpose of`currentNumber`

to remember that this is the total on to where the value is supposed to be added.So as of now the highest value is

`6`

which is`5 and 1`

Third element is

`-1`

`currentNumber = 5 -> add -1`

This is where the negative plays an important role is informing the`currentNumber`

that the value`1`

stops here, and thus neutralizing the`currentNumber`

so now it becomes`5`

which is still part of the second query`[2, 5, 5]`

And so on, until you reach the 4th element which is

`10`

, base on the query this is where`10`

should be added, but our`currentNumber = 5`

since we haven't neutralized or in other words`5`

is still should be there, therefore you add the two which will be our highest number.There are far more better ways to explain this, but this is for now.

+ 0 comments Here is the solution of Array manipulation Click Here

+ 0 comments java 8

public static long arrayManipulation(int n, List<List<Integer>> queries) { long[] answer = new long[n + 2]; long maxSum = Long.MIN_VALUE; for (int i = 0; i < queries.size(); i++) { int a = queries.get(i).get(0); int b = queries.get(i).get(1); int k = queries.get(i).get(2); answer[a - 1] += k; answer[b] -= k; } long currLong = 0L; for (int i = 0; i < answer.length; i++) { currLong += answer[i]; maxSum = Math.max(currLong, maxSum); } return maxSum; }

+ 1 comment public static long arrayManipulation(int n, List<List<Integer>> queries) { // Write your code here long[] res = new long[n+2]; long max = 0; for(int i=0; i<queries.size(); i++){ int a = queries.get(i).get(0); int b = queries.get(i).get(1); int k = queries.get(i).get(2); res[a] = res[a] + k; res[b+1] = res[b+1] - k; } for(int i=1; i<=n; i++){ res[i] = res[i] + res[i-1]; max = Math.max(res[i], max); } return max; }

Sort 2343 Discussions, By:

Please Login in order to post a comment