tag:blogger.com,1999:blog-6294663875929591018.post2266114237713689965..comments2023-09-24T03:12:58.137-07:00Comments on Ramblings of a techie: Given an array find any pair that sums up into a numberBragBoyhttp://www.blogger.com/profile/01173019524783723568noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-6294663875929591018.post-86973308926050510042011-01-30T10:06:31.295-08:002011-01-30T10:06:31.295-08:00@vijay : yes that is a very good idea to solve the...@vijay : yes that is a very good idea to solve the problem!!BragBoyhttps://www.blogger.com/profile/01173019524783723568noreply@blogger.comtag:blogger.com,1999:blog-6294663875929591018.post-11238778434878125192011-01-28T15:45:14.195-08:002011-01-28T15:45:14.195-08:00it might be a good idea to use BST here. create a ...it might be a good idea to use BST here. create a BST of n numbers (nlogn). then, for each number in an array (of size n), subtract it from TargetSum and then look for the other number in binary tree (logn) which should take (nlogn) total time ... the overall time would (nlogn + nlogn) which is nlogn... please correct me if I am wrong.vijayhttps://www.blogger.com/profile/15969796623460325709noreply@blogger.comtag:blogger.com,1999:blog-6294663875929591018.post-4454628997222482922010-04-29T07:33:00.443-07:002010-04-29T07:33:00.443-07:00You can easily tackle this question in O(n lg n) t...You can easily tackle this question in O(n lg n) time by first sorting the array using in-place comparison sort like quick sort. After sorting, you can have two pointers pointed to the head and the tail, then find the sum.ifanchuhttps://www.blogger.com/profile/10886023434653520373noreply@blogger.comtag:blogger.com,1999:blog-6294663875929591018.post-19410330753846352262010-02-18T00:06:53.592-08:002010-02-18T00:06:53.592-08:00@Arun: I completely accept your argument. The reas...@Arun: I completely accept your argument. The reason i want to solve the problem without using Hash is because that is what interviewers ask :) these days. They tell you not to solve using Hash. And they may say it should not be O(n*n) either.BragBoyhttps://www.blogger.com/profile/01173019524783723568noreply@blogger.comtag:blogger.com,1999:blog-6294663875929591018.post-32548165304857801822010-02-17T23:23:25.847-08:002010-02-17T23:23:25.847-08:00Considering that the members are not ordered, the ...Considering that the members are not ordered, the best bet would be to use a hash based datastructure. I am not sure why you generalize HashSet as expensive. List or an array would do horribly when doing a linear search with this data (as you know, binary search is impossible here). I cant think of any other datastructure you could fit in. Also, the performance of HashSet depends on the efficient implementation of the hash. So, there could be a cost you would pay for larger datasets but i am sure that would be better than linear search any day.Arunhttps://www.blogger.com/profile/06752352409247034897noreply@blogger.com