vector code optimization

Question

I need to find out indices of vector element whose sum is matching with user input.
I can return any possible pair's indices out of all possible pair.Below is code what I have written, but it fails performance criteria for large input size. Any thought to optimize this would be helpful.

https://code.sololearn.com/cEse2V5kc9dX

Answer 1

Correct.
While looping, you will have to use something to store what you have found so far.

There is a data structure that allows you to store unique values and requires constant time to check if the complement of an element is there.

You’re almost there!

Answer 2

Do you have any idea about time complexity of a program?

Your program runs in quadratic time. To make it applicable for large inputs, you have to make it run in linear time.

Your program does what is called ‘Brute Force’, and this cannot be optimized any further. It is rarely the optimal solution either, so you have find another approach for this problem.

Hint: use appropriate data structure.

Answer 3

Yes I have a bit idea on it... This is O(n*n) time complexity.

I thought about it. Is it good to implement with only one for loop and eliminating second for loop with introduction of find for complementary value of first for loops value? Something like below:

For (loop through all elements)
Find value to be search i.e. sum value (10) minus element in for loop
Find distance of founded element

is it ok or something else with other data structure ? I thought but could not decide suitable data structure for this

Answer 4

I chose unordered_map now. Is it correct?

I updated code with same also but it is taking more than 300% compared to that of earlier vector method...!

Answer 5

I would use unordered_set, because you just need the key from unordered_map, not the value.
Also, try using .count(), let me know if there’s any difference

PS. Your program is giving the wrong answer for both methods.

Answer 6

Oops.... How come answer is wrong ? I checked that values at suggested index sums up to 110.

Additionally I don't understand how set can help me on this? Does not we need index and value both?

103 , 109, 7,1 is suppose list value in vector... So 7,1 both need to be stored along with index...isn't it ?

edit : you are right.. I am just using find for key... but return in form of pair is second element of map that is value..so both key and value is imp..

Answer 7

Oh, I didn’t realize that you’re returning the index.. If you need the index, then you have to use map.

For example 103, 109, 7, 1, it will go like:
find 7, if not exist, m[103] = 0
find 1, if not exist, m[109] = 1
find 103, there’s one in the map. return {index of 7, m[103]}

By the way, inserting pair into map is uncommon, but if it works then good for you.
People usually use: m[key] = value
in this case, m[element] = index

Answer 8

Oh right, about execution time.. You can’t really measure execution time that way. There are too many hidden constants. Besides, your input is too small to see the difference. A modern processor can do 10⁸︎ instructions per second, so programs that finish things in microseconds do not fit as benchmark.

You have to use at least 1000 input to start seeing the difference.

Answer 9

It just happened that both programs found the pair in less than 1000 operations. If you find an instance where brute force doesn’t find any solution starting the first value, it will be a lot slower.

You can’t judge runtime complexity based on input variety. Runtime complexity is always measured based on the worst case runtime of your program. What you just described is the best case runtime, which is not a useful concept. We are talking about the upper bound, not the lower bound.

Consider 1000 input:
1, 1, 1, ... 1, 2, 3 and you are looking to find 5.
This kind of input is what I mean by worst case.
Brute force will have to do 1000000 operations, whereas map will need to do just 1000 operations, at worst.

Answer 10

I appreciate your help Bobby Fischer ...

I just now updated code to remove inserting pair into map...

With this logic , index of result changed to 41 and 42 instead of 33 and 42.. still expected output is valid.

However, my major issue is unresolved yet...the way I implemented is yet bit slower than originally implemented brute force method...

This issue is eating my head but yes I m learning a lot also 😊

Answer 11

Yes now able to observe in updated code....storing 2000 number in vector for testing..

If I am storing random number by module of 100, it is sure that entire loop gonna execute as there would not be any two number which add into 1100... In this case, unordered map is best solution.

However , storing value module 1000 would result into earlier index as result and their brute force is better...

So, now got the better understanding..

thanks a lot Bobby Fischer for your extended hand of support to making me this understand 🙏

Answer 12

I’m not sure I understood you correctly. I tried storing 2000, 3000, map is faster?

It doesn’t have anything to do with modulo anything.

Try 20000 input, your brute force doesn’t even run at all.

Answer 13

Okay... Updated code for 10,000 values in input...

Correct.. brute force takes hell lot of time compared to map method..

Reason : it has to iterate through all input in both the method as all values in input list are below 100 due to below line i.e. line number 95

int val = rand()%100;

Change that line as below:
int val = rand()%1000;

Now observe time taken... Brute force does it quickly compared to map method

Answer 14

Yes correct