Solving problem: Median of Two Sorted Arrays

Table of Contents

• Problem Statement
• Examples
• Test Cases
• Solution O(n+m)

Problem Statement

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

Constraints:

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

Examples

In this example, you are provided with an input of arrays containing integers. The length of this array will vary depending on every testcase. You will get atleast 2 items in the array.

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

OUTPUT: 2.00000

Explanation:

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

OUTPUT: 2.50000

Explanation: After combininig both the arrays you will get [1,2,3,4] and has a length of 4(which is even), you will substitute the value into the formula $\frac{n_p\ +\ n_{p+1}}{2}$.

• p = $\frac{4}{2} = 2$
• $\frac{2 + 3}{2} = 2.50000$

Test Cases

INPUT:
   nums1 = [3]
   nums2 = []

OUTPUT: 3.00000

INPUT:
   nums1 = []
   nums2 = [1]

OUTPUT: 1.00000

INPUT:
   nums1 = [3]
   nums2 = [-2, -1]

OUTPUT: -1.00000

INPUT:
   nums1 = [10000]
   nums2 = [10001]

OUTPUT: 10000.50000

HINT: Can you come up with an algorithm that is less than O(n+m) time complexity?

Solution O(n+m)

var findMedianSortedArrays = function (nums1, nums2) {
	if (nums2.length < 1 && nums1.length == 1) return nums1[0];
	if (nums1.length < 1 && nums2.length == 1) return nums2[0];

	let l = 0;
	let r = 0;
	let n = [];
	let le = nums1.length + nums2.length;

	for (let i = 0; i < le; i++) {
		if (nums2[r] == undefined) {
			n[i] = nums1[l];
			l++;
		} else if (nums1[l] <= nums2[r]) {
			n[i] = nums1[l];
			l++;
		} else if (nums1[l] >= nums2[r]) {
			n[i] = nums2[r];
			r++;
		} else if (nums1[l] == undefined) {
			n[i] = nums2[r];
			r++;
		}
	}

	let o = 0;

	if (le % 2) {
		o = n[(le - 1) / 2];
	} else {
		k = le / 2;
		o = (n[k] + n[k - 1]) / 2;
	}

	return Math.round(o * 10e5) / 10e5;
};

This is a JavaScript function called findMedianSortedArrays that takes two arrays of numbers (nums1 and nums2) as input and returns the median value of the combined sorted arrays.

The function first checks if either of the input arrays has a length of 1 and the other array is empty. In that case, the function returns the single value from the non-empty array as the median.

Next, the function initializes four variables: l and r are used as indices to traverse the nums1 and nums2 arrays, respectively; n is an empty array that will hold the sorted and combined values from both input arrays; le is the total length of both input arrays.

Then, the function uses a loop to iterate over the total number of values in the combined nums1 and nums2 arrays. Inside the loop, the function checks four conditions using if and else if statements:

• If the current index in nums2 is undefined (meaning all values from that array have been added to n), then the next value to add to n is from nums1 at the current index, and l is incremented to move to the next index in nums1.
• If the value in nums1 at the current index is less than or equal to the value in nums2 at the current index, then the next value to add to n is from nums1 at the current index, and l is incremented to move to the next index in nums1.
• If the value in nums1 at the current index is greater than or equal to the value in nums2 at the current index, then the next value to add to n is from nums2 at the current index, and r is incremented to move to the next index in nums2.
• If the current index in nums1 is undefined (meaning all values from that array have been added to n), then the next value to add to n is from nums2 at the current index, and r is incremented to move to the next index in nums2.

After all values have been added to n, the function calculates the median value based on the total length of both input arrays (le) and whether that length is even or odd.

• If le is odd, the median value is simply the value at the index (le - 1) / 2 in the n array.
• If le is even, the median value is the average of the values at indices le / 2 and le / 2 - 1 in the n array.

Finally, the function returns the median value rounded to 5 decimal places using Math.round and division by 10e5.

🔝 Go To Beginning 🔝