O(m+n) C solution clocked in at 16ms somehow


  • 0
    D

    Below is my test code for a submission in C which is O(m+n). This somehow performed better than all other C submissions clocking in at 16ms. This fact is strange to me.

    #include <stdio.h>
    
    double findMedianSortedArrays(int*, int, int*, int);
    
    int main() {
            int a1[] = {0,1,2,3,4,5};
            int a2[] = {2,6};
    
            printf("%0.1f\n", findMedianSortedArrays(a1,6,a2,2));
    }
    
    double arrsum(int *arr, int size) {
            int sum=0;
            for (int i=0; i<size; i++)
                    sum += arr[i];
            return (double)sum;
    }
    
    double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
            if (nums1Size+nums2Size == 2)
                    return (arrsum(nums1,nums1Size)+arrsum(nums2,nums2Size))/2;
            else if (nums1Size+nums2Size == 1)
                    return arrsum(nums1,nums1Size)+arrsum(nums2,nums2Size);
    
    /*
     * recursive case, nums1 and nums2 combine to have at least 3 elements
     * note that i use spacing to show order of evaluation, save some parenthesis
     * also the indexing is really tricky
     */
    
            if (!nums2Size || (nums1Size && nums1[0]<nums2[0])) {
                    nums1++;
                    nums1Size--;
            } else {
                    nums2++;
                    nums2Size--;
            }
    
            if (!nums2Size || (nums1Size && nums1[nums1Size-1]>nums2[nums2Size-1]))
                    nums1Size--;
            else
                    nums2Size--;
    
    /*
     * a tail recursive call which is highly efficient if compiler performs
     * tail recursion optimization which current c compilers probably do by default
     */
            return findMedianSortedArrays(nums1,nums1Size,nums2,nums2Size);
    }
    

  • 0
    D

    I (very badly) implemented a tail recursive version that should be O(log) and it runs even faster, clocking in at 12ms. I suspect the running time metrics have some flaws, like the machine C solutions run on recently got faster and are being compared to run times on a slower machine for older submissions.

    Here is my (very bad) O(log) solution for reference:

    #define max(a,b) (((a)>(b))?(a):(b))
    #define min(a,b) (((a)<(b))?(a):(b))
    
    double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
            if (nums1Size>nums2Size) {
                    int *t = nums1;
                    nums1 = nums2;
                    nums2 = t;
    
                    int tSize = nums1Size;
                    nums1Size = nums2Size;
                    nums2Size = tSize;
            }
    /*
     * now nums1Size <= nums2Size
     */
    
    /*
     * base case
     */
            if (nums1Size==0) {
                    if (nums2Size%2)
                            return (double)nums2[nums2Size/2];
                    else
                            return ((double)nums2[nums2Size/2-1]+(double)nums2[nums2Size/2])/2;
            } else if (nums1Size == 1) {
                    if (nums2Size == 1) {
                            return ((double)nums1[0]+(double)nums2[0])/2;
                    } else if (nums2Size%2) {
                            if (nums2[nums2Size/2]>nums1[0]) {
                                    if (nums2[nums2Size/2-1]>nums1[0])
                                            return ((double)nums2[nums2Size/2]+((double)nums2[nums2Size/2-1]))/2;
                                    else
                                            return ((double)nums2[nums2Size/2]+((double)nums1[0]))/2;
                            } else {
                                    if (nums2[nums2Size/2+1]<nums1[0])
                                            return ((double)nums2[nums2Size/2]+((double)nums2[nums2Size/2+1]))/2;
                                    else
                                            return ((double)nums2[nums2Size/2]+((double)nums1[0]))/2;
                            }
                    } else {
                            if (nums2[nums2Size/2-1]>nums1[0] && nums2[nums2Size/2]>nums1[0])
                                    return (double)nums2[nums2Size/2-1];
                            else if (nums2[nums2Size/2-1]<nums1[0] && nums2[nums2Size/2]<nums1[0])
                                    return (double)nums2[nums2Size/2];
                            else
                                    return (double)nums1[0];
                    }
            }
    
    /*
     * recursive case
     */
    
            int medianLeft1 = (nums1Size%2==1 && nums2Size%2==1) ? nums1Size/2 : nums1Size/2-1;
            int medianLeft2 = nums2Size/2-1;
            if (nums1[medianLeft1]>nums2[medianLeft2+1]) {
                    int drop1 = nums1Size-medianLeft1-1;
                    return findMedianSortedArrays(nums1,medianLeft1+1,nums2+drop1,nums2Size-drop1);
            } else if (nums2[medianLeft2]>nums1[medianLeft1+1]) {
                    int drop1 = medianLeft1+1;
                    return findMedianSortedArrays(nums1+drop1,nums1Size-drop1,nums2,nums2Size-drop1);
            } else {
                    if ((nums1Size+nums2Size)%2) {
                            return (double)min(nums1[medianLeft1+1],nums2[medianLeft2+1]);
                    } else {
                            return ((double)min(nums1[medianLeft1+1],nums2[medianLeft2+1]) + \
                                    (double)max(nums1[medianLeft1],nums2[medianLeft2]))/2;
                    }
            }
    }
    

Log in to reply
 

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