The kth largest element from two sorted arrays

January 5, 2017

Introduction
Spent over 2 hours to study Leetcode 4 and Leetcode 215: the medium of two sorted array, and then Leetcode 215: the kth largest element from the array, and then, Julia spent over one hour to work on the code for the algorithm: the kth largest element from two sorted array.

Workout

Here is the C# practice: binary search, time complexity: not O(lg n + lg m), smaller one: O(lg(n+m)), n, m are the length of two sorted arrays.

Julia likes to work on the test case a little more time, 20 - 30 minutes, and then post the algorithm on stackexchange.com for a code review.

Read the article again, learn more about the analysis.

January 9, 2017
The most important feedback about the code - code review:
Just so you know, your solution appears to be O(logk∗(n+m))$O(\log k\ast (n+m))$. The reason is that ArraySplice() makes a copy of the array, which takes either O(n)$O(n)$ or O(m)$O(m)$ time. If you would just avoid doing the copy and instead pass a starting index for each array to your function, you would be down to O(logk)$O(\log k)$ time. – JS1

Actionable Items:

1. Read a few articles about the algorithm, list here:

2. Write a new version of algorithm to solve all issues, post it on code review. Learn by doing.

3. C# practice with the correction of time complexity issue - array splice. Code is here.