Question

Divide and conquer problem.

Suppose we are given two sorted arrays A[1 . . . n] and B[1 . . . n] and an integer k. Describe an algorithm to find the kth smallest element in the union of A and B in O(log n) time. For example, if k = 1, your algorithm should return the smallest element of A ∪ B; if k = n, your algorithm should return the median of A ∪ B.)
You can assume that the arrays contain no duplicate elements using divide and conquer.
(b) Now suppose we are given three sorted arrays A[1 . . . n], B[1 . . . n], and C[1 . . . n], and an integer k. Describe an algorithm to find the kth smallest element in A ∪ B ∪ C in O(log n) time using divide and conquer (not heap)

Answer 1

Solution:

• Using the divide and conquer approach, below solution time complexity is: O(log n)
• Check whether kth element lies in first half of either of the 2 arrays.
• If yes, only seek kth element in first half only, else seek only in second half.
• This recursively, reduce the original problem into a subproblem with smaller search space.
• Check comments in the code section for a better understanding

Code: O(log n) solution

#include <bits/stdc++.h>   
using namespace std;

int kSmallest(int A[], int B[], int *endA, int *endB, int k)
{ 
    // if array A is empty, then return kth value in B 
    if(A==endA)
        return B[k];
    
    // if array B is empty, then return kth value in A
    if(B==endB)
        return A[k];
        
    // Find mid index of array A and B
    int midA = (endA - A)/2;
    int midB = (endB - B)/2;

    // If condition checks whether k lies in second half of either of the arrays 
    if(midA + midB < k){
        // when array A has more elements than B, ignore first half of B
        if(A[midA] > B[midB])
            return kSmallest(A, (B+midB+1), endA, endB, (k-midB-1));
        // otherwise first half of A
        else
            return kSmallest((A+midA+1), B, endA, endB, (k-midA-1));
    }
    // Else k lies in first half of either array A or B
    else{
        if(A[midA] > B[midB])
            return kSmallest(A, B, A+midA, endB, k);
        else
            return kSmallest(A, B, endA, B+midB, k);
    }
    
    return -1;
} 
  
// Driver code 
int main() 
{ 
    int A[6] = {1, 2, 5, 6, 7, 9}; 
    int B[4] = {0, 3, 8, 10}; 
  
    int k = 4;
    
    cout<<"Kth smallest number in union of A and B : "<< kSmallest(A, B, A+6, B+4, k-1); 
    return 0; 
} 

Input: (hardcoded)

int A[6] = {1, 2, 5, 6, 7, 9}; 
int B[4] = {0, 3, 8, 10}; 
int k = 4;
    

Output:

Kth smallest number in union of A and B : 3

Attached screenshot of code:

For question 2, extend same idea for 3 arrays, try do it on your own. Ask if you face any issue in implementation.

PS: Let me know if you have any doubt.