3 ms·
I might be misunderstanding the question; how many pairs can there be? You can't just loop over the array twice to find all qualifying pairs of indices, if ther
by fractionalhare 6y ago
I might be misunderstanding the question; how many pairs can there be? You can't just loop over the array twice to find all qualifying pairs of indices, if there are multiple. You'd have to loop over the array n times, where n is the size of the array. Isn't that why the question is difficult? There doesn't seem to be much incentive to using a hash table, complexity wise, if you could just solve it in O(n) time and O(1) space by naively iterating over the array.
- renewiltord 6y agoHe meant "write two loops" when he said "loop twice". It seemed obvious to me that he meant that but I can see how if you're used to more unambiguous language it could be confusing. Yeah, you just do it in O(n²) worst case because the problem is O(n²) to find all pairs that match because there can be O(n²) pairs. However he meant one pair here too. Pretty easy to solve. Did it in under 30 s in Python on my broken cellphone. If there are multiple pairs, just replace return with yield.