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

• 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);
}

• 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;
}
}
}

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