2

Given two sorted arrays of integers A1, A2, with the same length n and an integer x, I need to write an algorithm that runs in O(nlog(n)) that determines whether there exist two elements a1, a2 (one element in each array) that make a1+a2=x.

At first I thought about having two index iterators i1=0, i2=0 (one for each array) that start from 0 and increase one at a time, depending on the next element of A1 being bigger/smaller than the next element of A2. But after testing it on two arrays I found out that it might miss some possible solutions...

McLovin
  • 3,295
  • 7
  • 32
  • 67
  • 1
    In my opinion, iterating through every element `a` of `A1` and binary searching for `x - a` in `A2` should do the trick. – EvilTak Mar 17 '18 at 13:20
  • 1
    Possible duplicate of [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](https://stackoverflow.com/questions/3815116/given-two-arrays-a-and-b-find-all-pairs-of-elements-a1-b1-such-that-a1-belong) – user202729 Mar 17 '18 at 13:20

3 Answers3

5

Well, as they are both sorted already, the algorithm should be O(n) (sorting would be O(n * log(n))):

i1 = 0
i2 = A2.size - 1
while i1 < A1.size and i2 >= 0
    if A1[i1] + A2[i2] < x
        ++i1
    else if A1[i1] + A2[i2] > x
        --i2
    else
        success!!!!
Deduplicator
  • 44,692
  • 7
  • 66
  • 118
1

This is a strange question because there is an inelegant solution in time O(N Lg N) (for every element of A1, lookup A2 for x-a1 by dichotomic search), and a nice one requiring only O(N) operations.

Start from the left of A1 and the right of A2 and move left in A2 as long as a1+a2≥x. Then move right one position in A1 and update in A2 if needed...

1

You start one array from index = 0 = i and the other in reverse other = j. First step you know you have the smallest in the list A and the biggest in the list B so you subtract i from x, then move the j index down until the value =< X

Basically you have 2 indexes moving towards the middle If value of index i > value of index j then there is no such sum that match x.