LeetCode Algorithms Solved

This is another problem which requires basic array manipulation.

We traverse both the sorted arrays simultaneously and adjust the elements into new merged array to arrive at the solution to compute the median.

Given m to be the number of elements in Array 1 & n to be the number of elements in Array 2, the time complexity of the solution is O(m+n).

Code for the algorithm can be found @ Median of Two Sorted Arrays – LeetCode

Solution explained below :

1. If any of the input arrays are empty we return the median of remaining array.
2. We start the traversal from the beginning of each array with two indexes corresponding to each array and add the smaller of the two elements to the merged array.
3. We repeat step 2 until either of the arrays reached the end.
4. After breaking out of the loop at the end of an array traversal, we copy the elements of remaining array to the merged array.
5. Now we compute the median of merged array using the middle element(s) of it and return the result.

Please feel free to raise any questions / doubts.

– Vamshi.