← DiffPush

Kth element of two sorted arrays

Baseline Binary Search · In Search Space O(log(min(N, M))) · O(1)

Picking the k-th Batch from Two Interleaved Lines

Two production lines finish batches in individually sorted priority order, and dispatch needs the batch that would land in position k if both lines were merged. Merging kilobytes of batches just to read one position is wasteful, so the pick is made by cutting both lines at complementary points.

Input: Two sorted arrays arr1 and arr2 of sizes N and M, and an integer K (1-based position in the merged order).

Output: The element that would occupy position K in the sorted merge of arr1 and arr2.

Constraints

• 1 <= N, M <= 10^5
• 1 <= K <= N + M
• 0 <= arr1[i], arr2[j] <= 10^8
• An O(log(min(N, M))) algorithm is required

Examples

Example 1

Input: {"arr1":[2,3,6,7,9],"arr2":[1,4,8,10],"k":5}
Output: 6
The merged order is 1, 2, 3, 4, 6, 7, 8, 9, 10 and the fifth batch is 6.

Example 2

Input: {"arr1":[100,112,256,349,770],"arr2":[72,86,113,119,265,445,892],"k":7}
Output: 256
Six batches precede 256 in the merged order, so it lands at position 7.

Solve this in your browser →

Also on LeetCode ↗