leetcode: Median of Two Sorted Arrays Problem in C++
Tags: algorithms, datastructures, cpp, webdev
Published: 2024-04-11 14:08:03

## Introduction:

Finding the median of two sorted arrays efficiently. In this blog post, we'll explore how to solve this problem in C++, achieving a runtime complexity of O(log(m+n)).

## Problem Statement:

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

The overall run time complexity should be O(log (m+n)).

 

**Example 1:**

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.

**Example 2:**
Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.
 

**Constraints:**

1. `nums1.length == m`
2. `nums2.length == n`
3. `0 <= m <= 1000`
4. `0 <= n <= 1000`
5. `1 <= m + n <= 2000`
6. `-106 <= nums1[i], nums2[i] <= 106`



## Approach:

To solve this problem efficiently, we'll utilise the binary search algorithm. The key insight is to partition the arrays `nums1` and `nums2` into two parts such that the elements on the left side are smaller than or equal to the elements on the right side. This partition should be such that the length of the left partition is equal to or one element larger than the length of the right partition.

## Algorithm:

1. Ensure `nums1` is not larger than `nums2`. If it is, swap them.
2. Initialize `low` and `high` as 0 and the length of `nums1`, respectively.
3. Perform a binary search on `nums1` to find the correct partition `partN1`.
4. Calculate the corresponding partition `partN2` in `nums2`.
5. Determine the maximum elements (`mxLN1` and `mxLN2`) on the left side and the minimum elements (`minRN1` and `minRN2`) on the right side.
6. Check if the partitioning is correct, ensuring that `mxLN1 <= minRN2` and `mxLN2 <= minRN1`.
7. If the partitioning is correct, calculate the median based on the lengths of `nums1` and `nums2`.
8. Adjust `low` and `high` based on the comparison of `mxLN1` and `minRN2`.
9. Repeat the binary search until the correct partition is found.

## Code C++

```cpp
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        unsigned int n = nums1.size(), m = nums2.size();

        if (n == 0 && m == 0)
            return double(0);

        if (n == 0) {
            if (m % 2 == 0) {
                return (nums2[m / 2 - 1] + nums2[m / 2]) / 2.0;
            } else {
                return nums2[m / 2];
            }
        }

        if (m == 0) {
            if (n % 2 == 0) {
                return (nums1[n / 2 - 1] + nums1[n / 2]) / 2.0;
            } else {
                return nums1[n / 2];
            }
        }

        if (n > m) {
            return findMedianSortedArrays(nums2, nums1);
        }

        int low = 0, high = n;

        while (low <= high) {
            int partN1 = (low + high) / 2;
            int partN2 = (n + m + 1) / 2 - partN1;

            int mxLN1 = (partN1 == 0) ? INT_MIN : nums1[partN1 - 1];
            int minRN1 = (partN1 == n) ? INT_MAX : nums1[partN1];

            int mxLN2 = (partN2 == 0) ? INT_MIN : nums2[partN2 - 1];
            int minRN2 = (partN2 == m) ? INT_MAX : nums2[partN2];

            if (mxLN1 <= minRN2 && mxLN2 <= minRN1) {
                if ((n + m) % 2 == 0) {
                    return (max(mxLN1, mxLN2) + min(minRN1, minRN2)) / 2.0;
                } else {
                    return max(mxLN1, mxLN2);
                }
            } else if (mxLN1 > minRN2) {
                high = partN1 - 1;
            } else {
                low = partN1 + 1;
            }
        }

        return 0.0;
    }
};
```

## Code Explanation:

- We handle edge cases where one of the arrays is empty or both arrays are empty.

- We ensure that the length of `nums1` is smaller or equal to the length of `nums2`.

- We perform a binary search to find the correct partition in `nums1`.

- We calculate the corresponding partition in `nums2`.

- We check if the partitioning is correct and calculate the median accordingly.

- We adjust the search space based on the comparison of elements.

## Complexity Analysis:
- Time Complexity: O(log(min(m, n))) - The binary search is performed on the smaller array.
- Space Complexity: O(1) - Only a constant amount of extra space is used.

## Conclusion:

We discussed how to efficiently solve the median of two sorted arrays problem in C++ using a binary search approach. By partitioning the arrays intelligently, we were able to achieve a runtime complexity of O(log(m+n)).