Kth element of two sorted arrays

Given two sorted arrays arr1 and arr2, and an integer k, the task is to find the K-th element in the merged sorted sequence of these two arrays. The arrays are not merged; the goal is to find the K-th smallest element directly.

Input/Output Examples

plaintext
Example 1:
Input:
arr1 = [2, 3, 6, 7, 9]
arr2 = [1, 4, 8, 10]
k = 5
Output: 6
Explanation: The merged array is [1, 2, 3, 4, 6, 7, 8, 9, 10]. The 5th element is 6.

Example 2:
Input:
arr1 = [1, 2, 3, 4, 5]
arr2 = [6, 7, 8, 9, 10]
k = 4
Output: 4
Explanation: The merged array is [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]. The 4th element is 4.

Example 3:
Input:
arr1 = [2, 3, 6]
arr2 = [1, 4, 5, 8, 9]
k = 7
Output: 8
Explanation: The merged array is [1, 2, 3, 4, 5, 6, 8, 9]. The 7th element is 8.

Approach to find the Kth element of two sorted arrays

  1. Use Two Pointers to Traverse Both Arrays:
    • Since both arrays are sorted, initialize two pointers at the beginning of each array (i for arr1 and j for arr2).
    • The objective is to simulate merging the two arrays by incrementing the pointers until reaching the k-th element.
  2. Compare and Increment Pointers:
    • Keep a counter to track the position of the merged array elements.
    • For each step, compare the current elements of arr1 and arr2. Move the pointer of the smaller element forward and increase the counter.
    • If one of the arrays is exhausted, simply move through the remaining elements of the other array.
  3. Stop When the K-th Element is Found:
    • When the counter reaches k, stop and return the current element, as this is the k-th element in the merged sequence.

C++ Program to find the Kth element of two sorted arrays

cpp
#include <iostream>
#include <vector>
using namespace std;

// Function to find the k-th element in two sorted arrays
int findKthElement(vector<int>& arr1, vector<int>& arr2, int k) {
    int i = 0, j = 0;
    int count = 0;

    // Traverse both arrays until we find the k-th element
    while (i < arr1.size() && j < arr2.size()) {
        if (arr1[i] < arr2[j]) {
            count++;
            if (count == k) {
                return arr1[i];
            }
            i++;
        } else {
            count++;
            if (count == k) {
                return arr2[j];
            }
            j++;
        }
    }

    // If elements remain in arr1
    while (i < arr1.size()) {
        count++;
        if (count == k) {
            return arr1[i];
        }
        i++;
    }

    // If elements remain in arr2
    while (j < arr2.size()) {
        count++;
        if (count == k) {
            return arr2[j];
        }
        j++;
    }

    return -1; // Edge case, k is out of bounds
}

int main() {
    vector<int> arr1 = {2, 3, 6, 7, 9};
    vector<int> arr2 = {1, 4, 8, 10};
    int k = 5;
    
    int result = findKthElement(arr1, arr2, k);
    cout << "The " << k << "-th element is: " << result << endl;
    return 0;
}

Java Program to find the Kth element of two sorted arrays

java
public class KthElement {

    // Function to find the k-th element in two sorted arrays
    public static int findKthElement(int[] arr1, int[] arr2, int k) {
        int i = 0, j = 0;
        int count = 0;

        // Traverse both arrays until we find the k-th element
        while (i < arr1.length && j < arr2.length) {
            if (arr1[i] < arr2[j]) {
                count++;
                if (count == k) {
                    return arr1[i];
                }
                i++;
            } else {
                count++;
                if (count == k) {
                    return arr2[j];
                }
                j++;
            }
        }

        // If elements remain in arr1
        while (i < arr1.length) {
            count++;
            if (count == k) {
                return arr1[i];
            }
            i++;
        }

        // If elements remain in arr2
        while (j < arr2.length) {
            count++;
            if (count == k) {
                return arr2[j];
            }
            j++;
        }

        return -1; // Edge case, k is out of bounds
    }

    public static void main(String[] args) {
        int[] arr1 = {2, 3, 6, 7, 9};
        int[] arr2 = {1, 4, 8, 10};
        int k = 5;
        
        int result = findKthElement(arr1, arr2, k);
        System.out.println("The " + k + "-th element is: " + result);
    }
}

Python Program to find the Kth element of two sorted arrays

python
# Function to find the k-th element in two sorted arrays
def find_kth_element(arr1, arr2, k):
    i, j = 0, 0
    count = 0

    # Traverse both arrays until we find the k-th element
    while i < len(arr1) and j < len(arr2):
        if arr1[i] < arr2[j]:
            count += 1
            if count == k:
                return arr1[i]
            i += 1
        else:
            count += 1
            if count == k:
                return arr2[j]
            j += 1

    # If elements remain in arr1
    while i < len(arr1):
        count += 1
        if count == k:
            return arr1[i]
        i += 1

    # If elements remain in arr2
    while j < len(arr2):
        count += 1
        if count == k:
            return arr2[j]
        j += 1

    return -1  # Edge case, k is out of bounds

# Example usage
if __name__ == "__main__":
    arr1 = [2, 3, 6, 7, 9]
    arr2 = [1, 4, 8, 10]
    k = 5
    result = find_kth_element(arr1, arr2, k)
    print(f"The {k}-th element is: {result}")

Time Complexity:

  • O(k): The algorithm only traverses up to k elements, making it efficient for large arrays.

Space Complexity:

  • O(1): It uses a constant amount of space regardless of the array sizes.

DSA

5183

882

Related Articles