Find Median Of Two Sorted Arrays – LeetCode Solutions

by

LeetCode has a hard coding Problem in Its’ Algorithm Section: “Find Median Of Two Sorted Arrays”. Today We are going to solve this problem. LeetCode Link of the Problem is HERE

find median of two sorted arrays

Question

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.

Conditions

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

Solution to “Find Median Of Two Sorted Arrays“

The Skeleton Code Given by LeetCode:

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """

Firstly, I created a variable named sort, Where I stored both the Input lists merged together and Sorted them.

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        sort = sorted(nums1 + nums2)

Secondly, Check the length of the new list after both the lists are merged. If the length of the new list is odd then the middle element is median.

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        sort = sorted(nums1 + nums2)
        if len(sort)%2 == 1:
            return sort[(len(sort)/2)]

Finally, Checked for even length. If the length is even take the average of both middle elements.

Complete Solution:

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        sort = sorted(nums1 + nums2)
        if len(sort)%2 == 1:
            return sort[(len(sort)/2)]
        else:
            return (sort[(len(sort)/2)] + sort[(len(sort)/2) - 1] )/2.0

READ MORE

Python-related posts Visit HERE

C++ related posts Visit HERE

Databases related posts Visit HERE

Data Structures related posts visit HERE

Algorithms related posts visit HERE

Data Science related posts visit HERE





Share the Knowledge