LeetCode 4: Median of Two Sorted Arrays in PHP

LeetCode Problem 4, Median of Two Sorted Arrays, is a popular coding interview question that tests your understanding of binary search, sorted arrays, and partitioning.

In this tutorial, we will solve this problem using PHP with a simple, step-by-step explanation. We’ll first understand what the median is, then look at an easy approach, understand why it is not optimal, and finally implement the efficient binary search solution.

Even though LeetCode marks this problem as Hard, the main idea becomes much easier once you understand how to divide two sorted arrays into left and right halves.

1. Problem Statement

You are given two sorted arrays, nums1 and nums2, of sizes m and n, respectively. Your task is to find the median of the two sorted arrays.

The overall time complexity of your solution must be O(log(m+n)).

Example 1

Example 2

Constraints

• nums1.length == m
• nums2.length == n
• 0 <= m <= 1000
• 0 <= n <= 1000
• 1 <= m + n <= 2000
• -10⁶ <= nums1[i], nums2[i] <= 10⁶

2. What Is a Median?

The median is the middle value of a sorted collection of numbers.

There are two cases to remember:

Case 1: Odd Number of Elements

When the total number of elements is odd, the median is the single middle element.

Case 2: Even Number of Elements

When the total number of elements is even, there are two middle elements. The median is their average.

Our task is to find this median without necessarily combining the two arrays.

3. Understanding the Problem

Let’s take two sorted arrays:

The challenge is to find the middle value efficiently, without doing unnecessary work. The problem specifically requires logarithmic time, which leads us to binary search.

4. Brute Force Approach (Easy to Understand)

The easiest way to solve this problem is to merge both sorted arrays into one sorted array and then find the median.

PHP Code – Brute Force

class Solution {
    function findMedianSortedArrays($nums1, $nums2) {
        $merged = array_merge($nums1, $nums2);
        sort($merged);

        $total = count($merged);
        $mid = intdiv($total, 2);

        if ($total % 2 == 1) {
            return $merged[$mid];
        }

        return ($merged[$mid - 1] + $merged[$mid]) / 2;
    }
}

How This Approach Works

1. Combine both arrays using array_merge().
2. Sort the merged array using sort().
3. Calculate the middle index.
4. If the total length is odd, return the middle element.
5. If the total length is even, calculate the average of the two middle elements.

5. Optimal Approach: Binary Search

To achieve the required O(log(m+n)) time complexity, we can use binary search to find a correct partition across the two arrays.

Instead of merging the arrays, we divide their elements into two halves:

• The left half contains the smaller elements.
• The right half contains the larger elements.
• Every element on the left must be less than or equal to every element on the right.
• The left half should contain the same number of elements as the right half, or exactly one extra element if the total count is odd.

Once we find such a partition, the median can be calculated using only the values at the partition boundaries.

6. Visualizing the Partition

Let’s use the first example:

nums1 = [1, 3]

nums2 = [2]

There are three total elements. We want two elements on the left and one on the right.

We don’t need to actually create these halves in memory. We only need to calculate where each array should be divided.

7. How to Find the Correct Partition

We use two partition positions:

• i is the number of elements taken from nums1 into the left half.
• j is the number of elements taken from nums2 into the left half.

We calculate the total number of elements that should be in the left half:

$half = intdiv($m + $n + 1, 2);
$j = $half - $i;

We always search for the partition in the smaller array. This ensures that our binary search operates on the fewest possible elements.

Partition Boundary Values

For a chosen partition, we define four boundary values:

maxLeft1 <= minRight2
maxLeft2 <= minRight1

8. Step-by-Step Binary Search Example

Consider:

nums1 = [1, 3]

nums2 = [2]

First, we make sure that nums1 is the smaller array. Its length is 2 and nums2’s length is 1, so we swap them for the search.

Now:

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

Step 1: Calculate the Left Half Size

Total length = 1 + 2 = 3.

Since the total is odd:

$half = intdiv(1 + 2 + 1, 2);
// $half = 2

We need 2 elements in the left half.

Step 2: Initialize Binary Search

Our smaller array is [2], so the possible partition positions range from 0 to 1.

$low = 0;
$high = 1;

$i = intdiv($low + $high, 2); // 0
$j = $half - $i;              // 2

Step 3: Check the First Partition

With i = 0 and j = 2:

Step 4: Update the Search Range

$low = $i + 1;

Now low = 1 and high = 1. The next partition position is i = 1, and:

$i = 1;
$j = $half - $i; // 1

Step 5: Check the Correct Partition

9. Complete PHP Solution

Here is the optimized solution for the LeetCode PHP editor. It handles odd and even total lengths, empty individual arrays, and negative numbers.

class Solution {
    function findMedianSortedArrays($nums1, $nums2) {
        // Always binary search the smaller array
        if (count($nums1) > count($nums2)) {
            [$nums1, $nums2] = [$nums2, $nums1];
        }

        $m = count($nums1);
        $n = count($nums2);

        $low = 0;
        $high = $m;
        $half = intdiv($m + $n + 1, 2);

        while ($low <= $high) {
            $i = intdiv($low + $high, 2);
            $j = $half - $i;

            $maxLeft1 = ($i == 0)
                ? PHP_INT_MIN : $nums1[$i - 1];

            $minRight1 = ($i == $m)
                ? PHP_INT_MAX : $nums1[$i];

            $maxLeft2 = ($j == 0)
                ? PHP_INT_MIN : $nums2[$j - 1];

            $minRight2 = ($j == $n)
                ? PHP_INT_MAX : $nums2[$j];

            // Check if the partition is correct
            if (
                $maxLeft1 <= $minRight2 &&
                $maxLeft2 <= $minRight1
            ) {
                // Odd total: return the largest left value
                if (($m + $n) % 2 == 1) {
                    return max($maxLeft1, $maxLeft2);
                }

                // Even total: average the middle two values
                $leftMax = max($maxLeft1, $maxLeft2);
                $rightMin = min($minRight1, $minRight2);

                return ($leftMax + $rightMin) / 2;
            }

            // Move left or right in the smaller array
            if ($maxLeft1 > $minRight2) {
                $high = $i - 1;
            } else {
                $low = $i + 1;
            }
        }

        return 0;
    }
}

10. Understanding the Code Line by Line

Step 1: Ensure the First Array Is Smaller

if (count($nums1) > count($nums2)) {
    [$nums1, $nums2] = [$nums2, $nums1];
}

We always perform binary search on the smaller array. This keeps the search range small and ensures the partition in the other array remains within its valid boundaries.

Step 2: Calculate the Half Length

$half = intdiv($m + $n + 1, 2);

This calculates how many elements should be placed in the left half. Adding 1 before integer division ensures the left half gets the extra element when the total length is odd.

Step 3: Perform Binary Search

$low = 0;
$high = $m;

while ($low <= $high) {
    $i = intdiv($low + $high, 2);
    $j = $half - $i;
}

The variables low and high define the possible partition positions in the smaller array. Each iteration selects a middle position and calculates the corresponding partition in the other array.

Step 4: Find the Four Boundary Values

$maxLeft1 = ($i == 0)
    ? PHP_INT_MIN : $nums1[$i - 1];

$minRight1 = ($i == $m)
    ? PHP_INT_MAX : $nums1[$i];

$maxLeft2 = ($j == 0)
    ? PHP_INT_MIN : $nums2[$j - 1];

$minRight2 = ($j == $n)
    ? PHP_INT_MAX : $nums2[$j];

These values tell us what the largest value on the left and the smallest value on the right are for each array.

If a partition is at the beginning of an array, the left side is empty, so we use PHP_INT_MIN. If the partition is at the end, the right side is empty, so we use PHP_INT_MAX.

Step 5: Check the Partition

if (
    $maxLeft1 <= $minRight2 &&
    $maxLeft2 <= $minRight1
) {
    // Correct partition
}

Both comparisons must be true for a valid partition. Because each input array is already sorted, checking these two boundary comparisons is enough to ensure the entire left half is less than or equal to the entire right half.

Step 6: Calculate the Median

if (($m + $n) % 2 == 1) {
    return max($maxLeft1, $maxLeft2);
}

$leftMax = max($maxLeft1, $maxLeft2);
$rightMin = min($minRight1, $minRight2);

return ($leftMax + $rightMin) / 2;

For an odd number of elements, the left half contains one extra value, so its maximum is the median. For an even number of elements, we average the maximum value on the left with the minimum value on the right.

Step 7: Adjust the Binary Search Range

if ($maxLeft1 > $minRight2) {
    $high = $i - 1;
} else {
    $low = $i + 1;
}

If the left partition of nums1 has a value that is too large compared with the right partition of nums2, we need fewer elements from nums1 in the left half, so we move left. Otherwise, we need more elements from nums1, so we move right.

11. Dry Run: Example 2

Let’s test the even-length example:

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

Both arrays are sorted, and the total length is 4. The left half should contain 2 elements.

Iteration 1

The initial partition is:

Iteration 2

12. Edge Cases

A good solution should work not only for the examples but also for special inputs.

Case 1: One Array Is Empty

nums1 = []
nums2 = [1]

The median is 1. The algorithm handles this by searching the empty smaller array, while the second array provides the middle value.

Case 2: Both Arrays Have Equal Length

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

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

Case 3: Negative Numbers

nums1 = [-5, -3]
nums2 = [-2, -1]

The two middle values are -3 and -2. The median is (-3 + -2) / 2 = -2.5. The algorithm works with negative values because it compares the values directly.

Case 4: All Elements in One Array Are Smaller

nums1 = [1, 2]
nums2 = [10, 11]

The correct partition places both elements of nums1 in the left half and both elements of nums2 in the right half. The median is (2 + 10) / 2 = 6.

13. Time and Space Complexity

Time Complexity: O(log(min(m, n)))

We perform binary search only on the smaller array. Each iteration cuts the possible search range roughly in half. Therefore, the time complexity is:

This is within the required O(log(m+n)) time complexity.

Space Complexity: O(1)

The algorithm uses only a fixed number of variables, such as the partition positions, search boundaries, and four boundary values. It does not create a merged array or another data structure.

14. Brute Force vs Optimal Solution

15. Common Mistakes to Avoid

• Using the wrong median formula: Odd and even total lengths need different calculations.
• Searching the larger array: Always swap arrays when needed so binary search operates on the smaller one.
• Incorrect partition size: Use intdiv($m + $n + 1, 2) so the left half has the extra element when the total is odd.
• Ignoring empty partition sides: Use boundary sentinels for partitions at the beginning or end of an array.
• Checking only one condition: Both partition conditions must be true before returning a median.
• Merging the arrays in the optimal solution: The optimal approach calculates the median from partition boundaries without creating a merged array.
• Forgetting that the arrays are already sorted: The solution relies on sorted input, so an additional sorting step is unnecessary.

16. Frequently Asked Questions

17. Conclusion

LeetCode 4: Median of Two Sorted Arrays is a challenging problem that becomes more approachable when we understand how to partition the two sorted arrays.

The key is to use binary search on the smaller array, find a partition that places all smaller elements on the left and larger elements on the right, and calculate the median from the partition boundaries.

Practice this problem until you can explain why the partition conditions work. This will help you build a stronger understanding of binary search and prepare for advanced coding interviews.