<!DOCTYPE html>

LeetCode Solution #4: Median of Two Sorted Arrays

 body { font-family: sans-serif; } .container { width: 80%; margin: 0 auto; } h1, h2, h3 { text-align: center; } .code-block { background-color: #f5f5f5; padding: 10px; border-radius: 5px; margin: 10px 0; } img { display: block; margin: 0 auto; }

LeetCode Solution #4: Median of Two Sorted Arrays

Introduction

The Median of Two Sorted Arrays problem is a classic algorithm challenge found on LeetCode and other coding platforms. It is a popular interview question that tests a candidate's understanding of algorithms, binary search, and efficient problem-solving techniques.

The problem statement is as follows: Given two sorted arrays
nums1
and
nums2
of size
m
and
n
respectively, return the median of the two sorted arrays.

The median is the middle element of a sorted array. If the array has an even number of elements, the median is the average of the two middle elements.

Importance

This problem is important for the following reasons:

Algorithm Design and Analysis:
It requires understanding and applying various algorithms like binary search and divide-and-conquer.
Data Structures:
The solution involves working with sorted arrays and understanding their properties.
Efficiency:
The solution aims for an optimal time complexity, often striving for logarithmic time (O(log n)).
Interview Preparation:
This is a common interview question that assesses your problem-solving skills and ability to explain complex concepts.

Deep Dive into Concepts and Techniques

Understanding the Problem

The challenge lies in finding the median of two sorted arrays without merging them explicitly. Merging the arrays would result in a time complexity of O(m+n), which is not optimal for large arrays. The solution lies in leveraging the sorted nature of the arrays to find the median efficiently.

Binary Search Approach

The most common and efficient approach to solving this problem is using binary search. The key idea is to repeatedly narrow down the search space until we find the partition that divides the two arrays into equal halves.

Here's a step-by-step explanation:

Define Partitions:
We aim to divide the two arrays into two halves, where the left half of both arrays combined has the same number of elements as the right half.
Binary Search on One Array:
We perform binary search on one array (for example, nums1 ). The search space is the index range from 0 to m (size of nums1 ).
Calculate Partitions:
For each middle index partitionX in nums1 , we can calculate the corresponding partition in nums2 ( partitionY ) using the formula: partitionY = (m + n + 1) / 2 - partitionX .
Check Validity:
We check if the partitions are valid. A valid partition satisfies the following conditions:
- nums1[partitionX - 1] <= nums2[partitionY] (if partitionX > 0 )
- nums2[partitionY - 1] <= nums1[partitionX] (if partitionY > 0 )
Update Search Space:
Based on the validity of the partitions, we adjust the search space for the binary search in nums1 . If the partitions are valid, we've found the median. Otherwise, we move the search space to the left or right depending on the invalidity condition.

Illustrative Example

Let's consider the example of
nums1 = [1, 3]
and
nums2 = [2]
.

We perform binary search on
nums1
. In the first iteration, the middle index is 1 (
partitionX = 1
). We calculate
partitionY = (2 + 1 + 1) / 2 - 1 = 1
.

Checking the validity, we have:

nums1[1 - 1] <= nums2[1] : 1 <= 2 (True)
nums2[1 - 1] <= nums1[1] : 2 <= 3 (True)

Since both conditions are true, the partitions are valid, and we've found the median:
(nums1[1 - 1] + nums2[1]) / 2 = (1 + 2) / 2 = 1.5
.

Code Implementation

Here's a Python code implementation of the binary search solution:

```python

def findMedianSortedArrays(nums1, nums2):
m = len(nums1)
n = len(nums2)

  # Ensure nums1 is the shorter array
  if m &gt; n:
      nums1, nums2 = nums2, nums1
      m, n = n, m

  # Initialize the search space for binary search
  low = 0
  high = m

  while low &lt;= high:
      partitionX = (low + high) // 2  # Partition in nums1
      partitionY = (m + n + 1) // 2 - partitionX  # Partition in nums2

      # Check the validity of the partitions
      maxLeftX = nums1[partitionX - 1] if partitionX &gt; 0 else float('-inf')
      minRightX = nums1[partitionX] if partitionX &lt; m else float('inf')
      maxLeftY = nums2[partitionY - 1] if partitionY &gt; 0 else float('-inf')
      minRightY = nums2[partitionY] if partitionY &lt; n else float('inf')

      if maxLeftX &lt;= minRightY and maxLeftY &lt;= minRightX:
          # Partitions are valid. Calculate the median
          if (m + n) % 2 == 0:
              return (max(maxLeftX, maxLeftY) + min(minRightX, minRightY)) / 2
          else:
              return max(maxLeftX, maxLeftY)
      elif maxLeftX &gt; minRightY:
          # Search space needs to be moved to the left
          high = partitionX - 1
      else:
          # Search space needs to be moved to the right
          low = partitionX + 1

  return None  # Should never reach here



   </div>
   <h3>
    Time Complexity
   </h3>
   <p>
    The time complexity of this solution is O(log(min(m, n))), where m and n are the lengths of the arrays. This is due to the binary search performed on the shorter array. The search space is halved in each iteration until we find the valid partitions.
   </p>
   <h3>
    Space Complexity
   </h3>
   <p>
    The space complexity of this solution is O(1), meaning it uses a constant amount of extra space regardless of the input size. We only store a few variables for the binary search and partition calculations.
   </p>
   <h2>
    Conclusion
   </h2>
   <p>
    LeetCode Solution #4: Median of Two Sorted Arrays is an excellent example of how binary search can be applied to efficiently solve problems involving sorted data. The key is to understand the problem, break it down into smaller steps, and leverage the properties of sorted arrays. The solution provides a good illustration of algorithm design and analysis techniques. By understanding this problem and its solution, you gain valuable insights into efficient problem-solving strategies that can be applied to various other algorithms and interview questions.
   </p>
  </div>
 </body>
</html>