LeetCode Problem – Median of sorted array

Problem Statement

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 In Java

The problem of finding the median of two sorted arrays can be solved efficiently by applying a binary search algorithm. Here’s the Java solution:

public class MedianOfTwoSortedArrays {

    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int totalLength = nums1.length + nums2.length;

        if (totalLength % 2 == 0) {
            // If the total length is even, find the two middle elements
            int mid1 = findKthElement(nums1, nums2, totalLength / 2);
            int mid2 = findKthElement(nums1, nums2, totalLength / 2 + 1);
            return (mid1 + mid2) / 2.0;
        } else {
            // If the total length is odd, return the middle element
            return findKthElement(nums1, nums2, totalLength / 2 + 1);
        }
    }

    private static int findKthElement(int[] nums1, int[] nums2, int k) {
        int index1 = 0, index2 = 0;

        while (true) {
            // If one array is exhausted, return the kth element from the other array
            if (index1 == nums1.length) {
                return nums2[index2 + k - 1];
            }
            if (index2 == nums2.length) {
                return nums1[index1 + k - 1];
            }

            // Compare the current elements in both arrays and move the index accordingly
            if (nums1[index1] < nums2[index2]) {
                index1++;
            } else {
                index2++;
            }

            // Decrement k after comparing elements
            k--;
        }
    }

    public static void main(String[] args) {
        // Example 1
        int[] nums1 = {1, 3};
        int[] nums2 = {2};
        System.out.println(findMedianSortedArrays(nums1, nums2));

        // Example 2
        int[] nums3 = {1, 2};
        int[] nums4 = {3, 4};
        System.out.println(findMedianSortedArrays(nums3, nums4));
    }
}

This Java code defines a findMedianSortedArrays method that takes two sorted arrays (nums1 and nums2) as input and returns the median of the combined sorted array. The findKthElement method is a helper function used to find the kth element in the merged array using a binary search-like approach. The main method demonstrates the usage with the provided examples.

Python Solution

def findMedianSortedArrays(nums1, nums2):
    total_length = len(nums1) + len(nums2)

    if total_length % 2 == 0:
        # If the total length is even, find the two middle elements
        mid1 = find_kth_element(nums1, nums2, total_length // 2)
        mid2 = find_kth_element(nums1, nums2, total_length // 2 + 1)
        return (mid1 + mid2) / 2.0
    else:
        # If the total length is odd, return the middle element
        return find_kth_element(nums1, nums2, total_length // 2 + 1)


def find_kth_element(nums1, nums2, k):
    index1, index2 = 0, 0

    while True:
        # If one array is exhausted, return the kth element from the other array
        if index1 == len(nums1):
            return nums2[index2 + k - 1]
        if index2 == len(nums2):
            return nums1[index1 + k - 1]

        # Compare the current elements in both arrays and move the index accordingly
        if nums1[index1] < nums2[index2]:
            index1 += 1
        else:
            index2 += 1

        # Decrement k after comparing elements
        k -= 1


# Example 1
nums1 = [1, 3]
nums2 = [2]
print(findMedianSortedArrays(nums1, nums2))

# Example 2
nums3 = [1, 2]
nums4 = [3, 4]
print(findMedianSortedArrays(nums3, nums4))

In this Python version, the logic is the same as the Java solution. The findMedianSortedArrays function takes two sorted arrays (nums1 and nums2) as input and returns the median of the combined sorted array. The find_kth_element function is a helper function used to find the kth element in the merged array using a binary search-like approach. The examples demonstrate the usage of the function with the provided test cases.