Hommies

Posted on May 16

LeetCode Solution: 4. Median of Two Sorted Arrays

#leetcode #dsa #programming #tutorial

Unlock the Median Magic: Diving into Two Sorted Arrays!

Hey LeetCoders and aspiring developers! 👋

Today, we're tackling a classic LeetCode challenge that often pops up in interviews: 4. Median of Two Sorted Arrays. Don't let the "Hard" tag intimidate you! While the optimal solution is quite advanced, we'll walk through a very intuitive, step-by-step approach that makes perfect sense for beginners. Let's conquer this one together!

🚀 Problem Explanation: What are we actually doing?

Imagine you have two separate lists of numbers, nums1 and nums2, and here's the crucial part: both are already sorted! Your mission is to find the median of all the numbers if you were to combine these two lists into one big, sorted list.

What's a median?

If you have an odd number of elements in a sorted list, the median is simply the middle element. For [1, 2, 3], the median is 2.
If you have an even number of elements, the median is the average of the two middle elements. For [1, 2, 3, 4], the median is (2 + 3) / 2 = 2.5.

The problem throws a curveball: it asks for an overall runtime complexity of O(log(m+n)). We'll discuss this after exploring a more straightforward solution.

Example 1:

nums1 = [1,3], nums2 = [2]
If merged and sorted: [1,2,3]
Median: 2 (middle element)

Example 2:

nums1 = [1,2], nums2 = [3,4]
If merged and sorted: [1,2,3,4]
Median: (2+3)/2 = 2.5 (average of two middle elements)

🤔 Intuition: The "Aha!" Moment

The simplest way to find the median of two sorted arrays is to just... merge them! If we combine nums1 and nums2 into a single, sorted array, finding the median becomes trivial.

However, actually building a new merged array takes O(m+n) space and time. Can we do it without fully merging? Yes! We only need to find the element(s) at the median position(s). We can simulate the merge process by using two pointers, one for each array, and pick elements one by one until we reach the median position.

Think of it like this: you're trying to find the k-th smallest element in the combined list. Since the arrays are sorted, you can always compare the current smallest elements from nums1 and nums2 to find the overall next smallest element. We'll just keep doing this until we've "counted" up to our median position.

🪜 Approach: Simulating the Merge (O(m+n) Time)

Let's break down the step-by-step logic for our beginner-friendly O(m+n) approach:

Calculate Total Length & Median Positions:
- Find the total number of elements: total_len = len(nums1) + len(nums2).
- Determine if we need one median element (odd total_len) or two (even total_len). We'll need to iterate enough times to identify these elements.
Initialize Pointers and Median Candidates:
- Use two pointers, i for nums1 and j for nums2, both starting at 0.
- Introduce two variables, m1 and m2. m1 will store the current element identified as we iterate through the "merged" sequence. m2 will store the previous m1 value. This is crucial for when we need to average two middle elements (even total_len).
Iterate to the Median Position(s):
- We need to find elements up to total_len // 2 + 1. This ensures that for an even total_len, we capture both (total_len // 2) - 1 and (total_len // 2) elements (0-indexed).
- In each iteration:
  - First, m2 = m1. The current m1 becomes the "second to last" median candidate.
  - Then, compare the elements nums1[i] and nums2[j].
    - If nums1[i] is smaller (or nums2 is exhausted), pick nums1[i], assign it to m1, and increment i.
    - Otherwise (if nums2[j] is smaller or nums1 is exhausted), pick nums2[j], assign it to m1, and increment j.
Calculate and Return the Median:
- After the loop finishes, m1 will hold the element at total_len // 2 (0-indexed) and m2 will hold the element at (total_len // 2) - 1.
- If total_len is odd, m1 is our median.
- If total_len is even, the median is the average of m1 and m2.

This approach effectively "walks" through the merged sorted array without actually building it, stopping exactly when it finds the necessary median elements.

💻 Code: The O(m+n) Merge-Like Solution (Python)

class Solution:
    def findMedianSortedArrays(self, nums1: list[int], nums2: list[int]) -> float:
        m, n = len(nums1), len(nums2)
        total_len = m + n

        # m1 will store the element at the current "median" position
        # m2 will store the element at the "median-1" position (for even total_len)
        m1, m2 = 0, 0 

        i, j = 0, 0 # Pointers for nums1 and nums2

        # Iterate (m + n) // 2 + 1 times to find the median element(s)
        # We need to iterate one more time than total_len // 2 for even arrays
        # to capture both m1 and m2 correctly.
        for count in range(total_len // 2 + 1):
            m2 = m1 # m2 takes the value m1 had in the previous iteration

            # Logic to pick the next smallest element from either nums1 or nums2
            if i < m and (j >= n or nums1[i] < nums2[j]):
                m1 = nums1[i]
                i += 1 
            else: # j < n and (i >= m or nums2[j] <= nums1[i])
                m1 = nums2[j]
                j += 1

        # Check if the sum of n and m is odd.
        if (n + m) % 2 == 1:
            return float(m1)
        else:
            ans = float(m1) + float(m2)
            return ans / 2.0

⏱️ Time & Space Complexity Analysis

For the O(m+n) solution we just explored:

Time Complexity: O(m+n)
- We iterate through the arrays up to (m+n)/2 + 1 times in the worst case. This is directly proportional to the total number of elements.
Space Complexity: O(1)
- We only use a few extra variables (m1, m2, i, j, total_len). We don't create any new arrays proportional to the input size.

A Note on the O(log(m+n)) Requirement:
The problem statement does ask for an O(log(m+n)) runtime complexity. This typically points to a more advanced solution involving binary search on partitions. That approach is significantly more complex and often involves finding a "split point" in both arrays such that the elements to the left of the split form the lower half of the merged array, and elements to the right form the upper half.

While our O(m+n) solution is intuitive and a great starting point, mastering the O(log(m+n)) binary search approach is a fantastic next step once you're comfortable with this basic idea!

🌟 Key Takeaways

Simulate, Don't Always Build: For problems involving sorted arrays and finding specific elements (like the median or k-th smallest), you often don't need to physically merge them. Simulating the merge with pointers is efficient.
Median Logic: Remember the difference between odd and even total lengths for calculating the median. Keeping track of two "median candidate" variables (m1 and m2) helps simplify this.
Complexity Matters: Always be aware of the optimal time complexity required for a problem. While an O(m+n) solution is often a good first step, understanding the O(log(m+n)) binary search approach for this specific problem is key for interviews.

Happy coding, and keep practicing! You're doing great!

Author Account: p1Hzd8mRM8
Time Published: 2026-05-17 00:12:16

DEV Community