-4

Just as the title says. I'm currently working on a challenge that includes long variables in its test cases, and my solution takes too long to run. Here's the function in question:

long arrayManipulation(int n, vector<vector<int>> queries) {
    vector<long> final_vector(n, 0);
    for(int q = 0; q < queries.size(); q++){ 
        for(int index = queries[q][0]-1; index < queries[q][1]; index++){
            final_vector.at(index) += queries[q][2];
        }
    } 
    
    long max = 0;
    for(long intElement: final_vector){
        if(intElement > max){
            max = intElement;
        }
    }
    
    return max;
}

This solution to the problem takes too long. What should I change or do instead?

ins0m
  • 1
  • 1
  • you dont need an array in the first place. All you need is to find the maximum number in a hyptothetical array as if you had applied the operations. No need to actually apply the operations – 463035818_is_not_an_ai Jul 21 '23 at 07:28
  • 2
    When such a site tells you that your program takes too long, then you simply don't use the correct "trick". Basically you're using the wrong algorithm. – Some programmer dude Jul 21 '23 at 07:32
  • I'm sorry, but could you explain further? I'm not quite sure what you mean. – ins0m Jul 21 '23 at 07:33
  • The only problem is that the correct "trick" isn't really human friendly usually. As per this case. I'm not sure how many persons in the real world would apply the correct solution to this problem. Anyway, for these questions you could go in the discussion tab on that site and search for explanation. Usually is there. – Federico Jul 21 '23 at 07:34
  • someone forces you to copy a potentially big vector and then complains that your function is too slow, thats silly – 463035818_is_not_an_ai Jul 21 '23 at 07:34
  • 1
    questions should be selfcontained. All information should be in the question. – 463035818_is_not_an_ai Jul 21 '23 at 07:36
  • One thing that could help would be to pass `queries` as a constant reference, as hinted to by @463035818_is_not_an_ai. – Some programmer dude Jul 21 '23 at 07:37
  • I'll look into your suggestions. Also apologies to @463035818_is_not_an_ai. I'm not too familiar with the conventions here as I'm new. Thank you, I will keep this in mind for further questions – ins0m Jul 21 '23 at 07:41
  • you dont have to keep it in mind for further questions you can [edit](https://stackoverflow.com/posts/76735929/edit) this question – 463035818_is_not_an_ai Jul 21 '23 at 07:43
  • 3
    its not your way of handling the array that is inefficient. For an implementation of a brute force algorithm your code looks fine. The problem is not in your code but in your way of approaching the task. Frankly, the fact that you wrote a brute force and wonder why it is too slow suggests that you think this challenge would be about practicing 2d vectors and loops. But this challange is not about learning c++, it is about finding a trick. C++ is not learned from coding challenges, but from courses and [books](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list). – 463035818_is_not_an_ai Jul 21 '23 at 07:49
  • 1
    @ins0m - The "challenge" only asks for the maximum value, so there must be a way to compute that *without* storing all the other values. That makes it a Math problem, and not a C++ problem. So now you learn math and not coding. – BoP Jul 21 '23 at 08:24
  • Using a nested `vector` is very inefficient, especially for regular (not jagged) 2D data, i.e. a matrix. You basically want to flatten the data into `vector` and use lexic indexing. This is why C++23 added `std::mdspan` which makes it easier to use linear memory for multidimensional data. I.e. the fact that the challenge uses that data layout is yet another indication that these challenges promote bad practices. – paleonix Jul 21 '23 at 12:47

1 Answers1

1

Your code is ok for the chosen approach (passing the vector by value to the function aside). Your approach is inefficient. You need to choose a different algorithm.

The example input is n= 10 and queries = [[1,5,3],[4,8,7],[6,9,1]].

Look at the whole range:

   0   1   2   3   4   5   6   7   8   9    index
   1   1   1   1   1   1   1   1   1   1    original array
       3   3   3   3   3                    1st query
                   7   7   7   7   7        2nd query
                           3   3   3   3    3rd query
   1   4   4   4  11  11  11  11  11   3    sum

What your algorithm does is applying all the steps in order of this table, then iterates the array to get the maximum.

Instead of that you can merge the intervals:

Start with

[1,5,3]

Add [4,8,7]

-> [1,3,3] , [4,5,10] , [6,8,3]

Add [6,9,1]

-> [1,3,3] , [4,5,10] , [6,8,4] , [9,9,1]

Because I didnt include the initial ones, ie [0,n-1,1], the result is 10+1 = 11.

This is what the challenge is about, to find a way to retrive the result without actually carrying all the steps. When it says: You are given an array, and perform operations on that array, then determine the max element of the array, then you do not actually need the array. You only need to compute the maximum element in a hypothetical array with elements as if you carried out the operations.

I didn't think it trough completely, but I would expect the above to have much better complexity than your brute force approach. It does not depend on the number of elements in the array, only on the number of queries.

Do the maths first. Now you can start writing the code.

PS: There is a mistake in adding the invervals above. I hope you get the idea nevertheless.

463035818_is_not_an_ai
  • 109,796
  • 11
  • 89
  • 185