Logic used behind Array Manipulation of HackerRank

Question

I am not able to grasp the logic behind the solution of this problem of Hackerrank, https://www.hackerrank.com/challenges/crush/problem

In the discussion section, many have posted their solutions as well but I am unable to understand why that logic works.

The below solution is taken from the discussion section of the same problem and has maximum number of upvotes,

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    long int N,K,p,q,sum,i,j,max=0,x=0;

    cin>>N>>K;
    long int *a=new long int[N+1]();

    for(i=0;i<K;i++)
    {
        cin>>p>>q>>sum;
        a[p]+=sum;
        if((q+1)<=N) a[q+1]-=sum;
    }

    for(i=1;i<=N;i++)
    {
       x=x+a[i];
       if(max<x) max=x;

    }

    cout<<max;
    return 0;
}

Could someone please explain the logic behind the same? Thanks a ton for your help.

Answer 1

Before solving this problem you must know Prefix Sum Array & Difference array.

Consider below case

a b k
1 5 3
4 8 7
6 9 1 

If we calculate original array 'A' from this it will be

[3,3,3,10,10,8,8,8,1,0]

Now, lets find out the difference array 'D(A)' [3,0,0,7,0,-2,0,0,-7,-1]

Follow below steps & calculate the array

A[a] += k
A[b+1] -= k , b+1 < len(A)

you will get [3,0,0,7,0,-2,0,0,-7,-1] which is D(A) itself.

P(0, D(A)) = A. i.e. calculate prefix sum array of D(A). you will get the original array.

[3,3,3,10,10,8,8,8,1,0]

return max

Answer 2

The brute force approach requires us to iterate over the array and add the value to every element in the range a to b.

Instead of looping every time, what we can do this, we add the value at indexing a and subtract it from indexing b+1. And in the end we add it like a prefix array from left to right.

So what happens essentially is the value we add gets reflected from a to b. And as we subtract the same value from b+1, it won't be reflected after indexing b.

And this algorthm runs in O(n+m).

If you have any doubts regarding the explanation, you may watch this video which very nicely explains the algorithm and helps in better understanding by dry running the algo on few test cases. Just a 7 min video :).

Link : https://youtu.be/JtJKn_c9lB4

Answer 3

It is using the concept of Array Difference. It's a new concept to add value to a given range (i,j,k). i and j specify the range and k is the value to be added. It will be much helpful if you check the link. https://www.geeksforgeeks.org/difference-array-range-update-query-o1

Answer 4

We are basically storing the increment in the starting position and one past the last index in the range. For a b k we will increase +k for all elements in index [a,b] but then the next elements will not be increased. So we are subtracting it, because w.r.t the previous increment all elements to the right of the range will be lesser by -k. We are basically storing all the final values via this increment/decrement.

At last we are calculating the elements on the fly from left to right. If you think more deeply, it is just storing how much one element is bigger than the previous element.

Initially the array will be 0 0 0 0 0.

After the first operation 1 3 3 originally the array elements should be 3 3 3 0 0 but we are storing it like this

3 0 0 -3 0

Meaning

First element is 3 greater than 0.
Second  ->       0 greater than index 1 element.
Third   ->       0 greater than index 2 element
Fourth  ->      -3 greater than index 3 element.
fifth   ->       0 greater than index 4 element.

After the second operation 2 4 4 originally the array will be 3 7 7 4 0 but we store it like this 3 4 0 -3 -4. Just like I described in detail keep in mind that and think that way, you will see that we are not losing information. We just store it in a different way.

Final values will be

0+(3) 0+3+(4) 0+3+4+(0) 0+3+4+0+(-3) 0+3+4+0-3+(-4)

3  7    7       4           0  matches with what we got earlier.

Note how we calculate each element. Just adding previous element with the value by which current element is greater.

---

Note that this solution works because it is being queried only once. If it is queried m times, then this solution doesn't work because it will time out. Then you will have to dig deeper using advanced data structures like segment trees and/or binary indexed trees.

Answer 5

instead of adding k to all the elements within a range from a to b in an array, accumulate the difference array

Whenever we add anything at any index into an array and apply prefix sum algorithm the same element will be added to every element till the end of the array.

ex- n=5, m=1, a=2 b=5 k=5

    i     0.....1.....2.....3.....4.....5.....6   //take array of size N+2 to avoid index out of bound
  A[i]    0     0     0     0     0     0     0

Add k=5 to at a=2

A[a]=A[a]+k // start index from where k element should be added similar to a[p]+=sum;

     i    0.....1.....2.....3.....4.....5.....6 
   A[i]   0     0     5     0     0     0     0

now apply prefix sum algorithm

     i    0.....1.....2.....3.....4.....5.....6 
  A[i]    0     0     5     5     5     5     5

so you can see K=5 add to all the element till the end after applying prefix sum but we don't have to add k till the end. so to negate this effect we have to add -K also after b+1 index so that only from [a,b] range only will have K element addition effect.

A[b+1]=A[b]-k // to remove the effect of previously added k element after bth index.(same as a[q+1]-=sum;) that's why adding -k in the initial array along with +k.

    i    0.....1.....2.....3.....4.....5.....6 
  A[i]   0     0     5     0     0     0    -5

Now apply prefix sum Array

    i    0.....1.....2.....3.....4.....5.....6 
  A[i]   0     0     5     5     5     5     0

You can see now K=5 got added from a=2 to b=5 which was expected. Here we are only updating two indices for every query so complexity will be O(1).

Now apply the same algorithm in the input

         # 0.....1.....2.....3.....4.....5.....6    //taken array of size N+2 to avoid index out of bound
5 3      # 0     0     0     0     0     0     0
1 2 100  # 0    100    0   -100    0     0     0       
2 5 100  # 0    100   100  -100    0     0   -100
3 4 100  # 0    100   100    0     0  -100   -100

To calculate the max prefix sum, accumulate the difference array to 𝑁 while taking the maximum accumulated prefix.

After performing all the operation now apply prefix sum Array

    i      0.....1.....2.....3.....4.....5.....6 
  A[i]     0     100   200  200   200   100    0

Now you can traverse this array to find max which is 200. traversing the array will take O(N) time and updating the two indices for each query will take O(1)* number of queries(m)

overall complexity=O(N)+O(M) = O(N+M)

it means = (10^7+10^5) which is less than 10^8 (per second)

Note: If searching for video tutorial , you must check it out here for detailed explanation.

Answer 6

The following code worked for me in C++. I took some help online and then coded it.

long arrayManipulation(int n, vector<vector<int>> queries) {
  vector<long> resultVector(n);
  long maxVal=0, x=0, i;

  for(int i = 0; i<n ; i++)
  {
      resultVector[i]=0;
  }

  for(i=0; i<queries.size(); i++)
  {
      resultVector[(queries[i][0])-1] += queries[i][2];

      if((queries[i][1]) <= n)
      {
          resultVector[(queries[i][1])] -= queries[i][2];
      }
  }

  for(i=0; i <n; i++)
  {
      x+=resultVector[i];
      if(x>maxVal)
      {
          maxVal=x;
      }
  }

  return maxVal;
}

Answer 7

These two places helped me to understand this algorithm more clearly. Prefix_sum_array_and_difference_array
Stack Overflow

If you want a simple and direct explanation: Initial, the array is 0 0 0 0 0 cpp after the first operation, 1 2 100 it will become seq1: 100 100 0 0 0 and after second 2 5 100 seq2: 0 100 100 100 100 and after 3 4 100 seq2: 0 0 100 100 0 but when we apply difference array at every step, we will get

cpp diff seq of seq1: 100 0 -100 0 0 diff seq of seq2: 0 100 0 0 0 -100 diff seq of seq3: 0 0 100 0 -100

One important property is the difference sequence of the sum of the sequences is the sum of the difference sequences.

it will give us, cpp 100 100 0 0 -100 -100(for clarity purpose only) or you can add all the sequences as cpp seq1+seq2+seq3 = 100 200 200 200 100 and then find the difference seq or the difference array which is 100 100 0 0 -100 and then find the prefix array.

Why we ignore the first 100??? Read the first article about difference array and prefix sum array!!!!

and after this, do prefix sum cpp 100 200 200 200 100 0 Ignore last 0 as the last index we considered is for clarity purpose only.

so,both these steps find the difference array for us:) cpp a[p]+=sum; if((q+1)<=N) a[q+1]-=sum;

Answer 8

I'll try to explain my understanding of this:
Each line of input basically describes a sequence, and you are asked to find the maximum value of the sum of these sequences.
For example, if N is given as 5:
the line 2 4 13 describes the sequence [0, 13, 13, 13, 0]
the line 3 5 11 describes the sequence [0, 0, 11, 11, 11].
If those are the only lines we get the result sequence from the pointwise sum of the two, which is [0, 13, 24, 24, 11].

Now another way we can describe the sequences above are by the difference sequences, that is, at index i we will keep the difference between the element at index i and the element at index i-1, and we can get the original sequence by a running sum of the difference sequence.

In the case of the above sequences, the difference sequences are:
[0, 13, 0, 0, -13] for the sequence described by 2 3 13
[0, 0, 11, 0, 0] for the sequence described by 3 5 11
[0, 13, 11, 0, -13 for the sum of the sequences.

One important property is the difference sequence of the sum of the sequences is the sum of the difference sequences.

So what the solution does, for every line, is to sum the difference sequences (which only requires up to 2 operations due to the nature of the sequences), then to find the maximum it takes the running total of the difference sequence, thus getting the elements of the sequence, and holds the maximum value of that running total.

While the example I gave has only 2 lines, this same idea works for any number of lines.

I hope this gives good intuition as to the idea behind the solution.