my code got accepted on leetcode but here it is giving only 2 test cases correct. Kindly tell me where it is going wrong .
Https://ide.codingblocks.com/s/258659
@manuu_98 i think here you are not supposed to return the average of 2 medians (if there are 2) but rather just one of them. Please provide the link of the problem or the description (along with sample input/output) so i can clear it up.
@manuu_98 but it is giving “int” ans even in the case of 2 medians, in the given sample output it is clear that in that case you have to report the answer like 2.0 and not 2
@Ishitagambhir
in sample case there is single median only so as u earlier said ( like 13 and not 13.0 ) the ans should be 2 not 2.0
hi @manuu_98 i checked your code against all the test cases and your answer is not matching in many of them, so you need to change your approach. The test cases are quite big (10000 elements in each array) so I cannot share them with you.
I am sharing the tutorial with you
Median Of two Sorted Arrays(Binary Search)
Algorithm:-
The intuition here to use binary search is because we are given two sorted arrays. The approach discussed here will work even when we have arrays of different sizes.
. How is median of two arrays calculated:-
Intuition behind the approach:-
Let lenA be the size of array nums1 and lenB be the size of array nums2.
1. Let aCount is the index at which array nums1 is partitioned and bCount is the index at which array nums2 is partitioned. aCount + bCount = mid i.e the left and right partition must equally divide the combined elements of the array to find the median. Where is mid = (lenA + lenB + 1) / 2
2. Calculate max element of nums1 in left partition maxLeftA and min element in right partition minRightA. Similarly calculate maxLeftB and minRightB. Condition for perfect partition is when :- maxLeftA <= minRightB && maxLeftB <= minRightA
3. maxLeftA > minRightB, aCount partition is too far to the right so reduce the search space to the left and move the aCount to left.
4. Else aCount is too far to the left so reduce the search space to the right and move aCount to right.
5. If Perfect partition is found:-
If combined size of both the arrays is even i.e lenA + lenB is even:-
Return Avg(max(maxLeftA, maxLeftB) + min(minRightA, minRightB)) as median.
Else
Return max(maxLeftA, maxLeftB) as median.
Also the algorithm only involves iterating on the smaller of the two arrays, the function is called again so that nums1 is always the smaller array.
Time Complexity:- The algorithm has logarithmic time complexity as we have arrays already sorted and logn due to binary search.
Solution link:- https://ide.codingblocks.com/s/183462
1 Like