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 whyarr[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 ofarr
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 is1
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
and5
in this element and that is the purpose ofcurrentNumber
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 is5 and 1
Third element is
-1
currentNumber = 5 -> add -1
This is where the negative plays an important role is informing thecurrentNumber
that the value1
stops here, and thus neutralizing thecurrentNumber
so now it becomes5
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 where10
should be added, but ourcurrentNumber = 5
since we haven't neutralized or in other words5
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