4
\$\begingroup\$

I am working on an algorithm question in which I need to find out pair of number out of 2 sorted arrays which sum up to the given number. I need to print out the indexes of those pairs rather than number itself.

I have written an algorithm which does work but I am wondering is it the best solution or is there any better way to do it (complexity-wise).

    /**
     * Finds and prints all the pairs of indexes from 2 sorted arrays which sum up to the given number
     * @param array1 The first array
     * @param array2 The second array
     * @param sum The number which needs to be constructed by summing integers of both arrays
     */
    private static void findPairs(int[] array1, int[] array2, int sum) {
        if(array1.length == 0 || array2.length == 0) 
            return;

        Map<Integer, Integer> firstArrayMap = new HashMap<Integer, Integer>();

        for(int i = 0; i < array1.length; i++) {
            firstArrayMap.put(sum - array1[i], i);
        }

        for(int i = 0; i < array2.length; i++) {
            if(firstArrayMap.containsKey(array2[i])) 
                System.out.println("Pair found at index : " + firstArrayMap.get(array2[i]) + " " + i);

        }

    }
\$\endgroup\$
7
\$\begingroup\$

Your code reads easily: it loops over the two arrays to find the corresponding pairs.

However, it doesn't take advantage of the fact that both arrays are sorted. You can refer to this Stack Overflow answer by Mark Byers to see how it is possible to do it in linear time and constant storage when both arrays are sorted. Quoting for reference:

  • Start with two pointers, one pointing at the smallest element of A, the other pointing to the largest element of B.
  • Calculate the sum of the pointed to elements.
  • If it is smaller than k increment the pointer into A so that it points to the next largest element.
  • If it is larger than k decrement the pointer into B so that it points to the next smallest element.
  • If it is exactly k you've found a pair. Move one of the pointers and keep going to find the next pair.

In this version, each pointer will always go forward (for the first array) or backward (for the second array), so there will be at most A.length + B.length moves.

Putting this into code, you would have:

private static void findPairs(int[] array1, int[] array2, int sum) {
    int l = 0, r = array2.length - 1;
    while (l < array1.length && r >= 0) {
        int s = array1[l] + array2[r];
        if (s < sum) {
            l++;
        } else if (s > sum) {
            r--;
        } else {
            System.out.println("Pair found at index : " + l + " " + r);
            l++;
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ This makes much more sense. It's easily understandable too. Thanks :) \$\endgroup\$ – Sneh Feb 3 '16 at 14:15
  • \$\begingroup\$ Here's a test case: array1 = [1, 1] and array2 = [2, 2] and sum = 3. Mark Byers' algorithm doesn't emit all pairs. If you don't care about that, you can advance both pointers when you find an equality—but for what purpose are you then continuing the search? See also my comments to Mark's answer in which I give my suggested all-pairs algorithm. \$\endgroup\$ – Jonas Kölker Apr 5 '16 at 21:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.