Find median of two sorted arrays (merge approach)
Hard
Java
Methods
15 views
Problem Statement
Task: return median of two sorted arrays using merge-like walk (O(n+m)).
Input Format
• First line: Integer n (size of first array)
• Second line: n space-separated sorted integers
• Third line: Integer m (size of second array)
• Fourth line: m space-separated sorted integers
• Second line: n space-separated sorted integers
• Third line: Integer m (size of second array)
• Fourth line: m space-separated sorted integers
Output Format
Print the median value
Example
3 1 3 5 3 2 4 6
123
Constraints
• 0 ≤ n, m ≤ 10^5
• Arrays are sorted in non-decreasing order
• -10^9 ≤ elements ≤ 10^9
• At least one array is non-empty
• Arrays are sorted in non-decreasing order
• -10^9 ≤ elements ≤ 10^9
• At least one array is non-empty
Concept Explanation
Merged array would be:
1 2 3 4 5 6
Total elements = 6 (even)
Median = average of middle two elements
= (3 + 4) / 2
= 3.5
1 2 3 4 5 6
Total elements = 6 (even)
Median = average of middle two elements
= (3 + 4) / 2
= 3.5
Step-by-Step Explanation
1.Read both arrays.
2.Use two pointers i and j starting at 0.
3.Calculate total length = n + m.
4.Find positions needed for median:
• If total is odd → middle index = total / 2
• If even → need elements at (total/2 - 1) and (total/2)
5.Traverse arrays like merge step of merge sort:
• Compare current elements of both arrays.
• Move the pointer of smaller element.
• Keep counting elements visited.
6.When you reach required median position(s), store the value(s).
7.If total is odd → print that value.
8.If total is even → print average of two stored values.
2.Use two pointers i and j starting at 0.
3.Calculate total length = n + m.
4.Find positions needed for median:
• If total is odd → middle index = total / 2
• If even → need elements at (total/2 - 1) and (total/2)
5.Traverse arrays like merge step of merge sort:
• Compare current elements of both arrays.
• Move the pointer of smaller element.
• Keep counting elements visited.
6.When you reach required median position(s), store the value(s).
7.If total is odd → print that value.
8.If total is even → print average of two stored values.
Concept Explanation
Merged array would be:
1 2 3 4 5 6
Total elements = 6 (even)
Median = average of middle two elements
= (3 + 4) / 2
= 3.5
1 2 3 4 5 6
Total elements = 6 (even)
Median = average of middle two elements
= (3 + 4) / 2
= 3.5
Step-by-Step Explanation
1.Read both arrays.
2.Use two pointers i and j starting at 0.
3.Calculate total length = n + m.
4.Find positions needed for median:
• If total is odd → middle index = total / 2
• If even → need elements at (total/2 - 1) and (total/2)
5.Traverse arrays like merge step of merge sort:
• Compare current elements of both arrays.
• Move the pointer of smaller element.
• Keep counting elements visited.
6.When you reach required median position(s), store the value(s).
7.If total is odd → print that value.
8.If total is even → print average of two stored values.
2.Use two pointers i and j starting at 0.
3.Calculate total length = n + m.
4.Find positions needed for median:
• If total is odd → middle index = total / 2
• If even → need elements at (total/2 - 1) and (total/2)
5.Traverse arrays like merge step of merge sort:
• Compare current elements of both arrays.
• Move the pointer of smaller element.
• Keep counting elements visited.
6.When you reach required median position(s), store the value(s).
7.If total is odd → print that value.
8.If total is even → print average of two stored values.
Input / Output Format
Input Format
• First line: Integer n (size of first array)
• Second line: n space-separated sorted integers
• Third line: Integer m (size of second array)
• Fourth line: m space-separated sorted integers
• Second line: n space-separated sorted integers
• Third line: Integer m (size of second array)
• Fourth line: m space-separated sorted integers
Output Format
Print the median value
Constraints
• 0 ≤ n, m ≤ 10^5
• Arrays are sorted in non-decreasing order
• -10^9 ≤ elements ≤ 10^9
• At least one array is non-empty
• Arrays are sorted in non-decreasing order
• -10^9 ≤ elements ≤ 10^9
• At least one array is non-empty
Examples
Input:
3
1 3 5
3
2 4 6
Output:
123
Example Solution (Public)
static double median2(int[] a,int[] b){int n=a.length,m=b.length;int total=n+m;int i=0,j=0;int prev=0,cur=0;for(int k=0;k<=total/2;k++){prev=cur;if(i<n && (j>=m || a[i]<=b[j])) cur=a[i++]; else cur=b[j++];}if((total&1)==1) return cur;return (prev+cur)/2.0;}
Official Solution Code
static double median2(int[] a,int[] b){int n=a.length,m=b.length;int total=n+m;int i=0,j=0;int prev=0,cur=0;for(int k=0;k<=total/2;k++){prev=cur;if(i<n && (j>=m || a[i]<=b[j])) cur=a[i++]; else cur=b[j++];}if((total&1)==1) return cur;return (prev+cur)/2.0;}
Please login to submit solutions.