4. Median of Two Sorted Arrays: From intuitive to optimized(Java, Hard)

• LeetCode 4: Median of Two Sorted Arrays

Problem Overview

Finding the median of two sorted arrays is a classic problem that can be solved in multiple ways. We'll explore both an intuitive approach and an optimized solution that meets the O(log(min(m,n))) time complexity requirement.

Approach 1: Intuitive Solution (Merge Approach)

How It Works

The most straightforward approach is to merge the two sorted arrays and then find the median directly.

1. Merge Process: Use two pointers to merge both sorted arrays into a single sorted array
2. Median Calculation:
   • If total length is odd: return the middle element
   • If total length is even: return the average of the two middle elements

Example Walkthrough

Example 1 (Odd Length): Arrays nums1 = [1, 3] and nums2 = [2]

1. Merge: [1, 2, 3]
2. Total length = 3 (odd)
3. Median = merged[3/2] = merged[1] = 2

Example 2 (Even Length): Arrays nums1 = [1, 2] and nums2 = [3, 4]

1. Merge: [1, 2, 3, 4]
2. Total length = 4 (even)
3. Median = (merged[4/2-1] + merged[4/2]) / 2 = (merged[1] + merged[2]) / 2 = (2 + 3) / 2 = 2.5

Algorithm Implementation

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int[] merged = new int[m + n];

        int i = 0, j = 0, k = 0;

        // Merge the two arrays
        while (i < m && j < n) {
            if (nums1[i] <= nums2[j]) {
                merged[k++] = nums1[i++];
            } else {
                merged[k++] = nums2[j++];
            }
        }

        // Add remaining elements from nums1
        while (i < m) {
            merged[k++] = nums1[i++];
        }

        // Add remaining elements from nums2
        while (j < n) {
            merged[k++] = nums2[j++];
        }

        // Find median
        int total = m + n;
        if (total % 2 == 1) {
            return merged[total / 2];
        } else {
            return (merged[total / 2 - 1] + merged[total / 2]) / 2.0;
        }
    }
}

Complexity Analysis

• Time Complexity: O(m + n) - we need to traverse both arrays completely
• Space Complexity: O(m + n) - we create a merged array of size m + n

Pros and Cons

Pros:

• Easy to understand and implement
• Straightforward logic
• Works for any size arrays

Cons:

• Uses extra space for merged array
• Doesn't meet the O(log(min(m,n))) requirement
• Not optimal for large arrays

Approach 2: Optimized Solution (Binary Search)

How It Works

This solution uses divide-and-conquer to find the k-th smallest element without merging the arrays.

Main Method Logic

• Odd total length: Find the element at position n/2
• Even total length: Find the average of elements at positions n/2-1 and n/2

Core Algorithm: solve Method

Base Cases: When one array segment is exhausted, the k-th element must be in the other array.

Binary Search Logic: Compare middle elements of both current segments.

Elimination Strategy: The algorithm works by comparing middle elements and their positions:

• If aIndex + bIndex < k: The k-th element is in the "right half", so eliminate the smaller left portion
• If aIndex + bIndex >= k: The k-th element is in the "left half", so eliminate the larger right portion

Key Insight

By comparing middle elements and their positions, we can determine which half of the search space contains our target element, allowing us to discard the other half safely. This is what gives us the logarithmic time complexity.

Example Walkthrough

Example 1 (Odd Length): Arrays A = [1, 3] and B = [2], finding median (k=1)

1. Initial Call: solve(A, B, 1, 0, 1, 0, 0)
2. Setup: aIndex = 0, bIndex = 0, aValue = 1, bValue = 2
3. Decision: aIndex + bIndex = 0 < k = 1 (right half case)
4. Elimination: Since aValue < bValue, eliminate left half of A
5. Recursion: Continue until finding the answer: 2

Example 2 (Even Length): Arrays A = [1, 2] and B = [3, 4], finding median

• Need two calls: solve(A, B, 1, ...) for position 1 and solve(A, B, 2, ...) for position 2
• First call returns 2, second call returns 3
• Median = (2 + 3) / 2 = 2.5

Algorithm Implementation

class Solution {
    public double findMedianSortedArrays(int[] A, int[] B) {
        int na = A.length, nb = B.length;
        int n = na + nb;
        if ((na + nb) % 2 == 1) {
            return solve(A, B, n / 2, 0, na - 1, 0, nb - 1);
        } else {
            return ((double) (solve(A, B, n / 2, 0, na - 1, 0, nb - 1) + 
                            solve(A, B, n / 2 - 1, 0, na - 1, 0, nb - 1)) / 2);
        }
    }

    public int solve(int[] A, int[] B, int k, int aStart, int aEnd, int bStart, int bEnd) {
        // If the segment of one array is empty, it means we have passed all
        // its elements, just return the corresponding element in the other array.
        if (aEnd < aStart) {
            return B[k - aStart];
        }
        if (bEnd < bStart) {
            return A[k - bStart];
        }

        // Get the middle indexes and middle values of A and B.
        int aIndex = (aStart + aEnd) / 2, bIndex = (bStart + bEnd) / 2;
        int aValue = A[aIndex], bValue = B[bIndex];

        // If k is in the right half of A + B, remove the smaller left half.
        if (aIndex + bIndex < k) {
            if (aValue > bValue) {
                return solve(A, B, k, aStart, aEnd, bIndex + 1, bEnd);
            } else {
                return solve(A, B, k, aIndex + 1, aEnd, bStart, bEnd);
            }
        }
        // Otherwise, remove the larger right half.
        else {
            if (aValue > bValue) {
                return solve(A, B, k, aStart, aIndex - 1, bStart, bEnd);
            } else {
                return solve(A, B, k, aStart, aEnd, bStart, bIndex - 1);
            }
        }
    }
}

Complexity Analysis

• Time Complexity: O(log(min(m,n))) - we eliminate half of the smaller array in each recursive call
• Space Complexity: O(log(min(m,n))) - due to the recursive call stack

Pros and Cons

Pros:

• Optimal time complexity
• Space-efficient (no extra array needed)
• Elegant divide-and-conquer approach
• Meets the problem's efficiency requirement

Cons:

• More complex to understand and implement
• Requires careful handling of edge cases
• Recursive solution may be harder to debug

Comparison Summary

When to Use Each Approach

Use Intuitive Solution when:

• Learning the problem for the first time
• Code readability is more important than efficiency
• Working with small arrays where performance isn't critical
• Need to understand the problem before optimizing

Use Optimized Solution when:

• Performance is critical
• Working with large datasets
• Need to meet specific time complexity requirements
• In competitive programming or technical interviews

Both solutions are valid, but the optimized approach is what makes this problem worthy of its "Hard" difficulty rating and demonstrates advanced algorithmic thinking.