Leet Code: Median of Two Sorted Arrays
y
Author: Jason Smith
Greetings programs!
The LeetCode problem we will be tackling in this post is Median of Two Sorted Arrays. It is classified as a hard problem.
Problem Description
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)).
Constraints:
- nums1.length == m
- nums2.length == n
- 0 <= m <= 1000
- 0 <= n <= 1000
- 1 <= m + n <= 2000
- -10^6 <= nums1[i], nums2[i] <= 10^6
Solution
Alright, this was a doozy of a problem. It was obvious that it needed to be tackled with
a binary search by the time complexity requirement. But binary search on two arrays at the
same time is not an easy task. However, if you can do binary search on one array though then all
that is really needed is to understand how to choose your middle point when looking
at two arrays.
So how do we do a binary search on two arrays? Well first we need to choose an array to be our
main array we will interact with. It always best to choose the smaller array here so we can
search less space. Then we setup this smaller array for a basic binary search by creating our
left, right, and middle indices. Then it becomes time to tackle the other array, and here is
where it gets tricky. We need to consider these two arrays as a single whole array. When we
choose our middle position in the bigger array we are looking to keep the same amount of elements
on the left and the right of both arrays the same. A small diagram may help show this better.
Small Array: [3, 5, (6), 8, 9]
Big Array: [1, 2, 3, 4, 5, (6), 7, 8, 9, 10]
Small Array: [3, 5, 6, ---------------------------------- 8, 9]
Big Array: [1, 2, 3, 4, 5, ---------------------------- 6, 7, 8, 9, 10]
So if index two is choosen in the small array as the middle then to keep about the same amount
of elements on either size we must choose either index four or five. This gives us eight elements
on the left and seven elements on the right. Now this is easy to do for the
first iteration because it is basically the middle of the array, but as we change the middle
position in the smaller array, this will need to be recalculated in the bigger array. What you
will find is that as the middle position in the small array goes more to the right, the middle
position in the big array will go more towards the left, and vice versa.
Once you understand how to calculate the middle then the only tough part left is how to move the
left and right positions in the array and determine when to stop. To handle this we need to know
the values on either side of our middle points. I call these the min (left) and max (right) for each
of the arrays. If a min would ever fall below 0 then it is the minimum value that could ever be
considered and if a max would ever fall past the array size then it is the maximum value that could
ever be considered. It is important to note that while the middle calculation is solely based on
what index value you are looking at, the min and max values are looking at the actual stored values
in the array.
With these min and max values in hand we can move our positions in the smaller array by adjusting
the left position when the big array's max value is greater than or equal to the small array's minimum
value. Otherwise we move the right position. And we are just moving these positions to be to the
small array's middle point.
This leave just the task of knowing when to stop. That will be when the small array's max is greater or
equal to the big array's min, and the small array's min is less than or equal to the big array's max.
Then you just need to the maximum of the two array's minimum values, or if there are an even number of
elements total in both arrays you take the max of the array min values added to the min of the array max
values and divide by two.
This will take O(log(m+n)) time run, but also take O(1) constant memory as you can just use the array data as it was passed in.
Conclusion
This was a hard problem indeed. Knowing how to manipulate the binary search algorithm for two arrays at the same time is not something that you need often and isn't taught that often in school. I only remember it being shown to me during a programming team practice. This was a great problem to gnaw your teeth on and learn something new if you have not seen this before.
End of Line