Leetcode Problem 4: Median of Two Sorted Arrays

The essence of this exercise was to write a median function instead of using a third-party library. The problem description is quite straightforward, and the trick to solving this is to realise that by sorting the merged array, without removing duplicates, we essentially have to find the middle element of the merged array by splitting it in two even parts. That means distinguishing between two cases:

  1. merged array is even –> there will be two middle elements that will have to be averaged to get the median

  2. merged array is odd –> there is only one middle element and that will be the median

We use length of the array and the modulo % operator to find out if the merged array is odd-sized or even.

Python solution Link to heading


class Solution:
    def findMedianSortedArrays(self, nums1: list[int], nums2: list[int]) -> float:
        merged = sorted(nums1 + nums2)
        k = len(merged)

        # case 1: merged array is even -> two numbers will make up the median
        if k % 2 == 0:
            # find the two middle elements
            l_1 = merged[:(k // 2)]
            l_2 = merged[(k // 2):]
            r = l_1[-1]  # right-most elem in left list
            l = l_2[0]   # left-most elem in right list
            median = (r + l) / 2
        # case 2: merged array is odd -> only one number makes up the median and it's the middle elem
        else:
            median = merged[(k - 1) // 2]

        return float(median)

C++ solution Link to heading


class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        double median;
        vector<int> merged;
        merged.reserve(nums1.size() + nums2.size());
        merged.insert(merged.end(), nums1.begin(), nums1.end());
        merged.insert(merged.end(), nums2.begin(), nums2.end());
        sort(merged.begin(), merged.end());
        int k = merged.size();

        if (k % 2 == 0) {
            vector<int> l_1(merged.begin(), merged.end() - (k / 2));
            vector<int> l_2(merged.begin() + (k / 2), merged.end());
            int r = l_1.back();
            int l = l_2.front();
            double  remainder = (r + l) % 2;
            median = (r + l) / 2 + (remainder / 2);
        }
        else {
            median = merged[(k - 1) / 2];
        }

        return median;
    }
};

My initial approach was to avoid sorting because it is expensive, and instead opt for a loop to traverse both arrays in parallel, but the code became convoluted fairly quickly as I had to:

  1. find out which of the two lists was smaller/bigger

  2. traverse both arrays in parallel

  3. keep track of whichever element of the two lists was smaller as I was traversing both, and adding the smaller element first, and the bigger one after, to a new array

  4. keep track of leftovers from the first loop, i.e. A = [1, 4, 5] B = [2, 3] -> C = [1, 2, 3, 4], A = [5], B = []. The 5 in A will be ignored if I were to use for a, b in zip(A, B) in step 1.; yet the 5 still needs to be added to C.

Python statistics Link to heading

Runtime: 88 ms         -> beats 81.44 % of python3 submissions.
Memory Usage: 14.4 MB  -> beats 93.41 % of python3 submissions.

C++ statistics Link to heading

Runtime: 16 ms         -> faster than 98.19% of C++ online submissions
Memory Usage: 14.4 MB  -> less than 20.34% of C++ online submissions.

Complexity analysis Link to heading

  • Time complexity: O(n log(n)). We assume worst-case scenario where k elements in merged need to be sorted.

  • Space complexity: O(n). We need the extra space to account for merged of size k, where k = len(nums1) + len(nums2).



Share on:
LinkedIn