Array Manipulation — Interview Tips (HackerRank Hard)

Before we begin, the link to this problem is

Array Manipulation | HackerRank

The problem requires us to perform additions on an array in the index ranges given to us and return the maximum value that we come across while performing those operations. As you may have noticed we start off with an array initialized with zeros.

For example

5 3
1 2 100
2 5 100
3 4 100

For this input, we add add from index 1 ( actual index in the array : 0 ) to 2 (actual index in our array : 1) a 100. Then we add from actual 1 to 4 another 100, and again from actual 2 to actual 3 another 100. At 2 we have the maximum of 200, which is our answer.

But how do we go about solving this in code? We can definitely try the brute force technique which would look like

static long arrayManipulation(int n, int[][] queries) {
        long [] arr = new long [n];
        long max = Integer.MIN_VALUE;
        for(int i = 0; i < queries.length; i++){
            int a = queries[i][0];
            int b = queries[i][1];
            int add = queries[i][2];
            for(int j = a; j <= b; j++){
                arr[j-1] += add;
                max = Math.max(arr[j-1],max);
            }
        }
        return max;
    }

We are basically adding where we are told to the indexes we are told. One thing to note even in the brute force technique is that we keep long to store our sum and our max because we want to make sure we can handle the values a integer will not be able to store. The bold part of this algorithm repeats length of queries numbers of times leading to an exponential time complexity. So we must use a more efficient approach.

The question is how do we mark our array to know that those indexes need to have certain values after operations.

One of the approaches to solving this problem is the difference method. So what is a difference method?

For example, if we are given the following operations as input

5 3
2 5 100
3 4 100
1 2 100

We know that from array index 1 to 4 we must add 100, so instead of actually going through every element from 0 to 4, we mark the starting point a which is 1 as 100 added, and we mark the ending point as 100 subtracted. Now our array would look like

0 100 0 0 -100

Our second operation is adding 100 from 2 to 3, which would make our array look like.

0 100 100 -100 -100

Our last operation is 0 to 1 add 100.

100 0 100 -100 -100

Note that we are not directly putting the negative value but instead subtracting the value from the value that is already present and this would also be the same case with addition.

So where is the answer? We are going to have to do one last thing to get the maximum value, which is moving along our final array adding up every element and simply returning the max value we come across.

100 0 100 -100 -100
100
   100 
      200
           100
                0

So here 200 is our answer.

Why is a method like this working?

Imagine if all the input/ operations we had to perform were overlapped when needed and separated when needed and in sequential order. Then the HARD problem would simply be turned into an easy problem where we simply iterate through the array of operations and get our maximum value which is exactly what we are doing after we overlap and separate accordingly in the first part.

for(int i = 0; i < queries.length; i++){
   int a = queries[i][0];
   int b = queries[i][1];
   int add = queries[i][2];
   arr[a-1]+=add;
   if(b<n) arr[b]-=add;
}

This part simply marks our array as mentioned earlier. This converts our HARD problem to an easy one to which we do this.

for(int i=0;i<n;i++){
   temp += arr[i];
   if(temp> max) max=temp;
}
return max;

The full code looks like

static long arrayManipulation(int n, int[][] queries) {
   long [] arr = new long [n];
   long max = -1;
   long temp = 0;
   for(int i = 0; i < queries.length; i++){
      int a = queries[i][0];
      int b = queries[i][1];
      int add = queries[i][2];
      arr[a-1]+=add;
      if(b<n) arr[b]-=add;
   }
   for(int i=0;i<n;i++){
      temp += arr[i];
      if(temp> max) max=temp;
   }
   return max;
}

Thank you for reading!