Partner Community Techplayon Codeplayon Telcosought
LeetCode

Leet code | Problem 4: Median of Two Sorted Arrays

ByAdmin

Jul 4, 2022

Problem Name: Median of Two Sorted Arrays

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.
The overall run time complexity should be O(log (m+n)).

Example 1:

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.

Example 2:

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

Constraints:

  • nums1.length == m
  • nums2.length == n
  • 0 <= m <= 1000
  • 0 <= n <= 1000
  • 1 <= m + n <= 2000
  • -106 <= nums1[i], nums2[i] <= 106

Solution:

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){

    if((nums1 == NULL) || (nums2 == NULL)){
        return 0;
    }

    int maxLen = nums1Size + nums2Size;
    int temp1 = 0;
    int temp2 = 0;
    int value = maxLen/2 + 1;

    int *out = (int *)calloc(maxLen, sizeof(int));
    if(out == NULL)
    {
        return 0;
    }

    for(int i = 0; i < value; i++)
    {
        if((temp1 < nums1Size) && (temp2 < nums2Size))
        {
            if(nums1[temp1] < nums2[temp2])
            {
                out[i] = nums1[temp1];
                temp1++;
            }
            else
            {
                out[i] = nums2[temp2];
                temp2++;
            }
        }
        else if(temp1 < nums1Size)
        {
            out[i] = nums1[temp1];
            temp1++;
        }
        else
        {
            out[i] = nums2[temp2];
            temp2++;
        }
    }

    temp1 = maxLen/2;

    if(maxLen%2)
    {
        return (double)out[temp1];
    }

    return (double)(out[temp1] + out[temp1 - 1])/2;
}