Median of Two Sorted Arrays – Leetcode #4

Problem Statement

This problem is from Leetcode – Median of Two Sorted Arrays. The problem statement is given below:

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

Solution

Approach – 1

Lets try a simple solution first. We can simply add elements from first and second array into a third array and sort it. Then find the median of the third array. See the code sample below:

public double findMedianSortedArrays(int[] nums1, int[] nums2) {

		double med = 0;

		// declare a third array
		int[] nums3 = new int[nums1.length + nums2.length];

		// add elements from first given array
		for(int i=0; i<nums1.length; i++) {

			nums3[i] = nums1[i];
		}

		// add elements from second given array
		int idx = nums1.length;
		for(int i=0; i<nums2.length; i++) {

			nums3[idx] = nums2[i];
			idx++;
		}

		// Sort the arrays
		Arrays.sort(nums3);

         // can use the below call also for sort
		//Arrays.parallelSort(nums3);

		int len3 = nums3.length;

		// if array length is even
		if(len3 == 0) {

			med = 0;
		}
		else {
			if(len3 % 2 == 0) {

				int n1 = nums3[len3/2 - 1];
				int n2 = nums3[len3/2] ;

				med =  (double)( n1 + n2  ) / 2 ;
			}
		}


		// if array length is odd
		if(len3 % 2 != 0) {

			if(len3 == 1 ) {

				med = nums3[0];
			}
			else {

				med = nums3[len3 / 2 ];
			}
		}

		return med;
	}

You can checkout the code from Github here: Median of two sorted arrays – First Approach. See the performance of this approach below:

Approach – 2

Can we improve upon the above approach ? Notice that the two given arrays are already sorted. All we need to do is to merge them efficiently. See the code sample below:

public double findMedianSortedArrays(int[] nums1, int[] nums2) {

		double med = 0;

		int i = 0;
		int j = 0;
		int k = 0;

		int m = nums1.length;
		int n = nums2.length;
		
		// declare third array - this will contain the merged sorted array 
		int[] nums3 = new int[m+n];
		
		// merge the given two sorted arrays into the third array
		while(i < m  &&  j < n){

			if (nums1[i] < nums2[j]) {
				
				nums3[k++] = nums1[i++];
			} 
			else {
				
				nums3[k++] = nums2[j++];
			}
		}
		
		/* append any integers that are left */
		
		while (i < m) {
			nums3[k++] = nums1[i++];
		}

		while (j < n) {
			nums3[k++] = nums2[j++];
		}
		
		/* now find the median of third array below */
		
		int len3 = nums3.length;

		// if array length is even
		if(len3 == 0) {

			med = 0;
		}
		else {
			if(len3 % 2 == 0) {

				int n1 = nums3[len3/2 - 1];
				int n2 = nums3[len3/2] ;

				med =  (double)( n1 + n2  ) / 2 ;
			}
		}


		// if array length is odd
		if(len3 % 2 != 0) {

			if(len3 == 1 ) {

				med = nums3[0];
			}
			else {

				med = nums3[len3 / 2 ];
			}
		}


		return med;
	}

You can checkout the code from Github here: Second Approach. See the performance of this approach below:

Also see the complexity calculated by Leetcode: