Solve an issue using algorithm using javascript

Question

I am working on following example

Given: 2 sorted arrays of integers(e.g. A = [1,2,3,4,5], B = [6, 7, 8, 9, 10]) and answer(e.g 13)
Find: What I have to do is to find pair of indices(1 in each array) of those two elements in both arrays so when I add them then it should be equal to the given answer.

I used following 2 solutions. But the problem with both of them is that I am looping through both arrays. First I loop through first array and inside this I loop through second array. And add elements on those two indices to see if its addition is equal to answer. It works fine and outputs correct answer. The problem is performance. If we have 10,000 integers in both arrays then these loops will take a lot of resources such as time, CPU and memory to be executed and get answer.

How can I solve above particular problem in more efficient way?

function find (A1, A2, ans) {
  var a = [];
  for (var i = 0, len1 = A1.length; i < len1; i++) {
    for (var j = 0, len2 = A2.length; j < len2; j++) {
      if (ans === A1[i] + A2[j]) {
        a.push(i + ', ' + j);
      }
    }
  }
  return a;
}

second

function search (A, B, ans) {
  var arr = [];
  A.map(function (v, i) {
    B.filter(function (val, ind) {
      if (ans === v + val) arr.push(i + ', ' +ind);
    });
  });
  return arr;
}

What shall happen when no match is found (eg answer = 16 in your example) ? — Martin Ernst
– Martin Ernst, Commented Sep 29, 2014 at 11:31
Iterate first array and use binary search in second. Time complexity will be O(n log m). Your current time Complexity is O(n * m). binary search will save your time. — Md. Yusuf
– Md. Yusuf, Commented Sep 29, 2014 at 11:34

Mohit Jain · Accepted Answer · 2014-09-29 14:05:37Z

2

Solution1
You can iterate through all elements of array with lesser elements up to answer and binary search in second array for (answer - array[index]), complexity of this algo is O(N log M).

Live code in C++

Solution2
Or you can merge both arrays in linear time and apply following algorithm to find the pair in linear time. While merging, keep reverse mapping arrays mapA and mapB of size N+M in which mapA[i] points to index in array A from where i^th array of merged array came and -1 otherwise. Do similar for mapB also.

/* Merge the arrays */
mapA, mapB, MA all are arrays of size M+N, initialized with all -1
i = 0, j = 0
while(i < M && j < N)
    if(A[i] < B[j])
        MA[i+j] = A[i];
        mapA[i+j] = i++;
    else
        MA[i+j] = B[j];
        mapB[i+j] = j++;
while(i < M)
    MA[i+j] = A[i];
    mapA[i+j] = i++;
while(j < N)
    MA[i+j] = B[j];
    mapB[i+j] = j++;

/* Search the pair */
i = 0
j = N + M - 1
while(i < j){
   if(mapA[i] == -1) i++;
   else if(mapB[j] == -1) j--;
   else if (MA[i] + MA[j] == answer) return pair(mapA[i], mapB[j]);
   else if (MA[i] + MA[j] <  answer) i++;
   else if (MA[i] + MA[j] >  answer) j--;
}
return null_pair;  // no answer found

Live code example in C++

Solution3
There is a better algorithm (inspired from 3 sum algorithm) which works in linear time i.e. O(N + M) in constant space.

i = 0
j = M - 1
while(i < N && j >= 0){
   if      (A[i] + B[j] == answer) return pair(i, j);
   else if (A[i] + B[j] <  answer) i++;
   else if (A[i] + B[j] >  answer) j--;
}
return null_pair;  // no answer found

Proof
Let's assume A[x] + B[y] = answer. Then either x will reach i first or j will reach y first or we will find some other pair such that A[i] + B[j] = answer. Without loss of generality let's assume x becomes i first. Now for all j > y, A[i] + B[j] > answer so j will eventually reach answer. If there is no answer, we will exit the loop.

edited Sep 29, 2014 at 14:05

answered Sep 29, 2014 at 11:31

Mohit Jain

30.6k8 gold badges80 silver badges104 bronze badges

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

10 Comments

JLRishe Over a year ago

I think you mean O(N log M) for the first approach.

a-d Over a year ago

Also wouldn't it be O(N + M) in linear time?

Mohit Jain Over a year ago

Yes if size of smaller array is N. N log N if size of both arrays are comparable. Similary O(N+M) is similar to O(N) in same way. But your point is right, I would update it.

JLRishe Over a year ago

What is the reasoning behind while (i < j)? If you had two arrays [1, 2, 3] and [10, 17] and you were looking for the sum 13, the answer would be at i = 2, j = 0 and your while loop would have already exited.

Green Su Over a year ago

I have put a O(M+N) solution below.

|

Green Su · Accepted Answer · 2014-10-08 02:55:22Z

2

// get all pairs of number from array a and b, that a[i] + b[j] = sum
// return array of pairs
function getSumPairs(a, b, sum) {
    var pa = 0, pb = b.length - 1;
    var pairs = [];
    while (pa < a.length && pb >= 0) {
        if (a[pa] + b[pb] > sum ) {
            pb = pb - 1;
        } else if (a[pa] + b[pb] < sum) {
            pa = pa + 1;
        } else {
            pairs.push([a[pa], b[pb]]);
            pa = pa + 1;
            pb = pb - 1;
        }
    }
    return pairs;
}


// data for test
var arr1 = [-1, 1, 2, 3, 4, 5, 7, 9],
    arr2 = [5, 7, 10, 12, 13, 14, 15];

console.log(getSumPairs(arr1, arr2, 14))
console.log(getSumPairs(arr1, arr2, 15))

The algorithm is to sum the data from array a and b from different end. As the arrays are sorted:

if a[i] + b[j] < sum, a[i] + b[j-1] will still less than sum, so just need to increase i.

if a[i] + b[j] > sum, a[i+1] + b[j] will still larger than sum, so just need to decrease j.

Thus, all the elements from the tow arrays are only looped once. The complexity is O(M + N), for a[N] and b[M].

Try for yourself http://jsfiddle.net/9L4p1j3L/

edited Oct 8, 2014 at 2:55

answered Sep 29, 2014 at 12:24

Green Su

2,3483 gold badges22 silver badges16 bronze badges

5 Comments

Green Su Over a year ago

Hi @MohitJain, for both of your input, I have run the code, and it get [3,9], and [9, 3] respectively. Just change the input and call getSumPairs(arr1, arr2, 12).

26ph19 Over a year ago

@GreenSu could you create a jsfiddle for this with my inputs in question? It does not work properly for that input.

26ph19 Over a year ago

I mean it does not work for this input var arr1 = [-1, 1, 2, 3, 4, 5, -7], arr2 = [6, 7, 8, 9, 10, 20, 11];. for this one -7+20=13 but it does not evaluate this as true and does not put in pairs array.

Green Su Over a year ago

@26ph19 As the question described, the input should be two sorted array. So your input is not valid. arr1 should be [-7, -1, 1, 2, 3, 4, 5].

Green Su Over a year ago

@26ph19 And arr2 be [6, 7, 8, 9, 10, 11, 20]

dReAmEr · Accepted Answer · 2014-09-29 11:34:55Z

1

function find (A1, A2, ans) {
  var a = [];
  for (var i = 0, len1 = A1.length; i < len1; i++) {
    var noToSearch = ans - A1[i];
    var secondIndex  = binarySearch(A2,noToSearch);
    if(secondIndex !=-1){
        a.push(i + ', ' + secondIndex );
    }
  }
  return a;
}

function binarySearch(A2,num){
 var index = -1;
  //write binary search algo to find the element in array A2
 return index;
}

answered Sep 29, 2014 at 11:34

dReAmEr

7,2047 gold badges40 silver badges67 bronze badges

Collectives™ on Stack Overflow

Solve an issue using algorithm using javascript

3 Answers 3

10 Comments

5 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

10 Comments

5 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related