median_two_sorted_arrays
dz / leetcode / median_two_sorted_arraysSummary
Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
Node Tree
Nodes
| URL | |
| content | URL |
| hyperlink | https://leetcode.com/problems/median-of-two-sorted-arrays |
| intuition | |
| content | The remark about performance being O(log(m + n)) to me sounds like a clue that this is a divide and conquer problem maybe? |
| children | is_log_always_divide_and_conquer, iterate_until_nm_div2 (guess. it's only a O((n + m)/2) solution though.), merging_takes_linear_time, total_size_n_plus_m |
| total_size_n_plus_m | |
| content | The total size of the thing is n + m. |
| children | median_n_m_div_2 |
| parents | intuition |
| median_n_m_div_2 | |
| content | The median point is going to be located at (n + m)/2. |
| children | iterate_until_nm_div2 (following this logic) |
| parents | total_size_n_plus_m |
| iterate_until_nm_div2 | |
| content | A solution I thought of could be to have a loop that iterates to the (n + m)/2 element. In the loop, you'd go between the two arrays depending on which has the smallest value. If (n + m) is even, you'd just average (n + m)/2 plus 1. This has a runtime of O((n+m/2)) (linear), not log time. |
| parents | intuition, median_n_m_div_2 |
| is_log_always_divide_and_conquer | |
| content | does log time complexity (almost always) imply a divide and conquer approach? divide and conquer because log? |
| children | something_something_midpoint (divide and conquer as thinking about midpoints) |
| parents | intuition |
| something_something_midpoint | |
| content | I wonder if the solution has something to do with midpoints? The median of each individual array is at points (n/2) and (m/2), respecitively. You can get midpoints of those, and so forth until the segment you are comparing is either of size 1 or 2. There's a divide and conquer pattern there. |
| children | what_can_be_said_about_two_midpoints |
| parents | is_log_always_divide_and_conquer |
| merging_takes_linear_time | |
| content | Merging the arrays into a new array is a linear time operation. So the solution can't be that. |
| parents | intuition |
| what_can_be_said_about_two_midpoints | |
| content | What can be said about the midpoints of two separate but sorted arrays? The values are going to be less than, greater than, or equal to eachother. Somehow, this must be a factor right? |
| parents | something_something_midpoint |
| cpp_implementation | |
| content | CPP implementation |
| children | binary_search |
| binary_search | |
| content | The solution apparently involves binary search algorithm. |
| parents | cpp_implementation |
| cpp_impl_too_complicated | |
| content | There's too much code in the CPP solution, and the author has remarked about this as well. I'm looking for a more theoretical resources on this. |
| children | algorithm_theory |
| algorithm_theory | |
| content | Algorithm Theory |
| children | leetcode_editorial, wikipedia_selection_algorithm |
| parents | cpp_impl_too_complicated |
| leetcode_editorial | |
| content | Three solutions, one linear time, two log time. |
| children | wikipedia_selection_algorithm (this boils down to a selection algorithm using a pivot) |
| parents | algorithm_theory |
| hyperlink | https://leetcode.com/problems/median-of-two-sorted-arrays/editorial/ |
| wikipedia_selection_algorithm | |
| content | Wikipedia: selection algorithm, or an algorithm for finding the kth smallest value in a collection of ordered items. |
| children | find_n_m_2_smallest |
| parents | algorithm_theory, leetcode_editorial |
| hyperlink | https://en.wikipedia.org/wiki/Selection_algorithm |
| find_n_m_2_smallest | |
| content | This problem can be rephrased as find the (n + m)/2 smallest element between two sorted arrays. So you have to understand how to do the selection algorithm, and also how to do the implicit merging. |
| parents | wikipedia_selection_algorithm |