CODEWITHSUNDEEP
algorithmbinary-search
John Tan
John Tan

Reputation: 147

Kth Smallest SUM In Two Sorted Arrays - Binary Search Solution

I am trying to solve an interview practice problem.

The problem is:

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.

For example

Given [1, 7, 11] and [2, 4, 6].

For k = 3, return 7.

For k = 4, return 9.

For k = 8, return 15.

We define n as the size of A, and m as the size of B. I know how to solve it using heap (O(k log min(n, m, k)) time complexity). But the problem states that there is another binary search method to do it with O( (m + n) log maxValue), where maxValue is the max number in A and B. Can anyone give some comments for solving it using binary search?

My thinking is that we may use x = A[] + B[] as the searching object, because the k-th x is what we want. If so, how can x be updated in binary search? How can I check if the updated x is valid or not (such a pair really exists or not)?

Thank you

The original problem is here: https://www.lintcode.com/en/problem/kth-smallest-sum-in-two-sorted-arrays/

Upvotes: 3

Views: 2720

Answers (1)

square1001
square1001

Reputation: 1464

You can solve for binary search and sliding window, and the time complexity is O((N + M) log maxvalue).

Let's think solving this problem (I call it counting problem).

You are given integers N, M, S, sequences a and b.
The length of sequence a is exactly N.
The length of sequence b is exactly M.
The sequence a, b is sorted.
Please calculate the number of pairs that satisfies a[i]+b[j]<=S (0<=i<=N-1, 0<=j<=M-1).

Actually, this counting problem can solve for binary search in O(N log M) time.
Surprisingly, this problem can solve for O(N+M).

Binary Search Algorithm
You can solve the maximum value of x that satisfies a[i] + b[x] <= S --> b[x] <= S - a[i] for O(log M).
Therefore, you can solve the number of value of x for O(log M) because it is equal to x+1.

O(N+M) Algorithm
Actually, if you do i++, the value of x is equal or less than previous value of x.
So you can use sliding window algorithm and.
You can solve for O(N+M), because you have to do operation i++ N times, and operation x-- M times.

Solving this main problem
You can binary_search for S and you can solve the inequality (counting problem's answer <= K).
The answer is the maximum value of S.
The time complexity is O((N + M) log maxvalue).

Upvotes: 1

Related Questions