LeetCode Problem 4, Medium of Two Sorted Arrays<\/a>.<\/p>\nProblem<\/h3>\n
The problem is simple: given two sorted integer arrays, find the medium element of the elements from the two arrays combined.<\/p>\n
Solution<\/h3>\n
First, instead of finding the medium of the elements, we can solve a generalized version of this problem: giving two sorted arrays, find the\u00a0k<\/em>-th smallest element for any\u00a0k<\/em>.<\/p>\nNow assume that\u00a0k<\/em>-th element is smaller or equal to the medium. Consider the two medium elements of both arrays,\u00a0m_1<\/em>\u00a0and\u00a0m_2<\/em>, if\u00a0m_1 >= m_2<\/em>, we know that any element\u00a0e<\/em>\u00a0after\u00a0m_1<\/em>\u00a0in array 1 would be\u00a0>= m_1 >= m_2<\/em>. Thus all those elements would be larger than all elements before\u00a0m_1<\/em>\u00a0in array 1 and all elements before\u00a0m_2<\/em>\u00a0in the second array, which are half of all elements. Thus\u00a0e<\/em>\u00a0is larger than the medium and can\u2019t be the solution. Thus we can eliminate all element\u00a0e<\/em>, i.e., all elements after\u00a0m_1<\/em>\u00a0in array 1.<\/p>\nSimilarly, we can eliminate half of the elements in array 2 if\u00a0m_1 <= m_2<\/em>. And similarly, if the\u00a0k<\/em>-th element is larger than the medium, we can eliminate the first half of array 1 or array 2.<\/p>\nIn every iteration, we can either eliminate half of the elements in array 1 or eliminate half of the elements in array 2. Therefore, in O(log(m)+log(n)) = O(log(m+n)) iteration, we can reduce one of the arrays to length 1, in which case we can fine the solution in O(1) time.<\/p>\n
Note<\/h5>\n
The algorithm and the proofs above are not rigid. I prefer to focus on the core idea of the algorithm instead of wasting time on the details which would make the this article incomprehensible. You can see the source code in the end if you are interested in implementation details.<\/p>\n
Takeaway<\/h3>\n
There are two takeaways of solving this problem. The first one is finding a generalized problem so that we can find a recursive solution. It\u2019s hard to find a recursive relation between finding the medium of two longer arrays and finding the medium of two shorter arrays. But it\u2019s easier to find the relationship between finding the\u00a0k<\/em>-th element of two longer arrays and the\u00a0k\u2019<\/em>-th element between two shorter arrays.<\/p>\nThe second one is how to find the recursive step. If we can reduce the size of the problem to\u00a0any<\/strong>\u00a0fraction of the original size in constant time, we can find a\u00a0O(log(n))<\/em>\u00a0solution. We don\u2019t have to reduce the size of the problem by half. In this particular problem, we only reduce half of the elements in one of the two arrays, about 1\/4 of the total elements. But this algorithm is still\u00a0O(log(n))<\/em>.<\/p>\nSource Code<\/h3>\n
My solution is posted below. I write it in good old C because it\u2019s easier to pass sub-arrays, and I am confident that getting a sub-array in C is O(1) without looking up the documents.<\/p>\n
\nint findElement(int* nums1, int nums1Size, int* nums2, int nums2Size, int k) {\n \/\/ We make sure the first array is longer than the second array \n \/\/ to make our lives easier later.\n if (nums1Size > nums2Size)\n return findElement(nums2, nums2Size, nums1, nums1Size, k);\n \n \/\/ base cases\n if (nums1Size == 0)\n return nums2[k];\n if (nums1Size == 1) {\n int e = nums1[0];\n if (k == 0)\n return (e < nums2[0]) ? e : nums2[0]; if (k >= nums2Size) \n return (e > nums2[nums2Size - 1]) ? e : nums2[nums2Size - 1];\n if (e >= nums2[k]) {\n return nums2[k];\n }\n return (e >= nums2[k-1]) ? e : nums2[k-1];\n }\n \n \/\/ induction step\n if (k + k <= nums1Size + nums2Size) {\n if (nums1[nums1Size\/2] < nums2[nums2Size\/2])\n return findElement(nums1, nums1Size, nums2, (nums2Size+1) \/ 2, k);\n else\n return findElement(nums1, (nums1Size+1) \/ 2, nums2, nums2Size, k);\n }\n else {\n if ( nums1[(nums1Size-1) \/ 2] < nums2[(nums2Size-1) \/ 2] ) \n return findElement(&nums1[nums1Size\/2], (nums1Size+1) \/ 2, \n nums2, nums2Size, k - nums1Size\/2);\n else\n return findElement(nums1, nums1Size, \n &nums2[nums2Size\/2], (nums2Size+1) \/ 2, k - nums2Size\/2);\n }\n}\n\ndouble findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {\n \/\/ if there are even number of elements, we need to find \n \/\/ the average of the two medium elements.\n int total = nums1Size + nums2Size;\n if (total & 1)\n return (double)findElement(nums1, nums1Size, nums2, nums2Size, total\/2 );\n else \n return ((double)findElement(nums1, nums1Size, nums2, nums2Size, total\/2-1 ) + \n (double)findElement(nums1, nums1Size, nums2, nums2Size, total\/2) ) \/ 2.;\n}\n\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"LeetCode has become the de facto go-to website for tech interviews. As a former competitive programmer, the LeetCode \u201chard\u201d, \u201cmedium\u201d, and \u201ceasy\u201d problems are more like \u201ceasy\u201d, \u201cvery easy\u201d, \u201cextremely easy\u201d for me. I think it would be a good idea for me to put my solutions of some of the LeetCode hard problems here. […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[8],"tags":[],"class_list":["post-18","post","type-post","status-publish","format-standard","hentry","category-coding"],"_links":{"self":[{"href":"https:\/\/sinyalee.com\/essays\/index.php?rest_route=\/wp\/v2\/posts\/18","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/sinyalee.com\/essays\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/sinyalee.com\/essays\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/sinyalee.com\/essays\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/sinyalee.com\/essays\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=18"}],"version-history":[{"count":5,"href":"https:\/\/sinyalee.com\/essays\/index.php?rest_route=\/wp\/v2\/posts\/18\/revisions"}],"predecessor-version":[{"id":131,"href":"https:\/\/sinyalee.com\/essays\/index.php?rest_route=\/wp\/v2\/posts\/18\/revisions\/131"}],"wp:attachment":[{"href":"https:\/\/sinyalee.com\/essays\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=18"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/sinyalee.com\/essays\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=18"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/sinyalee.com\/essays\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=18"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}