🚀3. Median of 2 Sorted Arrays of Different Sizes 🧠

The problem can be found at the following link: Problem Link

💡 Problem Description:

Given two sorted arrays a[] and b[], find and return the median of the combined array after merging them into a single sorted array.

🔍 Example Walkthrough

Input:

a[] = [-5, 3, 6, 12, 15], b[] = [-12, -10, -6, -3, 4, 10]

Output:

3

Explanation: The merged array is [-12, -10, -6, -5, -3, 3, 4, 6, 10, 12, 15]. So the median of the merged array is 3.

Input:

a[] = [2, 3, 5, 8], b[] = [10, 12, 14, 16, 18, 20]

Output:

11

Explanation: The merged array is [2, 3, 5, 8, 10, 12, 14, 16, 18, 20]. The median is the average of 10 and 12, which is (10 + 12) / 2 = 11.

Input:

a[] = [], b[] = [2, 4, 5, 6]

Output:

4.5

Explanation: The merged array is [2, 4, 5, 6]. The median is (4 + 5) / 2 = 4.5.

Constraints:

• $0 ≤ a.size(), b.size() ≤ 10^6$

• $1 ≤ a[i], b[i] ≤ 10^9$

• a.size() + b.size() > 0

🎯 My Approach:

The key to solving this problem efficiently is to use binary search to find the correct partition between the two sorted arrays, without actually merging them.

Step-by-Step:

1. Ensure a is the smaller array: We will always perform binary search on the smaller of the two arrays to minimize the number of iterations. If a is larger than b, we swap them.

2. Binary Search on a: We will partition array a at a point mid1 and array b at a point mid2. The goal is to find the partition such that:

   • The left half contains the elements smaller than or equal to the elements on the right half.

   • We maintain balance such that the total number of elements on the left side and the right side is either the same or off by one (for odd total size).

3. Calculate the Median:

   • If the total number of elements (n + m) is odd, the median will be the maximum of the left elements (max(l1, l2)).

   • If the total number of elements is even, the median will be the average of the maximum of the left elements and the minimum of the right elements ((max(l1, l2) + min(r1, r2)) / 2.0).

4. Adjust the Binary Search Window:

   • If l1 > r2, adjust the search to the left side of a.

   • If l2 > r1, adjust the search to the right side of a.

Edge Case:

• One of the arrays may be empty. In such cases, we can simply calculate the median of the non-empty array.

🕒 Time and Auxiliary Space Complexity:

• Expected Time Complexity: O(log(min(n, m))), where n and m are the sizes of the arrays a and b. The binary search reduces the problem size logarithmically.

• Expected Auxiliary Space Complexity: O(1), as we are not using any additional data structures that scale with the input size.

📝 Solution Code

Code (Cpp):

class Solution {
public:
    double medianOf2(vector<int>& a, vector<int>& b) {
        if (a.size() > b.size())
            return medianOf2(b, a);

        int n = a.size(), m = b.size(), lo = 0, hi = n;
        while (lo <= hi) {
            int mid1 = lo + (hi - lo) / 2;
            int mid2 = (n + m + 1) / 2 - mid1;

            int l1 = (mid1 == 0 ? INT_MIN : a[mid1 - 1]);
            int r1 = (mid1 == n ? INT_MAX : a[mid1]);
            int l2 = (mid2 == 0 ? INT_MIN : b[mid2 - 1]);
            int r2 = (mid2 == m ? INT_MAX : b[mid2]);

            if (l1 <= r2 && l2 <= r1)
                return (n + m) % 2 == 0 ? (max(l1, l2) + min(r1, r2)) / 2.0 : max(l1, l2);

            if (l1 > r2)
                hi = mid1 - 1;
            else
                lo = mid1 + 1;
        }
        return 0.0;
    }
};

Code (Java):

class Solution {
    public double medianOf2(int[] a, int[] b) {
        if (a.length > b.length)
            return medianOf2(b, a);

        int n = a.length, m = b.length;
        int lo = 0, hi = n;

        while (lo <= hi) {
            int mid1 = lo + (hi - lo) / 2;
            int mid2 = (n + m + 1) / 2 - mid1;

            int l1 = (mid1 == 0) ? Integer.MIN_VALUE : a[mid1 - 1];
            int r1 = (mid1 == n) ? Integer.MAX_VALUE : a[mid1];
            int l2 = (mid2 == 0) ? Integer.MIN_VALUE : b[mid2 - 1];
            int r2 = (mid2 == m) ? Integer.MAX_VALUE : b[mid2];

            if (l1 <= r2 && l2 <= r1) {
                if ((n + m) % 2 == 0) {
                    return (Math.max(l1, l2) + Math.min(r1, r2)) / 2.0;
                } else {
                    return Math.max(l1, l2);
                }
            } else if (l1 > r2) {
                hi = mid1 - 1;
            } else {
                lo = mid1 + 1;
            }
        }
        return 0.0;
    }
}

Code (Python):

class Solution:
    def medianOf2(self, a, b):
        if len(a) > len(b):
            return self.medianOf2(b, a)

        n, m = len(a), len(b)
        lo, hi = 0, n

        while lo <= hi:
            mid1 = lo + (hi - lo) // 2
            mid2 = (n + m + 1) // 2 - mid1

            l1 = float('-inf') if mid1 == 0 else a[mid1 - 1]
            r1 = float('inf') if mid1 == n else a[mid1]
            l2 = float('-inf') if mid2 == 0 else b[mid2 - 1]
            r2 = float('inf') if mid2 == m else b[mid2]

            if l1 <= r2 and l2 <= r1:
                if (n + m) % 2 == 0:
                    return (max(l1, l2) + min(r1, r2)) / 2.0
                else:
                    return max(l1, l2)
            elif l1 > r2:
                hi = mid1 - 1
            else:
                lo = mid1 + 1

        return 0.0

📢 Contribution and Support

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: Any Questions. Let’s make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

---

📍Visitor Count