New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
leetcode/hash-table/TwoSum.java #94
Comments
This assumes that the array is sorted which is not the case. Therefore this adds an overhead of O(nlogn) to sort which is slower than O(n) |
right but the hashmap increases use of space. shouldn't we consider the net effect ? |
@knasim Even if we go best sorting algorithm(merge/quick/tree), It will have time complexity O(nlogn) Using hashmap, we solve this in O(n) time with space O(n) even if all the elements are distinct in the array. |
@IAmPramod , I reckon hashmap is implemented using Red-Black trees, so the average lookup time for a huge N becomes log N. So for N elements it again comes to O(N log N) |
@sragha45 Yes, you are correct. But O(NlogN) is the worst case scenario when we have a very poor implementation of hash code which will map all entries to same bucket. Have a look at the performance of hashmap in average case. https://dzone.com/articles/hashmap-performance |
May be this is not completely related to the discussion. But with hash map and tuple together, we can solve this problem easily.
https://github.com/vin0010/Competitve-Programming/blob/master/python/leetcode/TwoSum.py |
There is a better solution for the TwoSum problem than the hashmap solution. Sure hashmap is fine and meets the desired output. however it can be completely eliminated as such. The techinque employs a pointers to track the argument array i.e. one from the begining aka
head
and the other one from the end akatail
. A single sweep on the array and adjusting the two pointers does the job rather nicely.The text was updated successfully, but these errors were encountered: