Searching in multiple sorted array and its complexity

Question

Given 3 sorted array. Find 3 elements, one from each array such that a+b=c. Can it be done less than O(n^3) time complexity? Please help me.

zw324 · Accepted Answer · 2012-04-26 14:13:46Z

4

Call the three arrays A, B and C, and the elements a, b and c.

While looping through the first two arrays, since if a is fixed, b can only increase, c also can only increase.

So you don't have to loop through C every time you have a pair of a and b; just loop through C while looping though B will do.

Now Suppose all three arrays have length O(N), the time complexity is O(N^2), since for each value in A, you need to go through all of B and all of C, the number which is O(N).

answered Apr 26, 2012 at 14:13

zw324

27.2k16 gold badges88 silver badges119 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

gabitzish · Accepted Answer · 2012-04-26 14:11:15Z

2

It can be done in O(N^2 * logN) complexity by iterating through 2 of the arrays for a and b and binary searching for c in the third array.

Another method would be O(N^2) by inserting the elements of one of the arrays into a hash, iterate for a and b in the other two arrays and looking if c = (a + b) exists in the hash.

answered Apr 26, 2012 at 14:11

gabitzish

9,7117 gold badges47 silver badges67 bronze badges

2 Comments

Neel Over a year ago

For method 2, is there any efficient way to solve it since it is given that all 3 arrays are already sorted?

gabitzish Over a year ago

You can't generate the (a,b) pairs better than O(N^2) ... The searching in the hash is O(1)

Collectives™ on Stack Overflow

Searching in multiple sorted array and its complexity

2 Answers 2

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related