CODEWITHSUNDEEP
arraysalgorithmtime-complexity
Luv
Luv

Reputation: 5451

find two elements so sum is equal to given value

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)?

Upvotes: 1

Views: 3152

Answers (1)

Tejas Patil
Tejas Patil

Reputation: 6169

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

Upvotes: 1

Related Questions