Given two integer arrays sorted in ascending order and an integer k. Define

sum = a + b

, where

a

is an element from the first array and

b

is an element from the second one. Find the

k

th smallest sum out of all possible sums.

1. need to convert this into kth smallest number in sorted matrix
2. the key is to find that the virtual matrix vMatrix[i][j] == A[i] + B[j]

public class Solution {

    /*
     * @param A: an integer arrays sorted in ascending order
     * @param B: an integer arrays sorted in ascending order
     * @param k: An integer
     * @return: An integer
     */
    class Pair {
        int i, j, val;
        public Pair(int i, int j, int val) {
            this.i = i;
            this.j = j;
            this.val = val;
        }
    }

    class PairComparator implements Comparator<Pair> {
        public int compare(Pair A, Pair B) {
            return A.val - B.val;
        }
    }

    private int[] dx = {0,1};
    private int[] dy = {1,0};

    public int kthSmallestSum(int[] A, int[] B, int k) {
        // write your code here
        if ((A == null && B == null) || (A.length == 0 && B.length == 0)) {
            return 0;
        }

        Queue<Pair> pq = new PriorityQueue<Pair>(k, new PairComparator());

        pq.offer(new Pair(0, 0, A[0] + B[0]));
        int[][] hash = new int[A.length][B.length];

        for (int p = 0; p < k - 1; p++) {
            Pair cur = pq.poll();
            for (int q = 0; q < 2; q++) {
                int next_i = cur.i + dx[q];
                int next_j = cur.j + dy[q];

                if (next_i < A.length && next_j < B.length && hash[next_i][next_j] != 1) {
                    hash[next_i][next_j] = 1;
                    Pair newPair = new Pair(next_i, next_j, A[next_i] + B[next_j]);
                    pq.offer(newPair);
                }
            }
        }

        return pq.peek().val;
    }
};