Kth Smallest Sum In Two Sorted Arrays

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 kth smallest sum out of all possible sums.

Example Given [1, 7, 11] and [2, 4, 6]. For k = 3, return 7. For k = 4, return 9. For k = 8, return 15.

Challenge Do it in either of the following time complexity: O(k log min(n, m, k)). where n is the size of A, and m is the size of B. O( (m + n) log maxValue). where maxValue is the max number in A and B.

KeyPoints: O(3nlgn) O(2n) / O(2nlgn) O(n)

1. Sum of two sorted arrays is exactly the same as a sorted matrix, where each element must be smaller than the element on the left and below.

2. After transforming the problem into matrix, it turns out to be the same problem as Kth Smallest Number in Sorted Matrix.

   In this case:

   

         /**
         * @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
         */
        public int kthSmallestSum(int[] A, int[] B, int k) {
            if (A.length == 0 || B.length == 0 || k == 0) {
                return 0;
            }
            HashSet<Point> set = new HashSet<>();
            Queue<Point> heap = new PriorityQueue<>();
            heap.offer(new Point(0, 0, A[0] + B[0]));
   
            for (int i = 1; i < k; i++) {
                Point p = heap.poll();
   
                if (p.x + 1 < A.length) {
                    Point p1 = new Point(p.x + 1, p.y, A[p.x + 1] + B[p.y]);
                    if (!set.contains(p1)) {
                        heap.offer(p1);
                        set.add(p1);
                    }
                }
                if (p.y + 1 < B.length) {
                    Point p2 = new Point(p.x, p.y + 1, A[p.x] + B[p.y + 1]);
                    if (!set.contains(p2)) {
                        heap.offer(p2);
                        set.add(p2);
                    }
                }
            }
            return heap.peek().val;
   
        }
   
        class Point implements Comparable<Point> {
            int x, y;
            int val;
   
            Point(int x, int y, int val) {
                this.x = x;
                this.y = y;
                this.val = val;
            }
   
            @Override
            //For Heap
            public int compareTo(Point another) {
                if (this.val == another.val) {
                    return 0;
                }
                return this.val < another.val ? -1 : 1;
            }
   
            @Override
            //For HashSet
            public boolean equals(Object obj) {
                if (obj == this) {
                    return true;
                } else if (!(obj instanceof Point)) {
                    return false;
                }
                Point another = (Point) obj;
                return this.x == another.x && this.y == another.y;
            }
   
            @Override
            public int hashCode() {
                return x * 101 + y;
            }
        }