Optimal code for the array problem

[Monsterboy]

Homework Statement

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.

Relevant Equations

NA

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 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
queries - a two dimensional array of queries where each queries 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 lines m contains three space-separated integers a,b and k, the left index, right index and summand.

Output Format

Return the integer maximum value in the finished array.

Sample Input
5 3
1 2 100
2 5 100
3 4 100

Sample Output

200

Explanation

After the first update list will be 100 100 0 0 0 .
After the second update list will be 100 200 100 100 100 .
After the third update list will be 100 200 200 200 100 . The required answer will be 200.

I have attached a file with the problem statement. Have a look at it if the above is not clear

My solution:

My solution is in javascript.

// Complete the arrayManipulation function below.
function arrayManipulation(n, queries) {
   let arr = new Array(n).fill(0);
    for(let i=0; i<queries.length; i++) {
        for(let j=queries[i][0]; j<=queries[i][1]; j++) {
            arr[j-1] = arr[j-1] + queries[i][2]
        }
    }
    return Math.max.apply(null, arr);
}

I have tried to optimize it as much as I can but my code is unable to pass some tests because it is taking too much time, any help will be appreciated.

If interested checkout this website.

https://www.hackerrank.com/challenges/crush/problem

 

[Mark44]

// Complete the arrayManipulation function below.
function arrayManipulation(n, queries) {
   let arr = new Array(n).fill(0);
    for(let i=0; i<queries.length; i++) {
        for(let j=queries[i][0]; j<=queries[i][1]; j++) {
            arr[j-1] = arr[j-1] + queries[i][2]
        }
    }
    return Math.max.apply(null, arr);
}

A couple suggestions:
1. See if creating the array outside your function, and passing it as a parameter to the function might help. Your code has to call the Array constructor and its fill method before anything else happens.
2. You might save some time by replacing the call to Math.max.apply() by a for loop that iterates through the array looking for the largest value.

 

[Monsterboy]

A couple suggestions:
1. See if creating the array outside your function, and passing it as a parameter to the function might help. Your code has to call the Array constructor and its fill method before anything else happens.
2. You might save some time by replacing the call to Math.max.apply() by a for loop that iterates through the array looking for the largest value.

Okay, I did that, but it's not enough.
Even if I create that array of zeros outside the function, the statement still has to execute and it must be taking time. That function is not the only code that is running. There is some other code above and below it that I am not asked to edit.

I removed the Math.max.apply() and wrote what you suggested.

    let largest = arr[0]
    for(let i=0; i<arr.length; i++) {
        if(arr[i] > largest) {
            largest = arr[i]
        }
    }

Is there any other way to create array of zeros more efficiently, I am not sure if that is the main problem here.

 

[Ibix]

Can you tell me what is the value of arr[i]-arr[i-1] for some i in terms of the inputs?

 

[Monsterboy]

Can you tell me what is the value of arr[i]-arr[i-1] for some i in terms of the inputs?

Didn't get your question. The inputs to the function are the array length and the queries 2-d array.

 

[Ibix]

Let me ask another way. If you've run your algorithm and your array is populated, under what circumstances are two adjacent array elements the same? Under what circumstances are they different?

 

[Ibix]

Followup question: if I gave you an array, d whose ith element was the difference between the values you want in the ith and i-1th elements of arr, could you populate arr from that? And could you populate d from the answer to the question in the previous post?

 

[Monsterboy]

Let me ask another way. If you've run your algorithm and your array is populated, under what circumstances are two adjacent array elements the same? Under what circumstances are they different?

Well, if any two adjacent elements are undergoing the same operations(addition), their values remain the same.

 

[Ibix]

Concrete example: Given the input in your OP:

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

which elements of the final list are going to be different from the one immediately to their left? What will the differences be?

Hint: I know that element 1 will be different from (notional) element 0 and element 6 will be different from element 5. How do I know this?

 

[Mark44]

My solution is in javascript.

Is there a requirement that your implementation be in Javascript? Writing the code in a compiled language would produce much faster code.

 

[Monsterboy]

Concrete example: Given the input in your OP:

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

which elements of the final list are going to be different from the one immediately to their left? What will the differences be?

[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] --this is the final list

10th and 9th elements are different, difference is 1

9th and 8th elements are different, difference is 7

6th and 5th elements are different, difference is 2

4th and 3rd elements are different, difference is 7

I don't know where this is going.

Hint: I know that element 1 will be different from (notional) element 0 and element 6 will be different from element 5.

Well, the first two elements appear to be the same. element 5 and 6 are different, yes.

How do I know this?

I don't know.

 

[Monsterboy]

Is there a requirement that your implementation be in Javascript? Writing the code in a compiled language would produce much faster code.

There is a list of languages available, I don't know C or C++, do you think doing it in Java can be faster ?

 

[Mark44]

There is a list of languages available, I don't know C or C++, do you think doing it in Java can be faster ?

Compiled Java might be faster, as opposed to where the system interprets and runs the lines one at a time.

 

[Monsterboy]

Compiled Java might be faster, as opposed to where the system interprets and runs the lines one at a time.

Just tried it in Java it failed again, looks like they have set different time limits for different languages.

 static long arrayManipulation(int n, int[][] queries) {

        int arr[] = new int[n];
        for(int i =0; i< n; i++) {
            arr[i] = 0;
        }
        for(int i=0; i<queries.length; i++) {
            for(int j=queries[i][0]; j<=queries[i][1]; j++) {
                arr[j-1] = arr[j-1] + queries[i][2];
            }
        }
        // return Math.max.apply(null, arr);
        int largest = arr[0];
        for(int i=0; i<arr.length; i++) {
            if(arr[i] > largest) {
                largest = arr[i];
            }
        }
        return largest;
    }

I haven't written anything in Java for quite some time, not sure if the above code can be optimized further.

 

[Mark44]

I haven't written any Java for a long time, either (like 25 years), but I'll take a stab, using your code to start with.

static int arrayManipulation(int n, int[][] queries) {            // 1. changed return type

        int arr[] = new int[n];
        for(int i =0; i< n; i++) {
            arr[i] = 0;
        }
        int qLen = queries.length;                               // 2. added line
        for(int i=0; i<qLen; i++) {                                  // 3. modified
            for(int j=queries[i][0]; j<=queries[i][1]; j++) {
                arr[j-1] = arr[j-1] + queries[i][2];
            }
        }
        // return Math.max.apply(null, arr);
        int largest = arr[0];
        int aLen = arr.length;                                      // 4. added line
        for(int i=1; i<aLen; i++) {                                 // 5. modified in two places
            if(arr[i] > largest) {
                largest = arr[i];
            }
        }
        return largest;
    }

Here are brief explanations of my changes.
1. Changed return type of function to int from long. Not sure if that will make any difference time-wise.
2. Added a local variable qLen for the length of the queries. I assume this means the number of queries rather than the number of bytes in the whole string of queries.
3. qLen will be the same each iteration of the loop, so calculating queries.length in each iteration could possibly take more time than just comparing i and qLen. My reasoning is the the Java machine might need to load the address of queries, and then add whatever offset is necessary to find the value in length. This would be slower than just loading the address of qLen and getting the value there.
4. Add a local variable aLen.
5. Same reasoning as for item 3.

You don't show the rest of your code, so I can't tell whether there are opportunities for improvement in that part. Also, I don't know how the code submission goes, so I don't know what happens when you submit, say, Java code -- i.e., does that code get compiled or does it compile and execute lines one at a time. The latter option is much slower in comparison to compiling the whole program all at once into Java bytecodes, and then translating all the bytecodes into native machine code.

 

[Ibix]

The strategy I propose is to populate an array with the differences between adjacent elements of the result, then pass over the array once generating the final answer by cumulative sum. This should be faster than your approach, a lot faster if b-a is large for several operations.

So taking your original example:
a b k
1 5 3
4 8 7
6 9 1
I note that the first operation means that element 1 will be 3 higher than "element 0" and element 6 will be three less than element 5. So I populate my differences array with
3,0,0,0,0,-3,0,0,0,0
Note that this is only two writes to the array instead of five. Looking at the second operation I see elements 4 and 9 will be seven more and less (respectively) than 3 and 8, so I change my differences array to
3,0,0,7,0,-3,0,0,-7,0
Again, this is only two writes. Finally the last operation tells me to edit elements 6 and 10:
3,0,0,7,0,-2,0,0,-7,-1
Now I just need to work along this array generating the cumulative sum:
3,3,3,10,10,8,8,8,1,0
This requires ten writes. I can also keep track of the current maximum as I go.

This should be faster than your approach unless there are a lot of operations that only affect small ranges.

 

[sbrothy]

Compiled Java [..]

You mean compiled to bytecode, right? Or am I missing some context? I'm sure you're aware that Java is an interpreted language but perhaps that's not true for everyone..

EDIT: Ah, the terms are not as well-defined as I thought. My apologies.

https://en.m.wikipedia.org/wiki/Interpreted_language

 

[Mark44]

You mean compiled to bytecode, right?

Yes

 

[sbrothy]

I always understood compilation in C/C++ context. That is, to machine code. Embarrassing, as I'm (was, heh) actually a SUN certified Java programmer. In my defense it's been 10+ years. :)

 

[Monsterboy]

You don't show the rest of your code, so I can't tell whether there are opportunities for improvement in that part.

Actually, that is just boiler plate code present in every problem in the website. We are not expected to optimize anything there, I am just given an empty function and asked to complete it.

I don't know how the code submission goes, so I don't know what happens when you submit,

I don't know how it happens either, there is a 'Submit' button which we are supposed to click after writing the code and we can see the test results.

Let me try the solution given by Ibix and see if it works.

 

[Monsterboy]

So taking your original example:
a b k
1 5 3
4 8 7
6 9 1
I note that the first operation means that element 1 will be 3 higher than "element 0" and element 6 will be three less than element 5. So I populate my differences array with
3,0,0,0,0,-3,0,0,0,0
Note that this is only two writes to the array instead of five. Looking at the second operation I see elements 4 and 9 will be seven more and less (respectively) than 3 and 8, so I change my differences array to
3,0,0,7,0,-3,0,0,-7,0
Again, this is only two writes. Finally the last operation tells me to edit elements 6 and 10:
3,0,0,7,0,-2,0,0,-7,-1
Now I just need to work along this array generating the cumulative sum:
3,3,3,10,10,8,8,8,1,0
This requires ten writes. I can also keep track of the current maximum as I go

Thanks a LOT for the help ! It actually worked !

// Complete the arrayManipulation function below.
function arrayManipulation(n, queries) {
    let arr = new Array(n).fill(0);
    let queryLen = queries.length
    let arrLen = arr.length
    for(let i=0; i<queryLen; i++) {
        arr[queries[i][0]-1] += queries[i][2]
        if(queries[i][1] < arrLen) {
            arr[queries[i][1]] -= queries[i][2]
        }
    }
    for(let i=1; i<arrLen; i++) {
        arr[i] = arr[i] + arr[i-1]
    }
    let largest = arr[0]
    for(let i=1; i<arrLen; i++) {
        if(arr[i] > largest) {
            largest = arr[i]
        }
    }
    return largest
}

I would like to know how you figured out this solution, is this some kind of a standard algorithm or something ? i.e you know...taking the differences and all that. It's not intuitive is it ?

 

[Ibix]

I would like to know how you figured out this solution, is this some kind of a standard algorithm or something ?

It was an approach I knew from having solved more or less exactly this problem in the real world. The idea that a function $f(t)$ can also be expressed as its derivative $f'(t)$ plus an initial value is absolutely standard, but I honestly don't recall how I came to think of applying it to this problem. I do recall I initially used your method but it was slow. I think that I was just thinking around the problem - are there related problems I could solve quickly? Yes - writing down the element-by-element changes would be much faster because the inner loop is gone. Does that help me? Ah ha!

So I guess the only advice I can really offer is to remember that there's often more than one way to solve a problem, and solving a related problem can be a building block for doing your original problem. That's very vague, I'm afraid.