Improvements in Algo/code for following HackerRank problem

Question

I'm aware, SO is not a place for homework and hence, being very specific to the scope of question.

I was trying to solve this problem on HackerRank: Array Manipulation - Crush. The problem statement is quite simple and I implemented following code:

function arrayManipulation(n, queries) {
  const arr = new Array(n).fill(0)
  for (let j = 0; j < queries.length; j++) {
    const query = queries[j];
    const i = query[0] - 1;
    const limit = query[1];
    const value = query[2];
    while (i < limit) {
      arr[i++] += value;
    }
  }
  return Math.max.apply(null, arr);
}

Now, it works fine for half the test-cases but breaks with following message: Terminated due to timeout for test-cases 7 - 13 as the time limit is 1 sec.

So the question is, what are the areas where I can improve this code. In my understanding, with current algo, there is not much scope (I may be wrong), so how can I improve algo?

---

Note: Not looking for alternates using array functions like .map or .reduce as for is faster. Also, using Math.max.apply(context, array) as it is faster that having custom loop. Attaching references for them.

References:

• How might I find the largest number contained in a JavaScript array?
• Javascript efficiency: 'for' vs 'forEach'

Answer 1

We could make some observations for this problem

• Let's keep a running sum representing the current value when we iterate from start to end of the array.
• If we break each operation into two other operation (a b k) -> (a k) and (b -k) with (a k) means adding k into the running sum at position a and (b -k) means subtracting k from the sum at position b.
• We could sort all of these operations by first their position, then their operator (addition preceding subtraction) we could see that we could always obtain the correct result.

Time complexty O (q log q) with q is the amount of queries.

Example:

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

we will break it into

(1 3) (5 -3) (4 7) (8 -7) (6 1) (9 -1)

Sort them:

(1 3) (4 7) (5 -3) (6 1) (8 -7) (9 -1)

Then go through one by one:

Start sum = 0 
-> (1 3)  -> sum = 3
-> (4 7)  -> sum = 10
-> (5 -3) -> sum = 7
-> (6 1)  -> sum = 8
-> (8 -7) -> sum = 1
-> (9 -1) -> sum = 0

The max sum is 10 -> answer for the problem.

My Java code which passed all tests https://ideone.com/jNbKHa

Answer 2

This algorithm will help.

https://www.geeksforgeeks.org/difference-array-range-update-query-o1/

Using this algorithm you can solve the problen in O(n+q) where n = size of the array and q = no of queries.

Answer 3

Why your brute force solution will not pass all test cases?

Today generation system can perform 10^8 operation in one second. keep this in mind you have to process N=10^7 input per query in the worse case. as you are using two nested for loops(one for adding K element and other for processing m queries) then the complexity of your solution is O(NM).

if you use your solution with O(NM) complexity it has to handle (10^7 *10 ^5)= 10^12 operation in worse case (which can not be computed in 1 sec at all)

That is the reason you will get the time out error for your brute force solution. So you need to optimise 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 4

I think the trick is not to actually perform the manipulations on arrays.

You can simply track the changes in index-intervals.

Keep a sorted list of intervals ( sorted by begin-index).

e.g. Input:       Internal representation
5 3               NOTHING TO DO
1 2 100           [1 2  value 100]
2 5 100           [1 1  value 100][2 2 value 200(100+100)][3 5  value 100]
3 4 100           [1 1  value 100][2 2 value 200(100+100)][3 4  value 200(100+100)][5 5  value 100]
                  as an optimization you could merge intervals with same value
                  ->  [1 1  value 100][2 4  value 200][5 5  value 100]

In the last step you iterate through your intervals and take the highest value.