2-line C++ solution O(m+n) ...if you squeeze into 2 lines :-)


  • 1

    The key is that it clearly states that the first array has enough space to hold the combined length of both arrays, which means we should definitely merge to fill from the tail of the first array to make the merging in-place without overwriting any unused elements.

    void merge(vector<int>& a, int m, vector<int>& b, int n) {
            int i = m-1, j = n-1, cur = m+n; // tail of first, second and combined arrays
            while (--cur >= 0) a[cur] = (i < 0 || j >= 0 && b[j] > a[i])? b[j--] : a[i--]; // pick the larger one
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.