Array Manipulation : HackerRank Questions : JAVA

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.

1 answer

  • answered 2019-05-22 06:33 Eran

    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.