Finding the K-th element of two sorted arrays is a common algorithm problem that tests understanding of binary search, arrays, and divide-and-conquer techniques. The problem requires determining the element that would appear at the K-th position if the two arrays were merged into a single sorted array, without actually merging them. This approach helps optimize time complexity for very large arrays.

The problem is defined as follows: Given two sorted arrays a[] and b[], and an integer k, find the K-th element in the merged sorted array.

For example, consider the arrays a = [2, 3, 6, 7, 9] and b = [1, 4, 8, 10] with k = 5. If we merged these arrays, the sorted array would be [1, 2, 3, 4, 6, 7, 8, 9, 10]. The 5th element is 6. Another example is a = [1, 4, 8, 10, 12] and b = [5, 7, 11, 15, 17] with k = 6. The combined sorted array is [1, 4, 5, 7, 8, 10, 11, 12, 15, 17], and the 6th element is 10.

A naive approach is to merge both arrays and directly access the K-th element. This method has a time complexity of O(n + m) and uses extra space, which is inefficient for very large arrays. To optimize, we use a binary search approach.

The key idea is to partition the arrays so that exactly k elements lie on the left side of the combined partition. We perform binary search on the smaller array to find the correct partition. For each partition, we check the maximum element on the left side and the minimum element on the right side of both arrays. When the condition leftMaxA <= rightMinB and leftMaxB <= rightMinA is satisfied, the K-th element is the maximum of the left-side elements.

Here is the step-by-step logic:

  1. Always apply binary search on the smaller array for efficiency.

  2. Choose a partition cut1 in the first array. The corresponding partition in the second array is cut2 = k - cut1.

  3. Determine left1 (last element of left part of first array) and left2 (last element of left part of second array), and similarly right1 and right2.

  4. If left1 <= right2 and left2 <= right1, return max(left1, left2) as the K-th element.

  5. If left1 > right2, reduce cut1; otherwise, increase cut1.

The time complexity of this approach is O(log(min(n, m))) and uses constant auxiliary space O(1).

The Java implementation is as follows:

class Solution {
    public int kthElement(int a[], int b[], int k) {
        int n = a.length;
        int m = b.length;

        // Ensure binary search is done on the 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);
            } else if (left1 > right2) {
                high = cut1 - 1;
            } else {
                low = cut1 + 1;
            }
        }
        return -1;
    }
}

This method avoids merging arrays, efficiently handles very large inputs, and directly finds the K-th element. It is widely used in coding interviews and competitive programming due to its logarithmic time complexity.

By understanding this approach, one can solve problems related to finding medians, K-th smallest/largest elements in multiple arrays, and similar divide-and-conquer array challenges.