We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
You cannot do better than sorting the array and looking up the target value with binary search. Binary search is O(log n), and you have to do n of those, so your total complexity is O(n log n), which is the same complexity as sort, so sorting the array is a "free" operation.
If you implement this with any other data structure (hashmap, etc) that has O(log n) complexity for a lookup and insert, you're still going to have to make n lookups, which gives you a total complexity of O(n log n). The only way to improve on the sorted array would be to have a data structure that allows lookup and insert complexity below O(log n), and there's no such thing.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Pairs
You are viewing a single comment's thread. Return to all comments →
You cannot do better than sorting the array and looking up the target value with binary search. Binary search is O(log n), and you have to do n of those, so your total complexity is O(n log n), which is the same complexity as sort, so sorting the array is a "free" operation.
If you implement this with any other data structure (hashmap, etc) that has O(log n) complexity for a lookup and insert, you're still going to have to make n lookups, which gives you a total complexity of O(n log n). The only way to improve on the sorted array would be to have a data structure that allows lookup and insert complexity below O(log n), and there's no such thing.