PYTHON 3

Problem Complete the function findKthSmallest() to take in two sorted arrays, array1 and array2, and an integer k, and return the k-th smallest element from the two arrays. You must write an algorithm that finds the solution in O(n) (i.e. you cannot combine the two arrays and sort them again). Hint: consider the way Merge Sort works, and how we combine two sorted arrays in O(n). This problem becomes trivial once you follow the Merge Sort approach. You can safely assume that k will always be less than or equal to the length of the two arrays combined.

Examples

findKthSmallest([1, 2, 3], [4, 5, 6], 2)

returns 2 findKthSmallest([8, 10, 12], [1, 9, 13], 3)

returns 9 findKthSmallest([19, 22, 25], [20, 23, 26], 4)

returns 23