347. K-th Element of Two Sorted Arrays

Given two sorted arrays and an integer k, find the k-th smallest element (1-indexed) if the two arrays were merged into one sorted array.

Input: The first line contains n1, the second line contains n1 space-separated sorted integers. The third line contains n2, the fourth line contains n2 space-separated sorted integers. The fifth line contains the integer k. Output: Print a single integer - the k-th smallest element of the two arrays merged.

1 <= n1, n2 <= 10^5, 1 <= k <= n1 + n2

Binary searching on the SMALLER of the two arrays (not the larger) is what keeps the complexity down to O(log(min(n1,n2))) - searching the larger array's split points instead would still be correct but strictly less efficient.

Given two sorted arrays, find the kth smallest value as if they were merged into one combined sorted array - without necessarily merging them fully. Brute force: Fully merge both sorted arrays using a standard two-pointer merge, then index directly into position k-1 - this is simple and correct, costing O(n1+n2), which is often perfectly acceptable, though not the theoretically optimal approach. Optimised: Binary searching on the SPLIT POINT (how many elements come from each array) rather than merging everything reduces the work to O(log(min(n1,n2))) - since only the smaller array's possible split points need to be tried, each checked in O(1) via simple boundary comparisons.

Since both arrays are already individually sorted, walk two pointers, one per array, exactly like the merge step of merge sort: always advance whichever pointer currently points at the smaller value and increment a counter each step. Stop as soon as the counter reaches k and report that value. This avoids sorting entirely and only does as much comparison work as needed to reach the kth element instead of building the full merged array. Time: O(k) Space: O(1)

Concatenate both arrays into one combined array and sort it from scratch, ignoring the fact that each individual array is already sorted, then return the element sitting at index k-1. This is correct because a full sort always produces the exact merged order needed, but it wastes the existing sorted order of both inputs by paying for a general-purpose sort. Time: O((n1+n2) log(n1+n2)) Space: O(n1+n2)

Binary search over a partition index in the smaller of the two arrays, deriving the matching partition index in the other array so the two partitions together always contain exactly k elements. Compare the four boundary elements around both partitions and shift the binary search bounds until every element on the left side of the combined partition is less than or equal to every element on the right side. Because the correctness of a partition is monotonic in the search index, binary search locates the valid partition, and the largest left-side element (or smallest right-side element, depending on parity) is the answer, in logarithmic time regardless of how large k is. Time: O(log(min(n1,n2))) Space: O(1)

1. Binary search on how many elements to take from the SMALLER array (say, x elements) - this automatically determines how many to take from the other array (k - x), since exactly k total must be taken. 2. Compare the 'boundary' elements just inside and just outside this split on both arrays - if they're correctly ordered (each array's included boundary is <= the other array's excluded boundary), this split is valid. 3. Adjust x up or down based on which boundary comparison fails, narrowing toward the correct split.

Time: O(log(min(n1,n2))) for the optimal binary-search-on-split approach; O(n1+n2) for the simpler merge-based approach. Space: O(1) for the binary-search approach; O(n1+n2) if fully merging.

Test k = 1 and k = n1 + n2 (smallest and largest overall), one array much smaller than the other, and n1 = n2 = 10^5 for performance.

This is essentially a specific instance of the 'median of two sorted arrays' technique - be ready to connect the two, since median is really just 'the kth element' for a specific choice of k.