Introduction:

The "Median of Two Sorted Arrays" problem holds significant value in the realm of algorithmic programming. It presents a captivating challenge that requires finding the median value, a vital statistical measure with practical implications in various domains. The ability to solve this problem empowers us to delve into data analysis, make informed decisions, and optimize algorithms to tackle real-world scenarios effectively. In this blog, we will delve into the essence of the "Median of Two Sorted Arrays" problem, exploring its relevance in statistical analysis, finance, healthcare, and data science. By understanding its significance, we can unlock new insights and strengthen our problem-solving skills in algorithmic programming.

Problem Overview

Question:

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:

• nums1.length == m

• nums2.length == n

• 0 <= m <= 1000

• 0 <= n <= 1000

• 1 <= m + n <= 2000

• -10<sup>6</sup> <= nums1[i], nums2[i] <= 10<sup>6</sup>

Brute Force Approach - Bubble Sort and Find Median

The core concept of the problem involves two fundamental steps:

1. Merging the two arrays: Initially, we need to combine the given arrays into a single, unified array. This consolidation allows us to work with a comprehensive dataset that includes all the elements.

2. Sorting the merged array: Following the merging step, we proceed to sort the combined array in ascending order. Sorting is essential for arranging the elements properly and facilitating the determination of the median.

3. Determining the median: Once the array is sorted, we can identify the median value. If the length of the combined array is odd, the median corresponds to the middle element. However, if the length is even, the median is calculated by averaging the two middle elements.

Now let's discuss the step-by-step process of the brute-force solution:

1. Combining the arrays: We begin by merging the elements of nums1 and nums2 into a single array, which we refer to as joinedArray. This consolidation allows us to work with a unified dataset.

2. Sorting the array: To ensure the elements are in the desired order, we proceed to sort joinedArray. In this brute-force approach, we employ the bubble sort algorithm, a simple yet less efficient sorting technique. The resulting sorted array is stored in the variable sortedArray.

3. Determining the median value: Our objective is to find the median, which differs based on the size of sortedArray. If the size is odd, we adopt the following approach:

   • Calculate the middle index by dividing the size of sortedArray by 2.

   • Obtain the element located at the middle index in sortedArray, which represents the median value.

However, when the size of sortedArray is even, a slightly different approach is necessary:

• Compute the index of the first middle element by subtracting 1 from the size of sortedArray divided by 2.

• Determine the median by calculating the average of the element at the first middle index and the following element.

Below is the provided code snippet for reference:

var findMedianSortedArrays = function(nums1, nums2) {

    let middleValue = 0

    const joinedArray = nums1.concat(nums2)
    const sortedArray = bubbleSort(joinedArray)


    if(sortedArray.length%2 !== 0){

        var getDecimal = Math.floor(sortedArray.length/2)
        middleValue =  sortedArray[getDecimal]

    } else {
        var split = (sortedArray.length/2) - 1

        var median = (sortedArray[split] + sortedArray[split+1]) / 2
        middleValue = median
    }

    return middleValue
};

function bubbleSort(arr) {
  const length = arr.length;

  for (let i = 0; i < length - 1; i++) {
    for (let j = 0; j < length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        const temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }

  return arr;
}

What is the time and space complexity of this solution?

1. Time Complexity:

   • The bubbleSort function uses the Bubble Sort algorithm to sort the joinedArray, which has a length of m + n, where m is the length of nums1 and n is the length of nums2.

   • Bubble Sort has an average and worst-case time complexity of O(n^2), where n is the number of elements in the array.

   • In the worst case, the nested loops in bubbleSort will iterate (m + n) times.

   • Therefore, the time complexity of sorting the array is O((m + n)^2).

2. Space Complexity:

   • The space complexity of the code is determined by the extra space used for the joinedArray and sortedArray variables, as well as the middleValue variable.

   • The joinedArray variable holds the merged array of nums1 and nums2, which requires space for m + n elements.

   • The sortedArray variable holds the sorted version of the joinedArray, still requiring space for m + n elements.

   • The middleValue variable requires space for a single element.

   • Therefore, the space complexity is O(m + n).

Optimal Approach - Merge Sort and Find Median

Merge sort is widely regarded as a superior sorting algorithm compared to bubble sort due to its efficiency and reliability. The key advantage of merge sort lies in its solid time complexity, making it more suitable for sorting large arrays. With a time complexity of O(n log n), merge sort excels in breaking down the array into smaller, sorted segments before merging them back together. This approach ensures a streamlined and efficient sorting process. In contrast, bubble sort's time complexity of O(n^2) makes it less efficient, as it requires multiple iterations and element comparisons. As a result, merge sort stands as a sorted and solid choice for sorting tasks, particularly when handling substantial data sets.

Below is the provided code snippet for reference:

var findMedianSortedArrays = function(nums1, nums2) {

    let middleValue = 0

    const joinedArray = nums1.concat(nums2)
    const sortedArray = mergeSort(joinedArray)


    if(sortedArray.length%2 !== 0){

        var getDecimal = Math.floor(sortedArray.length/2)
        middleValue =  sortedArray[getDecimal]

    } else {
        var split = (sortedArray.length/2) - 1

        var median = (sortedArray[split] + sortedArray[split+1]) / 2
        middleValue = median
    }

    return middleValue
};

function mergeSort(arr){
    if(arr.length <= 1){
        return arr
    }

    const mid = Math.floor(arr.length/2)
    const left = arr.slice(0,mid)
    const right = arr.slice(mid)


    const sortedLeft = mergeSort(left)
    const sortedRight = mergeSort(right)

    return merge(sortedLeft, sortedRight)
}

function merge(left, right) {

    let result = [];
    let i = 0; 
    let j = 0; 


    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            result.push(left[i]);
            i++;
        } else {
            result.push(right[j]);
            j++;
        }
    }

    while (i < left.length) {
        result.push(left[i]);
        i++;
    }

    while (j < right.length) {
        result.push(right[j]);
        j++;
    }

    return result;
}

What is the time and space complexity of this solution?

1. Time Complexity:

   • The mergeSort function uses the Merge Sort algorithm to sort the joinedArray, which has a length of m + n, where m is the length of nums1 and n is the length of nums2.

   • Merge Sort has an average and worst-case time complexity of O(n log n), where n is the number of elements in the array.

   • In the worst case, the mergeSort function will recursively split the array until it reaches arrays of size 1, which takes log(n) recursive calls.

   • The merging step in the merge function takes O(n) time to merge the two sorted arrays.

   • Therefore, the time complexity of sorting the array using Merge Sort is O((m + n) log(m + n)).

2. Space Complexity:

   • The space complexity of the code is determined by the extra space used for the joinedArray, sortedArray, and the recursive calls in the mergeSort function.

   • The joinedArray variable holds the merged array of nums1 and nums2, which requires space for m + n elements.

   • The sortedArray variable holds the sorted version of the joinedArray, still requiring space for m + n elements.

   • The mergeSort function uses recursive calls, and each call creates new slices of the input array, requiring additional space for those slices.

   • However, the overall space used by the recursive calls is limited to O(log(m + n)), as the array is divided into halves.

   • Therefore, the space complexity is O((m + n) + log(m + n)), which simplifies to O(m + n).

Test Cases

To solidify your knowledge about it, it is recommended to try out various test cases.

Test Case 1: nums1 = [1, 3] nums2 = [2] Expected Output: 2.0

Test Case 2: nums1 = [1, 2] nums2 = [3, 4] Expected Output: 2.5

Test Case 3: nums1 = [0, 0] nums2 = [0, 0] Expected Output: 0.0

Test Case 4: nums1 = [] nums2 = [1] Expected Output: 1.0

Test Case 5: nums1 = [2] nums2 = [] Expected Output: 2.0

Test Case 6: nums1 = [1, 2, 5, 9] nums2 = [3, 4, 7, 8] Expected Output: 5.0

Test Case 7: nums1 = [10, 20, 30] nums2 = [40, 50, 60] Expected Output: 35.0

Test Case 8: nums1 = [1, 3, 5] nums2 = [2, 4, 6, 8] Expected Output: 4.0

Test Case 9: nums1 = [1, 3, 5, 7] nums2 = [2, 4, 6, 8] Expected Output: 4.5

Test Case 10: nums1 = [1, 3, 5, 7, 9] nums2 = [2, 4, 6, 8, 10] Expected Output: 5.5

Conclusion

The brute force solution can be summarized as follows: the code has a time complexity of O((m + n) log(m + n)), implying that the running time increases logarithmically with the size of the input arrays. In terms of space complexity, it is O(m + n), indicating that the space usage grows linearly with the size of the input arrays. By utilizing Merge Sort instead of Bubble Sort, the code employs a more efficient sorting algorithm, especially beneficial for larger arrays.

References:

• https://leetcode.com/problems/median-of-two-sorted-arrays/description/