K-th Element of Two Sorted Arrays

Find the Kth Element of Two Sorted Arrays

Introduction

Given two sorted arrays and an integer k, the task is to find the element that would appear at the kth position if both arrays were merged into a single sorted array.

The challenge is that the arrays can contain up to 10^6 elements, making it impractical to actually merge them.

Therefore, we need a more efficient solution.

Understanding the Problem

Consider:

a = [2, 3, 6, 7, 9]
b = [1, 4, 8, 10]
k = 5

Merged array:

[1, 2, 3, 4, 6, 7, 8, 9, 10]

The 5th element is:

Output:

Brute Force Approach

One straightforward method is:

Merge both arrays.
Sort the merged result.
Return the kth element.

Pseudo-code:

merge arrays
return merged[k-1]

Time Complexity

O(n + m)

Space Complexity

O(n + m)

Although acceptable for small inputs, this does not satisfy the expected logarithmic complexity.

Key Observation

Instead of finding the entire merged array, we only need the kth element.

This is similar to the famous Median of Two Sorted Arrays problem.

The idea is to divide both arrays into two parts such that:

Number of elements on the left side = k

Then the largest element on the left side becomes the answer.

Partition-Based Binary Search

Suppose:

cut1 = elements taken from array a
cut2 = k - cut1

Then:

Left Side

a[0 ... cut1-1]
b[0 ... cut2-1]

Right Side

remaining elements

We need a valid partition where:

leftMaxA <= rightMinB

and

leftMaxB <= rightMinA

Once this condition is satisfied:

answer = max(leftMaxA, leftMaxB)

because the left side contains exactly k elements.

Why Binary Search Works

Both arrays are sorted.

If:

leftMaxA > rightMinB

we have taken too many elements from array a.

Move left.

If:

leftMaxB > rightMinA

we have taken too few elements from array a.

Move right.

This allows binary search on the smaller array.

Algorithm

Always perform binary search on the smaller array.
Choose a partition in the first array.
Compute the corresponding partition in the second array.
Check partition validity.
Return the maximum value on the left side.

Java Solution

class Solution {

    public int kthElement(int a[], int b[], int k) {

        int n = a.length;
        int m = b.length;

        // Always binary search on smaller array
        if (n > m) {
            return kthElement(b, a, k);
        }

        int low = Math.max(0, k - m);
        int high = Math.min(k, n);

        while (low <= high) {

            int cut1 = low + (high - low) / 2;
            int cut2 = k - cut1;

            int left1 = (cut1 == 0) ? Integer.MIN_VALUE : a[cut1 - 1];
            int left2 = (cut2 == 0) ? Integer.MIN_VALUE : b[cut2 - 1];

            int right1 = (cut1 == n) ? Integer.MAX_VALUE : a[cut1];
            int right2 = (cut2 == m) ? Integer.MAX_VALUE : b[cut2];

            if (left1 <= right2 && left2 <= right1) {
                return Math.max(left1, left2);
            }

            if (left1 > right2) {
                high = cut1 - 1;
            } else {
                low = cut1 + 1;
            }
        }

        return -1;
    }
}

Dry Run

Input

a = [2, 3, 6, 7, 9]
b = [1, 4, 8, 10]
k = 5

Since:

n > m

swap arrays.

Now:

a = [1, 4, 8, 10]
b = [2, 3, 6, 7, 9]

Try partition:

cut1 = 2
cut2 = 3

Left Side

1, 4
2, 3, 6

Right Side

8, 10
7, 9

Check:

max(left) = 6

Partition is valid.

Answer:

Another Example

Input

a = [1, 4, 8, 10, 12]
b = [5, 7, 11, 15, 17]
k = 6

Merged array:

[1, 4, 5, 7, 8, 10, 11, 12, 15, 17]

6th element:

Output:

Complexity Analysis

Binary search is performed only on the smaller array.

Time Complexity

O(log(min(n, m)))

Space Complexity

O(1)

Key Insight

Instead of merging two sorted arrays, we partition them so that exactly k elements lie on the left side. Once a valid partition is found, the largest element on the left side is precisely the kth element of the merged sorted order. This partition-based binary search technique reduces the complexity from linear time to logarithmic time, making it suitable for very large arrays.

Summary

Finding the kth element in two sorted arrays can be solved efficiently without merging the arrays. By applying a partition-based binary search on the smaller array, we ensure that exactly k elements remain on the left side of the partition. When the partition satisfies the ordering conditions, the maximum element on the left side becomes the answer. This approach achieves O(log(min(n, m))) time complexity and O(1) space complexity, making it ideal for handling very large datasets.