Dot Product of Two Sparse Vectors || Leetcode 1570 || 1 Follow-up Question Meta Actually Asks

[@2NormalHuman]

Oh wow that's an awesome explanation, thanks for the video!

[@LiadMotorin]

Thanks !! please continue with the videos

[@AhmedHassan-vo5fz]

for the follow up can't we just use the smallest map or tuple as the itertor, then use a hasmap to find if the value is in the other array.

[@CodingWithMinmer]

You absolutely can, but Meta generally won't accept a map. In short, they're worried about collisions if the input is massively large (eh, really it's just their general attitude). A pre-allocated array would be more efficient.

[@MrApoorvWalls]

Wouldn’t it be better to keep the array and in the preprocessing step, instead of creating a list of tuples, we store the non zero indices in a set. Then before we perform the dot product, we can do set1 intersection set2 and just perform multiplication on the indices left in the intersection. It solves both the standard case and the follow up.

[@CodingWithMinmer]

I see what you mean. But one concern is the storage space if we keep the whole array: at least in the Leetcode problem, we can be given upwards 100,000 elements for example.

[@insofcury]

If we are storing index as key and the actual value as value in the map I don't think there would be any collisions related issue.

[@CodingWithMinmer]

"Most hash table designs employ an imperfect hash function. Hash collisions, where the hash function generates the same index for more than one key, therefore typically must be accommodated in some way." - Wikipedia Reference (yikes, URL encoding): en.wikipedia.org/wiki/Hash_table#:~:text=Most%20hash%20table%20designs%20employ%20an%20imperfect%20hash%20function.%20Hash%20collisions%2C%20where%20the%20hash%20function%20generates%20the%20same%20index%20for%20more%20than%20one%20key%2C%20therefore%20typically%20must%20be%20accommodated%20in%20some%20way.