4

Given two sorted arrays, A and B, find i,j for which |A[i] - B[j]| is minimum.

simplfuzz
  • 12,479
  • 24
  • 84
  • 137
  • Please, phrase what you would like to know as a question! – Goran Jovic Dec 10 '10 at 18:45
  • 3
    Given 2 homework questions, you have to ... at least try them yourself. – H H Dec 10 '10 at 18:46
  • He wants to know the most efficient way to find the smallest distance between any two items in the two different arrays. – sethvargo Dec 10 '10 at 18:47
  • It makes a difference if they are sorted in ascending or descending order. Which is it? – John Hartsock Dec 10 '10 at 18:48
  • 4
    Why the haste to close? This *is* a real question. It is *not* vague, incomplete, overly broad or rhetorical. It *can* be reasonably answered in its current form. – moinudin Dec 10 '10 at 18:51
  • @marcog: If for no other reason than to hopefully discourage him from his current spree of copying questions from some textbook into SO. – David Dec 10 '10 at 18:52
  • @David There are 4 more questions from this poster (all closed) in a record time of 9 mins! – Dr. belisarius Dec 10 '10 at 19:01
  • @David,belisarius, Why can't I ask 4 questions in 9 minutes? After a round of interviews, I wanted to post questions which I got. Do I really have to post MY answers with MY question, in order for them to look legitimate? – simplfuzz Dec 10 '10 at 19:04
  • @David, these questions are not copied from any textbook. I have given an explanation above. – simplfuzz Dec 10 '10 at 19:05
  • @dharm0us, "Do I really have to post MY answers with MY question" for homework and interview questions that would be a good start. – H H Dec 10 '10 at 21:09

1 Answers1

8

Since the arrays are sorted, you can pass through them with 2 pointers (one for each array). If |A[i+1] - B[j]| < |A[i] - B[j+1]| then increment i, otherwise increment j. Continue until you've reached the end of one of the arrays. Keep track of the minimal indexes as you go.

moinudin
  • 134,091
  • 45
  • 190
  • 216
  • what's the worst case run time complexity of this code ? It should be n^2, no ? – Yash Jan 27 '14 at 05:42
  • O(nlogm): for each element in A, use Binary Search method to find the element with the closest value in array B. – Yash Jan 27 '14 at 05:45
  • How do I figure out answers like this myself? What was the method you used to solve it? – template boy Nov 19 '14 at 22:07
  • what if |A[0]- B[0]| is less than all the other differences. May be you should add corner case to compare first two elements of arrays too, other than that it looks good to me. – username Jan 24 '15 at 19:05