Add a value to each of the array element between two given indices successively

Question

I am trying to solve the HackerRank: Array Manipulation problem using Java.

The problem that I am facing is that the program is running for half of the test cases, while for the other half it is showing "Execution couldn't be completed because of Timeout". It seems like there is a more efficient way to do the problem such that the program is executed within the given time frame. If anybody could guide me regarding the issue, it would be of great help.

Problem description

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 n=10. 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 10 after all operations are performed.

Function Description

Complete the function arrayManipulation in the editor below. It must return an integer, the maximum value in the resulting array.

arrayManipulation has the following parameters:

• n - the number of elements in your array
• queries - a two dimensional array of queries where each queries[i] contains three integers, a, b, and k.

Input Format

The first line contains two space-separated integers \$n\$ and \$m\$, the size of the array and the number of operations.

Each of the next \$m\$ lines contains three space-separated integers \$a\$,\$b\$ and \$k\$, the left index, right index and summand.

Constraints

• \$ 3 \le n \le 10^7 \$
• \$ 1 \le m \le 2 \cdot 10^5 \$
• \$ 1 \le a \le b \le n \$
• \$ 0 \le k \le 10^9 \$

Output Format

Return the integer maximum value in the finished array.

My Solution:

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {

    // Complete the arrayManipulation function below.
    static long arrayManipulation(int n, int[][] queries) {

        int queryLength = queries.length;

        System.out.println(queryLength);

        long[] p = new long[n];
        int a = 0 , b = 0 , k = 0;

        long max=0; 

        // initialize p

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

        for(int i = 0 ; i < queryLength ; i++ )
        {
            a = queries[i][0];
            b = queries[i][1];
            k = queries[i][2];

            for(int j = (a-1) ; j <= (b-1) ; j++)
            {
                p[j] = p[j] + k ;
            }

        }

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

        return max;

    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        String[] nm = scanner.nextLine().split(" ");

        int n = Integer.parseInt(nm[0]);

        int m = Integer.parseInt(nm[1]);

        int[][] queries = new int[m][3];

        for (int i = 0; i < m; i++) {
            String[] queriesRowItems = scanner.nextLine().split(" ");
            scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

            for (int j = 0; j < 3; j++) {
                int queriesItem = Integer.parseInt(queriesRowItems[j]);
                queries[i][j] = queriesItem;
            }
        }

        long result = arrayManipulation(n, queries);

        bufferedWriter.write(String.valueOf(result));
        bufferedWriter.newLine();

        bufferedWriter.close();

        scanner.close();





    }
}

Answer 1

Some general remarks:

System.out.println(queryLength);

The function should only return the result, but not print anything.

int a = 0 , b = 0 , k = 0;

The initial values are not used, and variables should be declared at the narrowest scope, in this case, inside the loop:

for(int i = 0 ; i < queryLength ; i++ )
{
    int a = queries[i][0];
    int b = queries[i][1];
    int k = queries[i][2];
    // ...
}

Iterating over all queries can also be done with an “enhanced for loop”:

for (int[] query: queries)
{
    int a = query[0];
    int b = query[1];
    int k = query[2];
    // ...
}

Here

for(int j = (a-1) ; j <= (b-1) ; j++)

the parentheses are not needed, and this

 p[j] = p[j] + k ;

can be shortened to

p[j] += k ;

The initialization

// initialize p
for(int i = 0 ; i < n ; i++)
{
    p[i] = 0 ;
}

is not needed because all elements are initialised to 0 by default.

It might be a matter of personal preference, but I would always put horizontal space around operators and keywords, e.g. in

if(p[i]>max)

There are also some unneeded import statements, but those are given by the submission template.

---

But your real problem is that the algorithm is too slow. The inner loop runs up to \$ 10^{7} \$ times, for each of the up to \$ 2 \cdot 10^{5} \$ queries.

The main idea to improve the performance is to represent the data differently. Instead of storing and updating the array with the actual numbers, one can store and update an array which holds the differences between successive numbers.

Initially, all differences are zero.

Then for each query \$ (a, b, k) \$ you only have to update two entries in the differences array: One difference increases by \$ k\$, and one difference decreases by \$ k \$.

Finally you compute the actual numbers by accumulating the differences, and determine the maximum value.

This should be much faster, because the inner loop has been eliminated.

---

Let's take the given example with \$n = 10\$ and the queries

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

Instead of maintaining an array of the \$ n \$ numbers

index:             1  2  3  4  5  6  7  8  9 10
initial array:    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
after (1, 5, 3):  [3, 3, 3, 3, 3, 0, 0, 0, 0, 0]
after (4, 8, 7):  [3, 3, 3,10,10, 7, 7, 7, 0, 0]
after (6, 9, 1):  [3, 3, 3,10,10, 8, 8, 8, 1, 0]

we maintain an array of \$ n+1 \$ differences, where each entry \$ d[i] \$ holds the difference \$a[i+1] - a[i] \$:

index:             0, 1  2  3  4  5  6  7  8  9 10
initial diffs:    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
after (1, 5, 3):  [3, 0, 0, 0, 0,-3, 0, 0, 0, 0, 0]
after (4, 8, 7):  [3, 0, 0, 7, 0,-3, 0, 0,-7, 0, 0]
after (6, 9, 1):  [3, 0, 0, 7, 0,-2, 0, 0,-7,-1, 0]
final array:         [3, 3, 3,10,10, 8, 8, 8, 1, 0]

Do you see that only two entries are updated for each query? Can you figure out the pattern?

The final array is reconstructed by accumulating the final entries in the differences array.