Array Manipulation : HackerRank Questions : JAVA

Question

I am doing this Array Manipulation problem from hackerrank and it tells me compile error is Terminated due to timeout.

For small arrays my method work perfectly. This error only happens for bigger array values.

Here is the question link. Question Here

Starting with a 1-indexed array of zeros and a list of operations, for each operation add a value to each of the array element between two given indices, inclusive. Once all operations have been performed, return the maximum value in your array.

For example, the length of your array of zeros . Your list of queries is as follows:

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

Add the values of between the indices and inclusive:

index -> 1 2 3  4  5 6 7 8 9 10
        [0,0,0, 0, 0,0,0,0,0, 0]
        [3,3,3, 3, 3,0,0,0,0, 0]
        [3,3,3,10,10,7,7,7,0, 0]
        [3,3,3,10,10,8,8,8,1, 0]

The largest value is after all operations are performed.

Given below is my method.

 static long arrayManipulation(int n, int[][] queries) {
    long max = 0L;
    long[] arr = new long[n];
    for (int i = 0; i < n; i++) {
        arr[i] = 0L;
    }
    for (int i = 0; i < queries.length; i++) {
        int[] q = queries[i];
        int start = q[0] - 1;
        int end = q[1] - 1;
        int val = q[2];
        long tempMax = updateVal(start, end, val, arr);
        if (tempMax > max) {
           max = tempMax;
        }
    }
    return max;
 }



static long updateVal(int start, int end, int val, long[] arr) {
   long max = 0L;
   for (int i = start; i <= end; i++) {
       arr[i] = arr[i] + val;
       if (arr[i] > max) {
           max = arr[i];
       }
   }
   return max;
}

Given below are few test classes that doesn't work with my code.
Test1 Test2 Test3

Please help me to figure this out. I searched for lots of answers based on java.
But I couldn't understand them.
This is my last resort. Please help.

Updated after Kanahaiya's answer

    static long arrayManipulation(int n, int[][] queries) {
        long max = 0L;
        int a, b, k;
        int[] arr = new int[n + 2];
        for (int i = 0; i < queries.length; i++) {
            a = queries[i][0];
            b = queries[i][1];
            k = queries[i][2];

            for (int j = 0; j < arr.length; j++) {
                if (j >= a) {
                    arr[j] = arr[j] + k;
                }
                if (j > b) {
                    arr[j] = arr[j] - k;
                }
            }
        }
        Arrays.sort(arr);
        max = arr[arr.length - 1];
        return max;
    }

Answer 1

Brute-force solution is not going to work here due to the given time constraint. That is the reason you will get the time out error.

So you need to optimize your code which can be done with the help of prefix sum array.

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

     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. 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 2

First of all, in case you don't realize it, Terminated due to timeout is not a compilation error, it means that your implementation is too slow. The challenge is not to implement any correct solution to the problem. The solution must also be efficient. Since your solution is inefficient, it fails for large inputs due to being too slow.

Since the number of queries seems to be 2 orders of magnitude smaller than the length of the array (100K vs. 10M in the 3 test cases you posted), it would be more efficient to work just with the queries instead of actually updating the array.

I'm not going to give you an implementation, but I'll suggest an algorithm that should be more efficient than your current implementation.

I suggest you process the queries as follows:

1. Add the first query to a list of processed queries, which will contain queries with disjoint sub-array ranges. This list will be sorted by the first array index (you will keep it sorted by adding new elements in the proper position).

2. For each query not processed yet, find all the processed queries that overlap it (you can do it using binary search to improve performence).

   • Split the current query in a way that the resulting queries will each be either fully contained in an existing processed query or not contained in each existing processed query.

   • For each of the queries created in the split:

     • if their range is equal to the range of an existing processed query, add the value of the query to the processed query.
     • If their range is not contained in any existing processed query, add that query as a new processed query.
     • If their range is partially contained in an existing processed query, split the processed query.

I'm not sure if my explanation is clear enough. I'll show an example with the

1 5 3
4 8 7
6 9 1

input:

Add 1 5 3 to the list of processed queries.

Process 4 8 7: There is one processed query the overlaps it - 1 5 3.

Split 4 8 7 into two sub-queries : 4 5 7 and 6 8 7.

4 5 7 is contained in 1 5 3, so split 1 5 3 into 1 3 3 and 4 5 3+7

6 8 7 is not contained in any processed queries, so add it as is.

Now the processed queries are:

1 3 3
4 5 10
6 8 7

Process 6 9 1: There is one processed query that overlaps it: 6 8 7.

Split 6 9 1 into two sub queries : 6 8 1 and 9 9 1.

6 8 1 has the same range a 6 8 7, which will become 6 8 7+1

9 9 1 is not contained in any processed queries, so add it as is.

Now the processed queries are:

1 3 3
4 5 10
6 8 8
9 9 1

As you process the queries you keep track of the max processed query value, so after you process all the queries you know that the max value is 10.