The other day I was working my way through some problems on LeetCode to try and brush up on my algorithm/problem solving skills and came across this problem. Here was the problem statement:

There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)). You may assume nums1 and nums2 cannot be both empty.

Below is one of the examples that was in the problem statement:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Oddly enough, the solution to this problem was immediately apparent to me and I felt like I had a Sean Parent momment where I could confidently identify a STL algorithm that would aid me in my solution. The algorithm I thought of was std::merge. I first became familiar with std::merge when I came across the fstl project on Github; a very fast .stl viewer written in C++ with a Qt5 frontend.

The stipulation of std::merge is that both of the input ranges must already be sorted. If you notice, this is explicity mentioned in the problem statement; we are guarunteed that the input arrays are already sorted. This makes the merge algorithm a perfect fit.

Before showing you my solution, please take a look at one of the given solutions by LeetCode. This particular solution was written in Python which as a language has a reputation of being concise and easy to read.

def median(A, B):
    m, n = len(A), len(B)
    if m > n:
        A, B, m, n = B, A, n, m
    if n == 0:
        raise ValueError

    imin, imax, half_len = 0, m, (m + n + 1) / 2
    while imin <= imax:
        i = (imin + imax) / 2
        j = half_len - i
        if i < m and B[j-1] > A[i]:
            # i is too small, must increase it
            imin = i + 1
        elif i > 0 and A[i-1] > B[j]:
            # i is too big, must decrease it
            imax = i - 1
        else:
            # i is perfect

            if i == 0: max_of_left = B[j-1]
            elif j == 0: max_of_left = A[i-1]
            else: max_of_left = max(A[i-1], B[j-1])

            if (m + n) % 2 == 1:
                return max_of_left

            if i == m: min_of_right = B[j]
            elif j == n: min_of_right = A[i]
            else: min_of_right = min(A[i], B[j])

            return (max_of_left + min_of_right) / 2.0

Now, don’t get me wrong, the python solution is well written. I’m not knocking the solution in any way, and I do enjoy programming in python as well. But…feast your eyes on the C++ solution I came up with:

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        vector<int> temp;
        std::merge(nums1.begin(), nums1.end(),
                  nums2.begin(), nums2.end(),
                  std::back_inserter(temp));
        
        auto size = temp.size();
        auto mid = size/2;
        
        return size %2 == 0 ? (temp[mid] + temp[mid-1]) / 2.0 : (double) temp[mid];
    }
};

I found it to be surprisingly short and very easy to write. Now granted, if you don’t know what std::merge does, then this solution is arguably less readable than the Python one. But, if you are familiar with algorithms in the STL, then this is elegant, easy to read and concise. It also turns out to be extremely performant. According to LeetCode, this solution executes in 20 ms (for the given test cases, 2048 in all) and has a memory footprint of 10.7 MB. This means that my solution beat 92.87 % of all other C++ submissions! I also tried a solution where I pre-allocate space in the temp vector for all the elements and then remove the use of std::back_inserter but this increased execution time to 24 ms but did reduce memory usage to 10.0 MB.

How about you? Have you had similar experiences with C++ versus other languages? Do you have a better way to solve this same solution to squeeze out even more performance? Leave a comment down below with your thoughts! Also be sure to subscribe to my blog so that you don’t miss another post. You can also follow me on Github.

Leave a Comment

Your email address will not be published. Required fields are marked *

Loading...