Merge input arrays using merge approach used in MergeSort, if the resultant array length is an even number, then take median as result[midIndex] + result[midIndex-1] / 2 , otherwise take median as result[midIndex].

1. Let's declare two variables i=0 and j=0 to track the indexes of nums1 and nums2 respectively.
2. Compare numbers from both arrays and take the smallest number into result array and repeat this process until one of the array is fully done.
3. Copy any remaining numbers from nums1 or nums2.
4. Now, you have result array fully sorted and you can take median of the resultant array.

Complexity:

Merging two sorted arrays, takes O (m + n) run time and takes O (m +n) space as we are copying sorted numbers into a resultant array.

The main idea in this approach is, as we compare elements from nums1 and nums2, just keep copy of the elements we need to compute median and ignore rest. If the resultant array after merging is going to be of length n, then we need at most n/2 +1 comparisons whether n is even or odd.

Let's take an example, say the given input arrays are nums1 = [1,4,9] and nums2 = [3,7,8] , when you merge them, this is the resultant array [1,3, 4,7 ,8,9], so the numbers required to compute median are located at 2^nd and 3^rd indexes. So, we only need to loop until 4th index.

Steps:

1. Let's declare two variables i=0 and j=0 to track the indexes of nums1 and nums2 respectively.
2. Declare two more variables m1=-1 and m2=-1 to store large numbers seen so far as we compare input arrays.

When resultant array is even length array:

1. In a for loop from 0 to n (inclusive) compare the elements from nums1 and nums2 and store the higher number into m2 (before storing it, copy the previous value from m2 into m1).
• If the highest number is taken from nums1 array, then increment i.
• If the highest number is taken from nums2 array, then increment j.
2. When i reach end of nums1 array, then look at elements from nums2 elements only.
3. When j reach end of nums2 array, then look at elements from nums1 elements only.
4. Once we have m1 and m2 values, take median as (m1 + m2) /2 .

When resultant array is odd length array:

1. Repeat the same exact steps as above in the case where resultant array length is even, but just copy minimum element in each loop into m1.
2. Finally return m1 as this will be the middle element when array merged.

Complexity:

For loop runs n/2 times, so it takes O (n) run time where n is the size of resultant array, and takes O (1) space as we are storing middle two numbers only into two temporary variables.

The main idea in this approach is to find a partion point from both arrays where they become middle 4 elements of resultant array, and if arrays are smaller then we use temporary values such as Integer.MAX_VALUE to represent right most maxinum element and similarly Integer.MIN_VALUE to represent left most minimum element.

Steps:

1. Assume nums1 array is the smallest array, in case if it isn't then reverse the input arrays.
2. Declare two variables low and high with lower and higher bounds of nums1 array. int low = 0; int high = nums1.length;
3. Partition both arrays at following indexes.
   nums1 array ==> at (low + high) / 2 index.
   nums2 array ==> at (nums1.length + nums2.length + 1) / 2 - nums1 partition index, here we have added +1 because in case if the resultant array is an odd length array, then we want middile element to be on life side of partition. int x= nums1.length; int y = nums2.length; int partitionX = (low + high) /2; int partitionY = (x + y + 1)/2 - partitionX;
4. When you partition the arrays, say leftX and rightX are elements on left and right side of nums1 array, and leftY and rightY are left and right elements of nums2 array.
   Note that we have to handle edge cases as well, incase if there are no elements left of left or right ends of arrays. //partitionX == 0 is when there is nothing left on left side of the nums1 array //partitionX == x is when there is nothing left on right side of the nums1 array int leftX = partitionX == 0 ? Integer.MIN_VALUE : nums1[partitionX-1]; int rightX = partitionX == x ? Integer.MAX_VALUE : nums1[partitionX]; //partitionY == 0 is when there is nothing left on left side of the nums2 array //partitionY == y is when there is nothing left on right side of the nums2 array int leftY = partitionY ==0 ? Integer.MIN_VALUE: nums2[partitionY-1]; int rightY = partitionY ==y ? Integer.MAX_VALUE: nums2[partitionY];
5. Now, check for following conditions, when these condition are met, that means we found a partition from both arrays where these 4 elements are what comes in the middle of the resultant array.
• leftX, the left element of nums1 array is less than or equal to rightY, the right element of nums2 array.
• leftY, the left element of nums2 array is less than or equal to rightX, the right element of nums1 array.
6. If we find such partition as step-5, then take median as follows.
• If resultant array is an even length array, then median is Max(leftX, leftY) + Min(rightX, rightY) /2 .
• If resultant array is an odd length array, then median is Max(leftX, leftY).
7. If we did not find partition as step-5, then check if leftX > rightY, this means we are too far on the right side of array. So, decrement high by 1. Otherwise increment low by 1 and repeat ste-3 onwards.