Median Of Two Sorted Arrays Leetcode Solution In Java

Finding the median of two sorted arrays is a classic problem that tests understanding of array manipulation and efficient algorithms. This problem often appears in technical interviews due to its requirement for an optimal logarithmic time solution.

In this article, you will learn how to approach this problem, starting with a straightforward merging technique and progressing to a more advanced binary search method to achieve optimal performance.

Problem Statement

The challenge is to find the median of two sorted arrays, nums1 and nums2, with sizes m and n respectively. The arrays are guaranteed to be sorted in ascending order. The overall run time complexity for an optimal solution should be O(log(min(m, n))). The arrays can be empty.

The median is defined as:

• For an odd total number of elements: The middle element when all elements are sorted.
• For an even total number of elements: The average of the two middle elements when all elements are sorted.

Example

Consider these two sorted arrays:

• nums1 = [1, 3]
• nums2 = [2]

When merged and sorted, the combined array is [1, 2, 3]. The median is 2.0.

Another example:

• nums1 = [1, 2]
• nums2 = [3, 4]

When merged and sorted, the combined array is [1, 2, 3, 4]. The median is (2 + 3) / 2 = 2.5.

Background & Knowledge Prerequisites

To effectively understand the solutions, readers should have a basic understanding of:

• Java Fundamentals: Variables, data types, arrays, loops, conditional statements.
• Sorted Arrays: Properties of sorted arrays, like elements being in increasing or decreasing order.
• Median Definition: How to calculate the median for a single sorted array with odd or even length.
• Binary Search (for the advanced solution): The concept of dividing a search space in half.

No specific imports beyond standard Java utilities are typically required for these solutions.

Use Cases or Case Studies

This problem, or the underlying techniques, finds applications in various scenarios:

• Data Aggregation and Analytics: When combining data from multiple sorted sources (e.g., sensor readings, financial transactions) and needing to quickly determine the central tendency of the merged dataset without fully sorting it.
• Database Query Optimization: Similar to finding the k-th smallest element in merged sorted sets, which can be useful in query planners to estimate distribution or perform range queries efficiently.
• Statistical Analysis: Calculating medians across combined samples in statistics, where maintaining sorted order is crucial.
• Algorithm Design: The core idea of partitioning and binary search on partitions is fundamental in many divide-and-conquer algorithms.
• Resource Management: Allocating resources based on median usage across different servers or processes, where each process reports its usage data in sorted order.

Solution Approaches

We will explore two primary approaches: a straightforward merging method and a more efficient binary search technique.

Approach 1: Merge and Find Median

This approach involves merging the two sorted arrays into a single new sorted array and then finding the median from this combined array.

• One-line summary: Create a new array by merging the two input arrays, then calculate the median from the merged array.

• Code example:

// Median of Two Sorted Arrays - Merge Approach
import java.util.Arrays; // Not strictly needed, but common for array utilities

public class Main {
    public static 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;

        // Step 1: Merge nums1 and nums2 into the 'merged' array
        while (i < m && j < n) {
            if (nums1[i] < nums2[j]) {
                merged[k++] = nums1[i++];
            } else {
                merged[k++] = nums2[j++];
            }
        }

        // Step 2: Add remaining elements from nums1, if any
        while (i < m) {
            merged[k++] = nums1[i++];
        }

        // Step 3: Add remaining elements from nums2, if any
        while (j < n) {
            merged[k++] = nums2[j++];
        }

        // Step 4: Calculate the median from the 'merged' array
        int totalLength = m + n;
        if (totalLength % 2 == 1) {
            // Odd length: median is the middle element
            return merged[totalLength / 2];
        } else {
            // Even length: median is the average of the two middle elements
            int mid1 = merged[totalLength / 2 - 1];
            int mid2 = merged[totalLength / 2];
            return (double) (mid1 + mid2) / 2.0;
        }
    }

    public static void main(String[] args) {
        int[] nums1_ex1 = {1, 3};
        int[] nums2_ex1 = {2};
        System.out.println("Example 1: " + findMedianSortedArrays(nums1_ex1, nums2_ex1)); // Expected: 2.0

        int[] nums1_ex2 = {1, 2};
        int[] nums2_ex2 = {3, 4};
        System.out.println("Example 2: " + findMedianSortedArrays(nums1_ex2, nums2_ex2)); // Expected: 2.5

        int[] nums1_ex3 = {};
        int[] nums2_ex3 = {1};
        System.out.println("Example 3: " + findMedianSortedArrays(nums1_ex3, nums2_ex3)); // Expected: 1.0

        int[] nums1_ex4 = {1};
        int[] nums2_ex4 = {};
        System.out.println("Example 4: " + findMedianSortedArrays(nums1_ex4, nums2_ex4)); // Expected: 1.0

        int[] nums1_ex5 = {2, 3};
        int[] nums2_ex5 = {1, 4};
        System.out.println("Example 5: " + findMedianSortedArrays(nums1_ex5, nums2_ex5)); // Expected: 2.5
    }
}

Run

• Sample output:

Example 1: 2.0
Example 2: 2.5
Example 3: 1.0
Example 4: 1.0
Example 5: 2.5

• Stepwise explanation for clarity:

1. Initialize three pointers (i, j, k) for nums1, nums2, and the merged array, respectively.
2. Iterate while both i and j are within their array bounds. Compare nums1[i] and nums2[j]. Copy the smaller element to merged[k] and increment the corresponding pointer (i or j) and k.
3. After one array is exhausted, copy any remaining elements from the other array into merged.
4. Once merged is fully populated, determine if its totalLength is odd or even.
5. If odd, the median is merged[totalLength / 2].
6. If even, the median is the average of merged[totalLength / 2 - 1] and merged[totalLength / 2].
7. Time Complexity: O(m + n) because we iterate through both arrays once to merge them.
8. Space Complexity: O(m + n) to store the merged array.

Approach 2: Binary Search (Efficient Solution)

This approach uses a binary search strategy to find the correct "partition" point in the smaller array. The goal is to divide the combined elements into two halves such that all elements in the left half are less than or equal to all elements in the right half, and the halves have an appropriate size.

• One-line summary: Apply binary search on the shorter array to find a partition that correctly divides the combined elements into two halves, where the maximum of the left half is less than or equal to the minimum of the right half.

• Code example:

// Median of Two Sorted Arrays - Binary Search Approach
public class Main {
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // Ensure nums1 is the shorter array for binary search optimization
        if (nums1.length > nums2.length) {
            return findMedianSortedArrays(nums2, nums1);
        }

        int m = nums1.length;
        int n = nums2.length;
        int totalHalfLength = (m + n + 1) / 2; // For odd total, this is the middle index. For even, it's the first of the two middle elements.

        int low = 0;
        int high = m; // Binary search range for cuts in nums1

        while (low <= high) {
            int cut1 = low + (high - low) / 2; // Partition point for nums1
            int cut2 = totalHalfLength - cut1; // Partition point for nums2

            // Calculate elements around the partition points
            // L1: Max element on the left side of nums1's partition
            // R1: Min element on the right side of nums1's partition
            // L2: Max element on the left side of nums2's partition
            // R2: Min element on the right side of nums2's partition

            int L1 = (cut1 == 0) ? Integer.MIN_VALUE : nums1[cut1 - 1];
            int R1 = (cut1 == m) ? Integer.MAX_VALUE : nums1[cut1];

            int L2 = (cut2 == 0) ? Integer.MIN_VALUE : nums2[cut2 - 1];
            int R2 = (cut2 == n) ? Integer.MAX_VALUE : nums2[cut2];

            // Check if the partition is correct
            if (L1 <= R2 && L2 <= R1) {
                // Correct partition found!
                // Calculate median based on total length
                if ((m + n) % 2 == 1) {
                    // Odd total length, median is the max of the left half
                    return Math.max(L1, L2);
                } else {
                    // Even total length, median is average of max of left half and min of right half
                    return (double) (Math.max(L1, L2) + Math.min(R1, R2)) / 2.0;
                }
            } else if (L1 > R2) {
                // L1 is too large, need to move cut1 to the left (reduce L1)
                high = cut1 - 1;
            } else { // L2 > R1
                // L2 is too large, need to move cut1 to the right (increase L1)
                low = cut1 + 1;
            }
        }
        // This part should technically not be reached if inputs are valid arrays
        return 0.0;
    }

    public static void main(String[] args) {
        int[] nums1_ex1 = {1, 3};
        int[] nums2_ex1 = {2};
        System.out.println("Example 1: " + findMedianSortedArrays(nums1_ex1, nums2_ex1)); // Expected: 2.0

        int[] nums1_ex2 = {1, 2};
        int[] nums2_ex2 = {3, 4};
        System.out.println("Example 2: " + findMedianSortedArrays(nums1_ex2, nums2_ex2)); // Expected: 2.5

        int[] nums1_ex3 = {};
        int[] nums2_ex3 = {1};
        System.out.println("Example 3: " + findMedianSortedArrays(nums1_ex3, nums2_ex3)); // Expected: 1.0

        int[] nums1_ex4 = {1};
        int[] nums2_ex4 = {};
        System.out.println("Example 4: " + findMedianSortedArrays(nums1_ex4, nums2_ex4)); // Expected: 1.0

        int[] nums1_ex5 = {2, 3};
        int[] nums2_ex5 = {1, 4};
        System.out.println("Example 5: " + findMedianSortedArrays(nums1_ex5, nums2_ex5)); // Expected: 2.5

        int[] nums1_ex6 = {10, 20, 30};
        int[] nums2_ex6 = {5, 15, 25, 35, 45};
        System.out.println("Example 6: " + findMedianSortedArrays(nums1_ex6, nums2_ex6)); // Expected: 22.5
    }
}

Run

• Sample output:

Example 1: 2.0
Example 2: 2.5
Example 3: 1.0
Example 4: 1.0
Example 5: 2.5
Example 6: 22.5

• Stepwise explanation for clarity:

1. Preprocessing: Ensure nums1 is the shorter array. This optimizes the binary search range, making it O(log(min(m, n))).
2. Define totalHalfLength: Calculate (m + n + 1) / 2. This represents the number of elements that should be in the left partition of the combined array. For odd total lengths, this is the index of the median. For even, it's the index of the first of the two middle elements.
3. Binary Search Setup: Initialize low = 0 and high = m (length of nums1). This defines the possible cut points in nums1.
4. Partition Calculation:

• Inside the binary search loop, cut1 is the partition point for nums1.
• cut2 is derived from totalHalfLength - cut1. This ensures that the combined left partitions always have totalHalfLength elements.

1. Identify Boundary Elements: For each cut1 and cut2, determine L1, R1, L2, R2:

• L1: Element just before cut1 in nums1. If cut1 is 0, use Integer.MIN_VALUE.
• R1: Element at cut1 in nums1. If cut1 is m, use Integer.MAX_VALUE.
• Similarly for L2 and R2 using nums2 and cut2.

1. Check Partition Validity:

• The partition is correct if L1 <= R2 (max of left nums1 part <= min of right nums2 part) AND L2 <= R1 (max of left nums2 part <= min of right nums1 part).
• If L1 <= R2 && L2 <= R1:
• If (m + n) is odd, the median is Math.max(L1, L2).
• If (m + n) is even, the median is (double) (Math.max(L1, L2) + Math.min(R1, R2)) / 2.0.
• If L1 > R2: cut1 is too far to the right. Adjust high = cut1 - 1.
• If L2 > R1: cut1 is too far to the left. Adjust low = cut1 + 1.

1. Time Complexity: O(log(min(m, n))) because the binary search space is the length of the shorter array.
2. Space Complexity: O(1) as only a few variables are used.

Conclusion

The problem of finding the median of two sorted arrays offers a great opportunity to explore different algorithmic trade-offs. While the merge-based approach is intuitive and easy to implement, it comes with a linear time and space complexity (O(m+n)). For larger datasets, this can become inefficient.

The binary search approach, although more complex to grasp initially, provides a significantly more efficient solution with logarithmic time complexity (O(log(min(m,n)))) and constant space complexity (O(1)). This efficiency makes it the preferred method for competitive programming and production systems where performance is critical.

Summary

• The problem requires finding the median of two sorted arrays nums1 and nums2.
• The median calculation depends on whether the total number of elements is odd (middle element) or even (average of two middle elements).
• Approach 1 (Merge and Find Median):
• Time: O(m + n)
• Space: O(m + n)
• Simple to understand, involves creating a new merged array.
• Approach 2 (Binary Search):
• Time: O(log(min(m, n)))
• Space: O(1)
• More complex, uses partitioning logic to efficiently find the median without fully merging arrays.
• It ensures the search space is always on the shorter array for optimal performance.