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

Array Manipulation

Sort 2343 Discussions, By:

  • jeevanebi
     + 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

  • billones_kenllo1
     + 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 this

    arr = [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.

  • dream101221
     + 0 comments

    Here is the solution of Array manipulation Click Here

  • nxhao3003
     + 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;
    }

  • hellovansh
     + 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;
        
    }
Load more conversations