It’s been a while since I created this site. I’ve been thinking about pulling some bits out of my older sites and blogs to put here before I actually continue on with this thing, but that proved to be rather tedious work. So after almost two years I figured that I’d better start a new life, so to speak, and be done with it.

So here is my first post in this new life. I have recently discovered the LeetCode site which is an awesome tool for getting ready for a software engineer interview. It’s not like I’m going to do one any time soon (although who knows?), but I felt that it’s a great chance to polish up my coding skills, so I went on.

At first I looked up solutions if I was unable to find one myself in a matter of a few hours. After doing that several times, though, I found it disappointing. While some of those problems required knowledge of arcane algorithms that people like Knuth spent tens of years to develop, some others only required hard thinking, and I felt like I was giving up too early. So I started looking harder for solutions and stopped looking them up. In the worst case, when I felt like I need a very specific algorithm to solve a part of the problem, I’d look up that very algorithm and then start to think how I would go about using it in this problem.

One of the problems I had to solve recently was this. Find the median of two sorted arrays of integers. The median is defined as the middle number of the array that would be the result of merging the two arrays together into one sorted array. And if this array would have even number of elements, then the median is the average of the two middle ones. The required time complexity was , where *n* and *m *are array sizes (it would be trivial to solve in linear time).

And this problem baffled me completely. It was pretty obvious that it doesn’t require any fancy algorithms. No knowledge of graphs and trees and whatnot would help me in this problem. The logarithmic complexity requirement obviously meant some sort of a binary search, but how would one go with binary searching *two* arrays?

My first though was to take medians of the two arrays and compare them. Never mind the odd/even size cases for now. If the medians are equal, then it is probably the answer. The idea is that if I was to merge the arrays, then half of the elements from the second array would go to the left part and half to the right part, so the median will remain the median. But what if they are not equal? Suppose the median of the second array is larger. That means that the second array has more elements that are larger than the median of the first one. It follows that if I was to merge the second array into the first one, then the median of the first one will shift left, so the real median is greater than or at least equal to it. By the same logic, if I was to merge the first array into the second one, it becomes clear that the median must also be less than or at least equal to the median of the second array.

So far so good. That gets rid of the left part of the first array and the right part of the second array. If I am able to continue this process, then I’ll get exactly complexity. But continuing this process proved more complicated than it seemed because it makes no sense any more to pick medians of the remaining arrays. I’d get a wrong answer because once I got rid of some elements, it’s not the median any more that I’m looking for. At least not if the arrays are of different sizes. Now I understand that if I continued with that approach, I’d get the right answer if I was able to figure out what I was looking for exactly. And that’s is the *k*th smallest element. For the median it’s roughly th element. And by throwing away some elements, I reduce the problem to the problem of finding th, where *l* is the number of elements I have thrown away. But at that time I wasn’t able to get a good grasp of the exact nature of the problem, so I got stuck.

The next idea was to use a binary search on the first array. Take the middle element, then check if it’s the median or not. How do I check? Well, the median needs to have exactly the same (plus-minus one if the length is even) amount of elements less than or equal to it to the left and greater than or equal to the right. For any given element of the second array, I know how many elements are to the left and to the right of it are there, but now I need to find out how many of them are in the second array. I can determine that by performing a binary search on the second array. If the would-be median is not there, then I find its insertion point and I know exactly how many elements less than and greater than are there. If it is there, though, then I need to look to the left and to the right of it because there may be many repeating elements that are equal to it. By repeating this process, I’d find the median if it is in the first array. If it’s not, then I need to repeat the whole thing for the second one. And for even sum of lengths I need to do the same thing for the second median element. Since I am performing a binary search, and on each step there is another binary search, the resulting complexity is , which is not exactly what we want either.

And then I saw the light. When doing the binary search, I need not calculate how many elements less/greater than or equal to the would-be median there are in the second array! I already know how many are there in the first one, so I know exactly how many I am lacking. What I need to check is whether there is exactly the right amount in the second array. I can determine that instantly by looking at the elements *i* and *i-1* in the second array, where *i* is the number of the lacking elements to the left of the would-be median. If the *i-1*th element is less than or equal to the would-be median and the *i*th element is greater than or equal to it, then it is the median. Note that both of these conditions cannot be false because the array is sorted. If the first condition is false, it means that there are not enough elements in the second array, so the median must be somewhere to the right in the first array (if it’s there in the first place). If the second condition is false, it means that there are too many elements and the median is to the left.

If the process finds the median, then all is good. If it doesn’t then I now have an insertion point, that is, the place where it would be if it was there. But that means I know exactly how many elements less than median are there in the first array! That gives me the location of the median in the second array instantly! Bingo!

Moreover, since I am performing a binary search on only one array, I might as well just pick the smallest one. That gives complexity! Although it’s only about twice as faster than the required one if the sizes are of the same order.

And to make things even better, I don’t need to repeat the process twice for even sizes. If I find the first median, then the next one must be right after it in one of the arrays. And since I know the position of the first median in one array and the insertion point in another, I can just check both, and pick the minimum one.

The full code for this solution is below. Somehow it beats less than 5% of other solutions on LeetCode, but that doesn’t mean much for two reasons. First is that people tend to take the best solution published by other submitters and submit them as their own simply to check whether that solution is really that fast (there is no way to figure that out without submitting). That leads to large peaks at the best solutions. Another reason is that my solution is 8 ms, while the best ones are 5 ms. But 3 ms is very little difference to measure precisely and I don’t know exactly what the margin of error is.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 |
public double findMedianSortedArrays(int[] nums1, int[] nums2) { if (nums1.length == 0) { return singleArrayMedian(nums2); } else if (nums2.length == 0) { return singleArrayMedian(nums1); } final int k = nums1.length + nums2.length; int[] smaller = nums1.length <= nums2.length ? nums1 : nums2; int[] bigger = smaller == nums1 ? nums2 : nums1; int[] median = findMedian(smaller, bigger, (k - 1) / 2 + 1); int m1 = median[0] >= 0 ? smaller[median[0]] : bigger[median[1]]; if (k % 2 == 1) return m1; // For even lengths, we need to find the next median. // It should be somewhere nearby! int i1 = median[0] >= 0 ? median[0] + 1 : -median[0] - 1; int i2 = median[1] >= 0 ? median[1] + 1: -median[1] - 1; int m2; if (i1 == smaller.length) { m2 = bigger[i2]; } else if (i2 == bigger.length) { m2 = smaller[i1]; } else { m2 = Math.min(smaller[i1], bigger[i2]); } return ((double) m1 + m2) / 2.0; } /** * Finds median or one of the medians. The median coordinate is given * by the {@code leCount} parameter which can be though of as 1-based * index of the median (like in the find kth element problem). * The returning value contains two values: first for the {@code nums1} * array, second for the {@code nums2} one. One of the values is a * non-negative index indicating where the median was found. The other one * is an insertion point like in binary search, that is, {@code -index - 1}. * Unlike binary search, however, the median may actually be present at * that point too, the algorithm just doesn't check that. * * @param nums1 the first array * @param nums2 the second array * @param leCount the number of the elements in the merged array that * are less than or equal to the median * @return an array of one index and one insertion point */ private int[] findMedian(int[] nums1, int[] nums2, int leCount) { int s1 = 0, e1 = nums1.length - 1; while (s1 <= e1) { int mid1 = (s1 + e1) / 2; // We have exactly mid1 + 1 elements in the first array that // are less than or equal to nums1[mid1] (including itself). // If mid1 is the median, then there must be exactly // leCount - (mid1 + 1) elements in the second array that // are less than or equal to the would-be median. // All subsequent elements must be greater than or equal, // so they can be put into the right half during the merge. int le2 = leCount - (mid1 + 1); assert le2 >= 0 && le2 <= nums2.length; if ((le2 == 0 || nums2[le2 - 1] <= nums1[mid1]) && (le2 == nums2.length || nums2[le2] >= nums1[mid1])) { return new int[] {mid1, -le2 - 1}; } else if (le2 > 0 && nums2[le2 - 1] > nums1[mid1]) { // missed, the median must be to the right s1 = mid1 + 1; } else { // or to the left e1 = mid1 - 1; } } // Haven't found the median in the first array, but we now know // where it would be if it was there. That means we know exactly // how many elements less than the median are here. That gives // us the exact answer where the median is in the second array! int mid2 = leCount - s1 - 1; assert mid2 >= 0 && mid2 < nums2.length; return new int[] {-s1 - 1, mid2}; } private static double singleArrayMedian(int[] nums) { if (nums.length % 2 == 0) { return ((double) nums[nums.length / 2 - 1] + nums[nums.length / 2]) / 2.0; } else { return nums[nums.length / 2]; } } |