Find given number by summing up integers from 2 sorted arrays

Question

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);

        }

    }

Answer 1

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++;
        }
    }
}