Thought I should share the hints here for people that are stuck but still want to solve this. This is my thought process:
- Look up definition of median. You want to find the value that bigger than half and smaller than half. In the 1 sorted array, this is the value at index ~n/2, but we have 2 sorted arrays case here.
- My first idea is to look at median of the 1st array, and median of the second array, you can easily infer that the median of both must bigger than the min of them and smaller than the max of them, hence you can eliminate half of each array (i.e. left half of the array with smaller median).
- Now we are looking for a O(log(n+m)) solution, we want to eliminate half (or some fixed percentage) each iteration.
- So the goal is try to eliminate as many as possible while keeping track of what have been eliminated to balance the bigger half and the smaller half, I reached a dead end with this process.
What works for me:
- 1st hint: from above, I came to realize to solve this, I should approach a more generalize problem: instead of finding the median, find the x-th position value (basically bigger than x other values and smaller than (n+m-x-1) other values). if that's solved, then the median will just be x=(n+m)/2; in case n+m is not even, use floor and ceiling, and then average.
- 2nd hint: no need trying to eliminate from both side, I only try to eliminate the left side. My recursive solution reduces x each time, till it reaches x = 0 (basic case)
- 3rd hint: inspired by the 1st elimination attempt, my solution is: pick the index i1 for 1st array and index i2 for 2nd array, in a clever way, such that when comparing these 2 values, you can eliminate 1st i1 values of 1st array or the 1st i2 values of 2nd array.