Median of Two Sorted Arrays


Clarify the problem

  • Are the arrays always non-empty?
  • Can the arrays contain duplicate elements?
  • What should be returned if the input arrays are invalid or empty?

Analyze the problem

  • Input: Two sorted arrays nums1 and nums2.
  • Output: Median of the two sorted arrays.
  • Constraints: Overall time complexity should be O(log(m + n)).
  • Approach: We need to find the median, which is the middle element when the combined arrays are sorted. Since the arrays are already sorted, we can utilize this property to find the median efficiently.

Design an algorithm

  • Initialize two pointers, p1 and p2, pointing to the start of each array.
  • Calculate the total length, total_len, of the combined arrays.
  • Iterate until (p1 + p2) <= (total_len / 2):
    • Check if nums1[p1] <= nums2[p2]:
      • Move p1 to the next element.
    • Otherwise:
      • Move p2 to the next element.
  • If the total length is odd:
    • Return the smaller value between nums1[p1] and nums2[p2].
  • Else:
    • Return the average of the two middle elements, min(nums1[p1], nums2[p2]) and the larger value between nums1[p1-1] and nums2[p2-1].

Explain your approach

  • We initialize two pointers, p1 and p2, to keep track of the current position in each array.
  • We iterate until (p1 + p2) is less than or equal to half the total length of the combined arrays.
  • At each iteration, we compare the current elements at positions p1 and p2 and move the pointer of the smaller element to the next position.
  • After the iteration, we check if the total length is odd or even and calculate the median accordingly.

Write clean and readable code

def findMedianSortedArrays(nums1, nums2):
    total_len = len(nums1) + len(nums2)
    p1, p2 = 0, 0
    prev, curr = 0, 0

    for _ in range(total_len // 2 + 1):
        prev = curr
        if p1 < len(nums1) and (p2 >= len(nums2) or nums1[p1] <= nums2[p2]):
            curr = nums1[p1]
            p1 += 1
        else:
            curr = nums2[p2]
            p2 += 1

    if total_len % 2 == 0:
        return (prev + curr) / 2
    else:
        return curr

Test your code

# Test case 1: Even number of elements
nums1 = [1, 3]
nums2 = [2]
# Combined and sorted: [1, 2, 3]
# Median: (2 + 3) / 2 = 2.5
print(findMedianSortedArrays(nums1, nums2))  # Output: 2.5

# Test case 2: Odd number of elements
nums1 = [1, 2]
nums2 = [3, 4, 5]
# Combined and sorted: [1, 2, 3, 4, 5]
# Median: 3
print(findMedianSortedArrays(nums1, nums2))  # Output: 3

# Test case 3: Empty arrays
nums1 = []
nums2 = []
# Combined and sorted: []
# Median: None (empty array)
print(findMedianSortedArrays(nums1, nums2))  # Output: None

Optimize if necessary

  • The provided algorithm has a time complexity of O(log(m + n)) as required.
  • Further optimization may not be necessary.

Handle error cases

  • The algorithm can handle empty arrays as inputs and returns None in such cases.
  • If the arrays are not sorted, the algorithm may not produce the correct result.

Discuss complexity analysis

  • Time complexity: The algorithm has a time complexity of O(log(m + n)), where m and n are the lengths of the input arrays nums1 and nums2. The algorithm iterates until (p1 + p2) is less than or equal to half the total length of the combined arrays, resulting in a logarithmic time complexity.
  • Space complexity: The algorithm has a constant space complexity of O(1) as it only uses a few additional variables to keep track of the pointers and the previous and current elements.
Next Post Previous Post