MEDIAN OF SORTED ARRAYS

#1

CAN U PLEASE CHECK THE APPROACH , HOW I’D SOLVED THIS QUESTION?
AND IF THERE IS ANY APPROACH BETTER THAN THIS, THAN DO LET ME KNOW PLEASE.

#2

your approach is correct

but if you want to optimize it
you have to understand few things

  1. your time complexity of code is O( (m+n) * log(m+n) )
    which is not better

  2. arrays are already sorted so again sort them is not good idea it takes more time

  • Approach: The given arrays are sorted, so merge the sorted arrays in an efficient way and keep the count of elements inserted in the output array or printed form. So when the elements in the output array are half the original size of the given array print the element as a median element. There are two cases:
    1. Case 1: m+n is odd, the median is at (m+n)/2 th index in the array obtained after merging both the arrays.
    2. Case 2: m+n is even, the median will be average of elements at index ((m+n)/2 – 1) and (m+n)/2 in the array obtained after merging both the arrays
  • Algorithm:
    1. Given two arrays are sorted. So they can be merged in O(m+n) time. Create a variable count to have a count of elements in the output array.
    2. If the value of (m+n) is odd then there is only one median else the median is the average of elements at index (m+n)/2 and ((m+n)/2 – 1).
    3. To merge the both arrays, keep two indices i and j initially assigned to 0. Compare the ith index of 1st array and jth index of second, increase the index of the smallest element and increase the count.
    4. Check if the count reached (m+n) / 2 if (m+n) is odd and store the element, if even store the average of (m+n)/2 th and (m+n)/2 -1 th element and print it.

Complexity Analysis: of this Approach

  • Time Complexity: O(m + n).
    To merge both the arrays O(m+n) time is needed.
  • Space Complexity: O(1).
    No extra space is required.

if you have more doubts regarding this feel free to ask
i hope this helps
if yes hit a like and don’t forgot to mark doubt as resolved :grinning:

#3

Thank you ji . . . .