Practice/Meta/Leetcode 4. Median of Two Sorted Arrays

Leetcode 4. Median of Two Sorted Arrays

CodingMust

Problem

You are given two sorted arrays of integers. Your task is to find the median of the combined elements from both arrays. The median is the middle value when all elements are arranged in sorted order. If there are an even number of elements, the median is the average of the two middle values.

You must solve this problem with a time complexity of O(log(m+n)), where m and n are the lengths of the two arrays. A naive approach of merging the arrays and finding the median would take O(m+n) time, which is not acceptable for this problem.

Requirements

1. Return the median as a floating-point number
2. Achieve O(log(m+n)) time complexity using binary search
3. Handle arrays of different lengths
4. Handle edge cases where one or both arrays may be empty

Constraints

• 0 ≤ nums1.length ≤ 1000
• 0 ≤ nums2.length ≤ 1000
• 1 ≤ nums1.length + nums2.length ≤ 2000
• -10^6 ≤ nums1[i], nums2[i] ≤ 10^6
• Both arrays are sorted in non-decreasing order

Examples

Example 1:

Input: nums1 = [1, 3], nums2 = [2] Output: 2.0 Explanation: When merged, the array becomes [1, 2, 3]. The median is the middle element, which is 2.

Example 2:

Input: nums1 = [1, 2], nums2 = [3, 4] Output: 2.5 Explanation: When merged, the array becomes [1, 2, 3, 4]. The median is the average of the two middle elements: (2 + 3) / 2 = 2.5

Example 3:

Input: nums1 = [], nums2 = [1] Output: 1.0 Explanation: With only one element, the median is that element itself.