493. Kth Element of Two Sorted Arrays

Given two sorted arrays and an integer k, return the k-th smallest element (1-indexed) of the combined sorted order of both arrays. Input: '[a], [b], k'.

Input: '[a], [b], k'.

Output: Integer — the k-th smallest combined element.

Examples

Input: [2,3,6,7,9], [1,4,8,10], 5
Output: 6
Explanation: Combined sorted 5th element is 6.

Input: [1,2], [3,4], 3
Output: 3
Explanation: 3rd element.

Input: [1], [2], 1
Output: 1
Explanation: Smallest element.

Constraints

• 0<=m,n<=10^5
• 1<=k<=m+n
• both sorted ascending

Asked by