K-th Element of Two Sorted Arrays | Algorithms - Computer Science Engineering (CSE) PDF Download

Problem Statement

Given two sorted arrays of sizes m and n respectively, the task is to find the element that would be at the k-th position in the final sorted array formed by merging these two arrays.

Input: Array 1 – [2, 3, 6, 7, 9], Array 2 – [1, 4, 8, 10], k=5
Output: 6
Explanation: The final sorted array is [1, 2, 3, 4, 6, 7, 8, 9, 10]. The 5th element is 6.

Input: Array 1 – [100, 112, 256, 349, 770], Array 2 – [72, 86, 113, 119, 265, 445, 892], k=7
Output: 256
Explanation: The final sorted array is [72, 86, 100, 112, 113, 119, 256, 265, 349, 445, 770, 892]. The 7th element is 256.

Approaches to Solve K-th Element of Two Sorted Arrays

1. [Naive Approach] Using Merging arrays – O(m + n) time and O(m + n) auxiliary space:

The basic idea here is to merge the given two arrays into a single sorted array and then simply return the element at the k-th position. This approach is straightforward because it directly uses the merging process of two sorted arrays, similar to the merge step in the merge sort algorithm.

We initialize three pointers: two pointers to traverse each array and one to keep track of the position in the merged array. By comparing the elements pointed to by the two array pointers, we place the smaller element into the merged array and move the respective pointer forward. This continues until one of the arrays is fully traversed. If any elements remain in either array, they are directly appended to the merged array. Finally, the k-th element of this merged array is returned.

Code Implementation:

#include <iostream>

using namespace std;

int kth(int arr1[], int arr2[], int n, int m, int k)

{

    // array to store the merged sorted array

    int sorted1[m + n];

    int i = 0, j = 0, d = 0;

    while (i < n && j < m) {

        // If the element of arr1 is smaller, insert the

        // element to the sorted array

        if (arr1[i] < arr2[j])

            sorted1[d++] = arr1[i++];

        else

            // If the element of arr2 is smaller, insert the

            // element to the sorted array

            sorted1[d++] = arr2[j++];

    }

    // Push the remaining elements of arr1

    while (i < n)

        sorted1[d++] = arr1[i++];

    // Push the remaining elements of arr2

    while (j < m)

        sorted1[d++] = arr2[j++];

    // Return the element at kth position in the merged

    // sorted array

    return sorted1[k - 1];

}

// 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;

}

Output:

6

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

2. [Optimal approach] Space Optimized Merge Approach – O(k) time and O(1) auxiliary space:

This approach optimizes the space complexity of the naive approach by avoiding the creation of an additional array. Instead, we use two pointers to traverse the input arrays and count the elements until we reach the k-th element. This method is more efficient in terms of space since it only uses a constant amount of extra memory.

We start with two pointers at the beginning of each array and another counter to keep track of the number of elements processed. By comparing the current elements of both arrays, the smaller one is considered as part of the merged sequence, and the pointer for that array would be incremented by 1. This process continues until we have processed k elements. The k-th element encountered in this process is our result.

Code Implementation:

#include <bits/stdc++.h>

using namespace std;

int find(int arr1[], int arr2[], int m, int n, int k)

{

    int d = 0, i = 0, j = 0;

    // Keep taking smaller of the current

    // elements of two sorted arrays and

    // keep incrementing k

    while (i < m && j < n) {

        if (arr1[i] < arr2[j]) {

            d++;

            if (d == k)

                return arr1[i];

            i++;

        }

        else {

            d++;

            if (d == k)

                return arr2[j];

            j++;

        }

    }

    // If array arr2[] is completely traversed

    while (i < m) {

        k++;

        if (d == k)

            return arr1[i];

        i++;

    }

    // If array arr1[] is completely traversed

    while (j < n) {

        d++;

        if (d == k)

            return arr2[j];

        j++;

    }

}

// Driver Code

int main()

{

    int A[5] = { 2, 3, 6, 7, 9 };

    int B[4] = { 1, 4, 8, 10 };

    int k = 5;

    cout << find(A, B, 5, 4, k);

    return 0;

}

Output:

6

Time Complexity: O(k) 

Auxiliary Space: O(1)

3. [Efficient Approach] Using Binary Search 

We know that the Kth element will lie either in arr1[] or in arr2[], so we can maintain 2 search spaces: [arr1, arr1 + n] and [arr2, arr2 + m] to find the kth element. Find the midpoints of both the search spaces, say mid1 and mid2. mid1 tells that the kth element can lie in the range [arr1, arr1 + mid1] and mid2 tells that kth element can lie in the range [arr2, arr2 + mid2].

Now, we can have 2 cases:

Case 1: (mid1 + mid2 < k), this means that we have taken less than k elements in our search space and we need to include more elements.

• If (arr1[mid1] > arr2[mid2]), means that there are larger elements in arr1[] so we should include more elements from arr2[].
• If (arr1[mid1] <= arr2[mid2]), means that there are larger elements in arr2[] so we should include more elements from arr1[].

Case 2: (mid1 + mid2 >= k), this means that we have taken more than or equal to k elements in our search space and we might need to remove extra elements.

• If (arr1[mid1] > arr2[mid2]), means that there are larger elements in arr1[] so we should remove the extra elements from arr1[].
• If (arr1[mid1] <= arr2[mid2]), means that there are larger elements in arr2[] so we should remove the extra elements from arr2[].

We keep on reducing the search space till we reach the kth element of the merge sorted array.

Code Implementation:

#include <iostream>

using namespace std;

// Recursive function to find the kth element in two sorted

// arrays

int kth(int* arr1, int* arr2, int* end1, int* end2, int k)

{

    // If the first array is exhausted, return the k-th

    // element from the second array

    if (arr1 == end1)

        return arr2[k];

    // If the second array is exhausted, return the k-th

    // element from the first array

    if (arr2 == end2)

        return arr1[k];

    // Calculate midpoints for both arrays

    int mid1 = (end1 - arr1) / 2;

    int mid2 = (end2 - arr2) / 2;

    if (mid1 + mid2 < k) {

        // If the value at mid1 in the first array is

        // greater, discard the left part of the second

        // array

        if (arr1[mid1] > arr2[mid2])

            return kth(arr1, arr2 + mid2 + 1, end1, end2,

                       k - mid2 - 1);

        // Otherwise, discard the left part of the first

        // array

        else

            return kth(arr1 + mid1 + 1, arr2, end1, end2,

                       k - mid1 - 1);

    }

    else {

        // If the value at mid1 in the first array is

        // greater, discard the right part of the first

        // array

        if (arr1[mid1] > arr2[mid2])

            return kth(arr1, arr2, arr1 + mid1, end2, k);

        // Otherwise, discard the right part of the second

        // array

        else

            return kth(arr1, arr2, end1, arr2 + mid2, k);

    }

}

// Function to find the k-th element in two sorted arrays

int kthElement(int arr1[], int arr2[], int n, int m, int k)

{

    return kth(arr1, arr2, arr1 + n, arr2 + m, k - 1);

}

int main()

{

    // Sample Input

    int n = 5, m = 4;

    int arr1[] = { 2, 3, 6, 7, 9 };

    int arr2[] = { 1, 4, 8, 10 };

    int k = 5;

    cout << kthElement(arr1, arr2, n, m, k);

    return 0;

}

Output:

6

Time Complexity: O(log n + log m)

Auxiliary Space: O(logn + logm)