Kth Smallest Element in Two Sorted Arrays

0
159

K-th Element of Two Sorted Arrays

In this post, You can easily learn kth smallest element in two sorted arrays. You must identify the element that would be at the kth position of the final sorted array given two sorted arrays of size m and n, respectively.

kth smallest element in two sorted arrays
kth smallest element in two sorted arrays

Examples:

Input : Array 1 - 2 3 6 7 9
        Array 2 - 1 4 8 10
        k = 5
Output : 6
Explanation: The final sorted array would be -
1, 2, 3, 4, 6, 7, 8, 9, 10
The 5th element of this array is 6.
Input : Array 1 - 100 112 256 349 770
        Array 2 - 72 86 113 119 265 445 892
        k = 7
Output : 256
Explanation: Final sorted array is -
72, 86, 100, 112, 113, 119, 256, 265, 349, 445, 770, 892
7th element of this array is 256.

Basic Approach

We can utilize the merging procedure to retrieve the final merged array because we have two sorted arrays. We simply go to the k’th index from here.

C++ Programe to Find kth Element from Two Sorted Arrays


// Program to find kth element from two sorted arrays 
#include <iostream> 
using namespace std; 
  
int kth(int arr1[], int arr2[], int m, int n, int k) 
{ 
    int sorted1[m + n]; 
    int i = 0, j = 0, d = 0; 
    while (i < m && j < n) 
    { 
        if (arr1[i] < arr2[j]) 
            sorted1[d++] = arr1[i++]; 
        else
            sorted1[d++] = arr2[j++]; 
    } 
    while (i < m) 
        sorted1[d++] = arr1[i++]; 
    while (j < n) 
        sorted1[d++] = arr2[j++]; 
    return sorted1[k - 1]; 
} 
  
int main() 
{ 
    int arr1[5] = {2, 3, 6, 7, 9}; 
    int arr2[4] = {1, 4, 8, 10}; 
    int k = 5; 
    cout << kth(arr1, arr2, 5, 4, k); 
    return 0; 
}  

Java Program to Find kth Element from Two Sorted Arrays


// Java Program to find kth element  
// from two sorted arrays 
  
class Main 
{ 
    static int kth(int arr1[], int arr2[], int m, int n, int k) 
    { 
        int[] sorted1 = new int[m + n]; 
        int i = 0, j = 0, d = 0; 
        while (i < m && j < n) 
        { 
            if (arr1[i] < arr2[j]) 
                sorted1[d++] = arr1[i++]; 
            else
                sorted1[d++] = arr2[j++]; 
        } 
        while (i < m) 
            sorted1[d++] = arr1[i++]; 
        while (j < n) 
            sorted1[d++] = arr2[j++]; 
        return sorted1[k - 1]; 
    } 
      
    // main function 
    public static void main (String[] args)  
    { 
        int arr1[] = {2, 3, 6, 7, 9}; 
        int arr2[] = {1, 4, 8, 10}; 
        int k = 5; 
        System.out.print(kth(arr1, arr2, 5, 4, k)); 
    } 
} 
  

Python 3 Program to Find kth Element from Two Sorted Arrays


# Program to find kth element 
# from two sorted arrays 
  
def kth(arr1, arr2, m, n, k): 
      
    sorted1 = [0] * (m + n) 
    i = 0
    j = 0
    d = 0
    while (i < m and j < n): 
      
        if (arr1[i] < arr2[j]): 
            sorted1[d] = arr1[i] 
            i += 1
        else: 
            sorted1[d] = arr2[j] 
            j += 1
        d += 1
  
    while (i < m): 
        sorted1[d] = arr1[i] 
        d += 1
        i += 1
    while (j < n): 
        sorted1[d] = arr2[j] 
        d += 1
        j += 1
    return sorted1[k - 1] 
  
# driver code 
arr1 = [2, 3, 6, 7, 9] 
arr2 = [1, 4, 8, 10] 
k = 5; 
print(kth(arr1, arr2, 5, 4, k)) 
  

C# Program to Find kth Element from Two Sorted Arrays


// C# Program to find kth element  
// from two sorted arrays 
class GFG 
{ 
static int kth(int[] arr1, int[] arr2,  
               int m, int n, int k) 
{ 
    int[] sorted1 = new int[m + n]; 
    int i = 0, j = 0, d = 0; 
    while (i < m && j < n) 
    { 
        if (arr1[i] < arr2[j]) 
            sorted1[d++] = arr1[i++]; 
        else
            sorted1[d++] = arr2[j++]; 
    } 
    while (i < m) 
        sorted1[d++] = arr1[i++]; 
    while (j < n) 
        sorted1[d++] = arr2[j++]; 
    return sorted1[k - 1]; 
} 
  
// Driver Code 
static void Main()  
{ 
    int[] arr1 = {2, 3, 6, 7, 9}; 
    int[] arr2 = {1, 4, 8, 10}; 
    int k = 5; 
    System.Console.WriteLine(kth(arr1, arr2, 
                                 5, 4, k)); 
} 
} 

PHP Program to Find kth Element from Two Sorted Arrays


<?php  
// Program to find kth 
// element from two  
// sorted arrays 
  
function kth($arr1, $arr2, 
             $m, $n, $k) 
{ 
    $sorted1[$m + $n] = 0; 
    $i = 0; 
    $j = 0; 
    $d = 0; 
    while ($i < $m && $j < $n) 
    { 
        if ($arr1[$i] < $arr2[$j]) 
            $sorted1[$d++] = $arr1[$i++]; 
        else
            $sorted1[$d++] = $arr2[$j++]; 
    } 
    while ($i < $m) 
        $sorted1[$d++] = $arr1[$i++]; 
    while ($j < $n) 
        $sorted1[$d++] = $arr2[$j++]; 
    return $sorted1[$k - 1]; 
} 
  
// Driver Code 
$arr1 = array(2, 3, 6, 7, 9); 
$arr2 = array(1, 4, 8, 10); 
$k = 5; 
echo kth($arr1, $arr2, 5, 4, $k); 

Output:

6
Time Complexity: O(n)
Auxiliary Space : O(m + n)

Divide And Conquer Approach 1

Can we make our algorithm more efficient while using the previous method? Yes, it is correct. We can try to identify the k’th element more efficiently by utilizing a divide and conquer strategy, similar to the one used in binary search.

We compare the middle elements of arrays arr1 and arr2, which we'll refer to as mid1 and mid2 indices.

If arr1[mid1] k, then the elements after mid2 definitely cannot be the needed element. The last element of arr2 is then set to arr2[mid2].

As a result, a new subproblem with half the size of one of the arrays is defined.

C++ Program to Find kth Element from Two Sorted Arrays


// Program to find k-th element from two sorted arrays 
#include <iostream> 
using namespace std; 
  
int kth(int *arr1, int *arr2, int *end1, int *end2, int k) 
{ 
    if (arr1 == end1) 
        return arr2[k]; 
    if (arr2 == end2) 
        return arr1[k]; 
    int mid1 = (end1 - arr1) / 2; 
    int mid2 = (end2 - arr2) / 2; 
    if (mid1 + mid2 < k) 
    { 
        if (arr1[mid1] > arr2[mid2]) 
            return kth(arr1, arr2 + mid2 + 1, end1, end2, 
                k - mid2 - 1); 
        else
            return kth(arr1 + mid1 + 1, arr2, end1, end2, 
                k - mid1 - 1); 
    } 
    else
    { 
        if (arr1[mid1] > arr2[mid2]) 
            return kth(arr1, arr2, arr1 + mid1, end2, k); 
        else
            return kth(arr1, arr2, end1, arr2 + mid2, k); 
    } 
} 
  
int main() 
{ 
    int arr1[5] = {2, 3, 6, 7, 9}; 
    int arr2[4] = {1, 4, 8, 10}; 
  
    int k = 5; 
    cout << kth(arr1, arr2, arr1 + 5, arr2 + 4,  k - 1); 
    return 0; 
}  

Output:

6

Note that k is indexed 0 in the preceding code, thus if we want a 1 indexed k, we must remove 1 before providing it to the function.
O(log n + log m) is the time complexity.

Divide And Conquer Approach 2

While the preceding approach is quite efficient, there is always room for improvement. Rather than partitioning the array into n / 2 and m / 2 parts and recursing, we can divide them both by k / 2 and recurse. This is shown in the implementation below.

Explanation:
Instead of comparing the middle element of the arrays,
we compare the k / 2th element.
Let arr1 and arr2 be the arrays.
Now, if arr1[k / 2]  arr1[1]

New subproblem:
Array 1 - 6 7 9
Array 2 - 1 4 8 10
k = 5 - 2 = 3

floor(k / 2) = 1
arr1[1] = 6
arr2[1] = 1
arr1[1] > arr2[1]

New subproblem:
Array 1 - 6 7 9
Array 2 - 4 8 10
k = 3 - 1 = 2

floor(k / 2) = 1
arr1[1] = 6
arr2[1] = 4
arr1[1] > arr2[1]

New subproblem:
Array 1 - 6 7 9
Array 2 - 8 10
k = 2 - 1 = 1

Now, we directly compare first elements,
since k = 1. 
arr1[1] < arr2[1]
Hence, arr1[1] = 6 is the answer.

C++ Program to Find kth Element from Two Sorted Arrays

// Program to find kth element from two sorted arrays 
#include <iostream> 
using namespace std; 
  
int kth(int arr1[], int arr2[], int m, int n, int k, 
                           int st1 = 0, int st2 = 0) 
{ 
    // In case we have reached end of array 1 
    if (st1 == m) 
        return arr2[st2 + k - 1]; 
  
    // In case we have reached end of array 2 
    if (st2 == n) 
        return arr1[st1 + k - 1]; 
  
    // k should never reach 0 or exceed sizes 
    // of arrays 
    if (k == 0 || k > (m - st1) + (n - st2)) 
        return -1; 
  
    // Compare first elements of arrays and return 
    if (k == 1) 
        return (arr1[st1] < arr2[st2]) ? 
            arr1[st1] : arr2[st2]; 
    int curr = k / 2; 
  
    // Size of array 1 is less than k / 2 
    if (curr - 1 >= m - st1) 
    { 
        // Last element of array 1 is not kth 
        // We can directly return the (k - m)th 
        // element in array 2 
        if (arr1[m - 1] < arr2[st2 + curr - 1]) 
            return arr2[st2 + (k - (m - st1) - 1)]; 
        else
            return kth(arr1, arr2, m, n, k - curr, 
                st1, st2 + curr); 
    } 
  
    // Size of array 2 is less than k / 2 
    if (curr-1 >= n-st2) 
    { 
        if (arr2[n - 1] < arr1[st1 + curr - 1]) 
            return arr1[st1 + (k - (n - st2) - 1)]; 
        else
            return kth(arr1, arr2, m, n, k - curr, 
                st1 + curr, st2); 
    } 
    else
    { 
        // Normal comparison, move starting index 
        // of one array k / 2 to the right 
        if (arr1[curr + st1 - 1] < arr2[curr + st2 - 1]) 
            return kth(arr1, arr2, m, n, k - curr, 
                st1 + curr, st2); 
        else
            return kth(arr1, arr2, m, n, k - curr, 
                st1, st2 + curr); 
    } 
} 
  
// Driver code 
int main() 
{ 
    int arr1[5] = {2, 3, 6, 7, 9}; 
    int arr2[4] = {1, 4, 8, 10}; 
  
    int k = 5; 
    cout << kth(arr1, arr2, 5, 4,  k); 
    return 0; 
} 

Java Program to Find kth Element from Two Sorted Arrays


// Java Program to find kth element from two sorted arrays 
class GFG  
{ 
  
    static int kth(int arr1[], int arr2[], int m, 
                   int n, int k, int st1, int st2)  
    { 
        // In case we have reached end of array 1 
        if (st1 == m)  
        { 
            return arr2[st2 + k - 1]; 
        } 
  
        // In case we have reached end of array 2 
        if (st2 == n)  
        { 
            return arr1[st1 + k - 1]; 
        } 
  
        // k should never reach 0 or exceed sizes 
        // of arrays 
        if (k == 0 || k > (m - st1) + (n - st2))  
        { 
            return -1; 
        } 
  
        // Compare first elements of arrays and return 
        if (k == 1)  
        { 
            return (arr1[st1] < arr2[st2]) 
                    ? arr1[st1] : arr2[st2]; 
        } 
        int curr = k / 2; 
  
        // Size of array 1 is less than k / 2 
        if (curr - 1 >= m - st1) 
        { 
              
            // Last element of array 1 is not kth 
            // We can directly return the (k - m)th 
            // element in array 2 
            if (arr1[m - 1] < arr2[st2 + curr - 1])  
            { 
                return arr2[st2 + (k - (m - st1) - 1)]; 
            }  
            else 
            { 
                return kth(arr1, arr2, m, n, k - curr, 
                        st1, st2 + curr); 
            } 
        } 
  
        // Size of array 2 is less than k / 2 
        if (curr - 1 >= n - st2) 
        { 
            if (arr2[n - 1] < arr1[st1 + curr - 1])  
            { 
                return arr1[st1 + (k - (n - st2) - 1)]; 
            } 
            else 
            { 
                return kth(arr1, arr2, m, n, k - curr, 
                        st1 + curr, st2); 
            } 
        }  
        else
          
        // Normal comparison, move starting index 
        // of one array k / 2 to the right 
        if (arr1[curr + st1 - 1] < arr2[curr + st2 - 1]) 
        { 
            return kth(arr1, arr2, m, n, k - curr, 
                    st1 + curr, st2); 
        }  
        else 
        { 
            return kth(arr1, arr2, m, n, k - curr, 
                    st1, st2 + curr); 
        } 
    } 
  
    // Driver code 
    public static void main(String[] args)  
    { 
        int arr1[] = {2, 3, 6, 7, 9}; 
        int arr2[] = {1, 4, 8, 10}; 
        int k = 5; 
        int st1 = 0, st2 = 0; 
        System.out.println(kth(arr1, arr2, 5, 4, k, st1, st2)); 
    } 
}  
  

C# Program to Find kth Element from Two Sorted Arrays


// C# Program to find kth element from two sorted arrays 
using System; 
  
class GFG  
{ 
  
    static int kth(int []arr1, int []arr2, int m, 
                int n, int k, int st1, int st2)  
    { 
        // In case we have reached end of array 1 
        if (st1 == m)  
        { 
            return arr2[st2 + k - 1]; 
        } 
  
        // In case we have reached end of array 2 
        if (st2 == n)  
        { 
            return arr1[st1 + k - 1]; 
        } 
  
        // k should never reach 0 or exceed sizes 
        // of arrays 
        if (k == 0 || k > (m - st1) + (n - st2))  
        { 
            return -1; 
        } 
  
        // Compare first elements of arrays and return 
        if (k == 1)  
        { 
            return (arr1[st1] < arr2[st2]) 
                    ? arr1[st1] : arr2[st2]; 
        } 
        int curr = k / 2; 
  
        // Size of array 1 is less than k / 2 
        if (curr - 1 >= m - st1) 
        { 
              
            // Last element of array 1 is not kth 
            // We can directly return the (k - m)th 
            // element in array 2 
            if (arr1[m - 1] < arr2[st2 + curr - 1])  
            { 
                return arr2[st2 + (k - (m - st1) - 1)]; 
            }  
            else
            { 
                return kth(arr1, arr2, m, n, k - curr, 
                        st1, st2 + curr); 
            } 
        } 
  
        // Size of array 2 is less than k / 2 
        if (curr - 1 >= n - st2) 
        { 
            if (arr2[n - 1] < arr1[st1 + curr - 1])  
            { 
                return arr1[st1 + (k - (n - st2) - 1)]; 
            } 
            else
            { 
                return kth(arr1, arr2, m, n, k - curr, 
                        st1 + curr, st2); 
            } 
        }  
        else
          
        // Normal comparison, move starting index 
        // of one array k / 2 to the right 
        if (arr1[curr + st1 - 1] < arr2[curr + st2 - 1]) 
        { 
            return kth(arr1, arr2, m, n, k - curr, 
                    st1 + curr, st2); 
        }  
        else
        { 
            return kth(arr1, arr2, m, n, k - curr, 
                    st1, st2 + curr); 
        } 
    } 
  
    // Driver code 
    public static void Main(String[] args)  
    { 
        int []arr1 = {2, 3, 6, 7, 9}; 
        int []arr2 = {1, 4, 8, 10}; 
        int k = 5; 
        int st1 = 0, st2 = 0; 
        Console.WriteLine(kth(arr1, arr2, 5, 4, k, st1, st2)); 
    } 
} 
  

Output:

6

Complexity of Time: O (log k)

k can now take on the maximum value of m + n. This suggests that log k might be log(m + n) in the worst-case scenario. Logm + logn = log(mn) by logarithm properties, and log(m + n) log(m + n) log(m + n) log(m + n) log(m + n) log(m + n) log(m + n) log(m + n) log(m + n) log(m (mn). As a result, this approach outperforms the previous algorithm by a little margin. Also, have a look at another log k approach that is straightforward to implement.

C++ Program to Find kth Element from Two Sorted Arrays

// C++ Program to find kth element from two sorted arrays 
// Time Complexity: O(log k) 
  
#include <iostream> 
using namespace std; 
  
int kth(int arr1[], int m, int arr2[], int n, int k) 
{ 
      
  if (k > (m+n) || k < 1) return -1; 
    
  // let m <= n 
  if (m > n) return kth(arr2, n, arr1, m, k); 
    
  // if arr1 is empty returning k-th element of arr2 
  if (m == 0) return arr2[k - 1]; 
    
  // if k = 1 return minimum of first two elements of both arrays  
  if (k == 1) return min(arr1[0], arr2[0]); 
    
  // now the divide and conquer part 
  int i = min(m, k / 2), j = min(n, k / 2); 
    
  if (arr1[i - 1] > arr2[j - 1] )  
    // Now we need to find only k-j th element since we have found out the lowest j 
    return kth(arr1, m, arr2 + j, n - j, k - j); 
  else 
    // Now we need to find only k-i th element since we have found out the lowest i 
    return kth(arr1 + i, m - i, arr2, n, k - i); 
} 
  
// Driver code 
int main() 
{ 
    int arr1[5] = {2, 3, 6, 7, 9}; 
    int arr2[4] = {1, 4, 8, 10}; 
    int m = sizeof(arr1)/sizeof(arr1[0]); 
    int n = sizeof(arr2)/sizeof(arr2[0]); 
    int k = 5; 
      
    int ans = kth(arr1,m,arr2, n, k); 
      
    if(ans == -1) cout<<"Invalid query"; 
    else cout<<ans; 
      
    return 0; 
} 

Time Complexity:O(log k)

Latest Article:

How to find the kth smallest element in the union of two sorted arrays?

LEAVE A REPLY

Please enter your comment!
Please enter your name here