Hello friends, we meet again on our journey of Java and the ocean of knowledge. I am sure you guys must be very excited about today's lesson as today we will deep dive into something that makes everyone's head scratch, yes, we will talk about a popular coding problem. So friends, get ready to scratch your head, learn something, code a few things, and use some of your grey cells (Agatha christie fans rejoicing in the back :p). So friends, today's topic is coding and we will take on one of the most famous and difficult problems. Today we will learn how to find the median of two sorted arrays. seems easy right? Wait a bit, I will make sure you learn something new and make it a bit of a challenge :D
So let's understand the problem first. It may sound like an easy problem, but the optimal implementation is a pretty hard one, especially if you have to find the median of two sorted arrays of different sizes or lengths.
The problem [Median of Two Sorted Array]:
 If n is even: median = array[n/2] (value of (n/2)nd element)
 if n is odd: median = ((array[(n1)/2]) + (array[(n+1)/2])) / 2
2. Solution:
2.1 Code (Brute Force approach):
import java.util.Arrays;
import java.util.Scanner;
public class MedianOfTwoSortedArrays {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int sizeOfFirstArray = sc.nextInt();
int sizeOfSecondArray = sc.nextInt();
int[] firstArray = new int[sizeOfFirstArray];
int[] secondArray = new int[sizeOfSecondArray];
for(int i=0;i<sizeOfFirstArray;i++) {
firstArray[i] = sc.nextInt();
}
for(int i=0;i<sizeOfSecondArray;i++) {
secondArray[i] = sc.nextInt();
}
Arrays.sort(firstArray);
Arrays.sort(secondArray);
double median = findMedianSortedArrays(firstArray, secondArray);
System.out.println("median of above two arrays is: "+median);
}
public static double findMedianSortedArrays(int[] firstArray, int[] secondArray) {
int firstArrayLength = firstArray.length;
int secondArrayLength = secondArray.length;
int[] combinedArray = new int[firstArrayLength+secondArrayLength];
int k=0;
for(int i:firstArray) {
combinedArray[k++] = i;
}
for(int i:secondArray) {
combinedArray[k++] = i;
}
Arrays.sort(combinedArray);
double median;
if(combinedArray.length % 2 == 0) {
median = combinedArray[combinedArray.length/2];
} else {
median = (combinedArray[(combinedArray.length1) / 2] + combinedArray[(combinedArray.length+1) / 2])/2;
}
return median;
}
}
Code (Efficient approach)
import java.util.Arrays;
import java.util.Scanner;
public class MedianOfTwoSortedArrays {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int sizeOfFirstArray = sc.nextInt();
int sizeOfSecondArray = sc.nextInt();
int[] firstArray = new int[sizeOfFirstArray];
int[] secondArray = new int[sizeOfSecondArray];
for(int i=0;i<sizeOfFirstArray;i++) {
firstArray[i] = sc.nextInt();
}
for(int i=0;i<sizeOfSecondArray;i++) {
secondArray[i] = sc.nextInt();
}
Arrays.sort(firstArray);
Arrays.sort(secondArray);
double median = findMedianSortedArrays(firstArray, secondArray);
System.out.println("median of above two arrays is: "+median);
}
public static double findMedianSortedArrays(int[] a, int[] b) {
if(a.length == 0 && b.length == 0) return 0.0;
//consider a=[2], b=[]
//if not swapped, bleft will be ve hence this condition will fail:
//bleft == 0 ? Integer.MIN_VALUE : b[bleft  1]
if(a.length > b.length) {
int[] temp = a;
a = b;
b = temp;
}
int lo = 0, hi = a.length, total = a.length + b.length;
while(lo <= hi) {
int aleft = lo + (hi  lo) / 2;
int bleft = (total + 1) / 2  aleft;
int maVal = aleft == 0 ? Integer.MIN_VALUE : a[aleft  1];
int mbVal = bleft == 0 ? Integer.MIN_VALUE : b[bleft  1];
int aVal = aleft == a.length ? Integer.MAX_VALUE : a[aleft];
int bVal = bleft == b.length ? Integer.MAX_VALUE : b[bleft];
if(maVal <= bVal && mbVal <= aVal) {
double res = Math.max(maVal, mbVal);
if(total % 2 == 0) {
res += Math.min(aVal, bVal);
res /= 2.0;
}
return res;
}else if(maVal > bVal) {
hi = aleft  1;
} else {
lo = aleft + 1;
}
}
return 0.0;
}
}
Now, as we have seen the code, can you guys try to understand it? take 2 minutes time and try to understand it by performing a dry run on the code. (yes, grab a penpaper :p)
So, let's understand it then.

perform binary search on 'a' if 'a' has less elements than 'b' else swap
'a' & 'b' & continue binary search on 'a'
 aleft & bleft are boundary elements

hi=a.length & not a.length1. run this test case to understand
better : a=[1,2] & b=[3,4] for hi boundaries

len(a)+len(b) is odd, median=max(a[aleft1],max[bleft1])

len(a)+len(b) is even,
median=(max(a[aleft1],max[bleft])+min(a[aleft],b[bleft])/2.0

(int+int)/2 will result integer value hence divide by 2.0 & not 2
 as using aleft1 & bleft1 to calculate median for odd no. of total elements so add 1 to total like this: bleft=(total + 1)/2aleft.The above steps would be enough to make you understand the code thoroughly.
That's all about the How to calculate the median of two sorted arrays in Java. This is an interesting problem and you should know how to solve this, especially if you're preparing for coding interviews. This also explores other algorithms like searching in a sorted array
Other Data Structure and Algorithms Resources you may like
 5 Free Courses to learn Algorithms indepth (courses)
 10 Algorithms books every Programmer should read (books)
 My favorite Free Algorithms and Data Structure Courses on FreeCodeCamp (courses)
 30+ linked list interview questions with a solution (linked list)
 30+ arraybased interview questions for programmers (array)
 75+ Coding Problems from Interviews (questions)
 10 Free Courses to learn Data Structure and Algorithms (courses)
 10 Books to Prepare Technical Programming/Coding Job Interviews (books)
 10 Courses to Prepare for Programming Job Interviews (courses)
 5 Websites for Coding Interview Preparation for FREE (websites)
 100+ Data Structure and Algorithms Interview Questions (questions)
 20+ String Coding Problems from Interviews (questions)
 10 Coding Tips and 101 Coding Questions for Interviews (tips)
 50+ Algorithm based Interview questions from HackerNoon (questions)
 Top 5 Data Structure and Algorithms Courses for Programmers (courses)
Thanks for reading this article so far. If you like this Array coding
problem and my solution and explanation, then please share it with your
friends and colleagues. If you have any questions or feedback, then please
drop a note.
P. S.  If you are looking for a FREE course to learn Data
Structure from scratch, you can also check out the
Data Structures in Java for the Noobs course
on Udemy. A complete guide to learning everything there is to know about
data structures for free.
No comments:
Post a Comment
Feel free to comment, ask questions if you have any doubt.