1

Two sets of 'n' numbers are given A and B. Chose one element from A and one from B such that the sum is equal to a given value, 'val'.

I have got the solution as:

We can hash the elements of Set A and Set B and check for every element in set A whether val-arr[i] exists in the hash of Set B or not. This would take O(n) time and O(n) space Can there be a better solutions with space as O(1) and time O(n)?

yoozer8
  • 7,361
  • 7
  • 58
  • 93
Luv
  • 5,381
  • 9
  • 48
  • 61
  • take a look at answers to [this question](http://stackoverflow.com/questions/8119911/on-logn-algorithm-that-checks-if-sum-of-2-numbers-in-a-int-given-number/8120870#8120870) – soulcheck Apr 07 '12 at 15:48
  • Then, no. The only other approach close to this would be to sort both arrays and do a reverse merge/match. The match is O(n) and no space (so O(1)), but the sorts are O(N*LogN) time and O(LogN) space. – RBarryYoung Apr 07 '12 at 15:53
  • Are the values limited by some maximum, or are they truly arbitrary? Are they integers? – Adam Liss Apr 07 '12 at 15:59
  • I don't think so. Maybe you could come up with something using parallel computing? Like sort the array in O(n) and think of what to do next... Dunno. – lampak Apr 07 '12 at 16:00
  • @lampak: Parallel processing doesn't reduce the time-complexity of an algorithm... – Oliver Charlesworth Apr 07 '12 at 17:24
  • No the values are not limited by any maximum, they are integers – Luv Apr 07 '12 at 18:07
  • @RBarryYoung there is a quick sort which is O(N*LogN) in avg time and O(1) in space. – Timofey Jan 30 '14 at 01:51
  • @Tim I did not know this. Can you provide a link or reference? I would really like to read up on this method. – RBarryYoung Jan 30 '14 at 16:15
  • @RBarryYoung I hope it is not trolling ;-) My comment was referred to your phrase "but the sorts are O(N*LogN) time and O(LogN) space". Just google for quicksort, or check out wikipedia http://goo.gl/pzw8 – Timofey Jan 31 '14 at 14:16
  • @Tim: The Wikipedia article never actually says that quicksort can be done in constant additional space. Rather, in three places is says that the *partitioning* can be done in place for O(1) space. In two of the three mentions, it then immediately points out that the recursive calls that follow this must use O(logN) space. I assume that the first mention is merely suffering from the usual confusion of wikipedia editing. AFAIK, there is still no way to do Quicksort in O(NlogN) time and less than O(logN) space. – RBarryYoung Jan 31 '14 at 18:16
  • @RBarryYoung Here is my recursive (and therefore limited) implementation of in-place (=O(1) space) quick sort: http://pastebin.com/HwLTCYRv – Timofey Feb 01 '14 at 14:20
  • @Tim This is not O(1) in space. The recursive use of the stack is O(logN). – RBarryYoung Feb 03 '14 at 04:54
  • @RBarryYoung you are right, there is a necessity of additional space which is allocated on stack. – Timofey Feb 03 '14 at 06:45
  • @RBarryYoung still there are sorts which are comparison-based sorts and use constant additional space: http://goo.gl/PAxbqv – Timofey Feb 03 '14 at 06:53
  • @Tim Sure, bubble-sort is one, but its CPU is O(n^2). Again, AFAIK, there is no general-purpose sorting algorithm better than O(NlogN) CPU and O(logN) additional space, and if there was, it would be big news. None of the abstracts in that digest list of citations you link to say otherwise, and I am not going to read every one of those articles in detail. If you know of a ***specific*** counter-example please cite it. – RBarryYoung Feb 03 '14 at 15:28
  • @RBarryYoung actually there is a sorting algorithm with O(NLogN) time and O(1) space complexity, this is heapsort: http://goo.gl/JQT0P6 :) – Timofey Oct 30 '14 at 15:08

1 Answers1

1

As you have both the arrays NOT sorted, you have NO other option but look at every element one-by-one. So, you cannot get below O(n) running time. I think the approach you are using is ok.

Read these related posts:

Given two arrays a and b .Find all pairs of elements (a1,b1) such that a1 belongs to Array A and b1 belongs to Array B whose sum a1+b1 = k

Find two elements in an array that sum to k

Community
  • 1
  • 1
Tejas Patil
  • 6,149
  • 1
  • 23
  • 38