Posts Median of Two Sorted Arrays
Post
Cancel

Median of Two Sorted Arrays

Problem Description

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.
The overall run time complexity should be O(log (m+n)).

leetcode

Solution

NeetCode Youtube

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
class Solution {

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

        //handle empty arrays
        if(nums1.length == 0 && nums2.length ==0)
            return 0;

        if(nums1.length == 0)
            return nums2.length%2 == 0 ? (nums2[nums2.length/2] + nums2[(nums2.length-1)/2] )/2.0 : nums2[nums2.length/2];

        if(nums2.length == 0)
            return nums1.length%2 == 0 ? (nums1[nums1.length/2] + nums1[(nums1.length-1)/2] )/2.0 : nums1[nums1.length/2];


        //ensure nums1 is of smaller length
        //we will apply Binary Search on smaller array for better time complexity
        if(nums1.length > nums2.length){
            int[] temp = nums1;
            nums1 = nums2;
            nums2 = temp;
        }

        //init
        int n = nums1.length;
        int m = nums2.length;
        int total = n+m;
        int half = total/2; //size of partition needed

        //binary search on nums1
        int l=0;
        int r=nums1.length;

        while(true){

            //IMPORTANT: https://www.geeksforgeeks.org/python-operators/
            //int i = (l+r)/2 will not work. We need to floor value which is equivalent of // in Python
            int i = (int)Math.floor((r+l)/2.0);

            //half - (number of elements till i) - 1 because 0 indexed
            //=> half - (i+1) - 1 = half - i - 2;
            int j = half - i - 2;

            //get the elements which need to be compared
            int nums1Left = (i>=0?nums1[i]:Integer.MIN_VALUE);
            int nums1Right = (i+1<nums1.length?nums1[i+1]:Integer.MAX_VALUE);

            int nums2Left = (j>=0?nums2[j]:Integer.MIN_VALUE);
            int nums2Right = (j+1<nums2.length?nums2[j+1]:Integer.MAX_VALUE);

            //valid partition
            if(nums1Left <= nums2Right && nums2Left <= nums1Right){
                //odd
                if(total%2 == 1){
                    return Math.min(nums1Right, nums2Right);
                }//even
                else{
                    return (double)(Math.max(nums1Left, nums2Left) + Math.min(nums1Right, nums2Right)) / 2;
                }
            //need to take lesser elements in nums1 partition
            }else if(nums1Left > nums2Right){
                r = i-1;
            //else need more elements in nums1 partition
            }else{
                l = i+1;
            }

        }

    }
}

ANOTHER WAY TO CODE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {

        if (nums1.length > nums2.length) {
            int[] temp = nums1;
            nums1 = nums2;
            nums2 = temp;
        }

        int n = nums1.length;
        int m = nums2.length;

        int total = n + m;
        int half = total / 2;

        int l = 0;
        int r = n;

        while (l <= r) {

            int i = (l + r) / 2;
            int j = half - i;

            int aLeft = (i > 0) ? nums1[i - 1] : Integer.MIN_VALUE;
            int aRight = (i < n) ? nums1[i] : Integer.MAX_VALUE;
            int bLeft = (j > 0) ? nums2[j - 1] : Integer.MIN_VALUE;
            int bRight = (j < m) ? nums2[j] : Integer.MAX_VALUE;

            if (aLeft <= bRight && bLeft <= aRight) {

                if (total % 2 == 1) {
                    return Math.min(aRight, bRight);
                } else {
                    return (Math.max(aLeft, bLeft) + Math.min(aRight, bRight)) / 2.0;
                }

            } else if (aLeft > bRight) {
                r = i - 1;
            } else {
                l = i + 1;
            }

        }

        return 0;
    }
}

SIMILAR CODE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
class Solution {

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

        int n = nums1.length;
        int m = nums2.length;

        // make the first array shorter
        // we will use binary search on nums1
        if(n > m)
            return findMedianSortedArrays(nums2, nums1);

        // total number of elements
        int total = n+m;

        // we need half of total to figure out the median
        int half = total/2;

        // init: for binary search
        int l = 0; // take 0 elements from nums1
        int r = n; // take n elements from nums1

        while(l <= r){

            // i -> partition position for first array
            int i = (l + r + 1)/2;

            // j -> if we take x elements from first array, we will take (half-x) from second array to figure out the median
            int j = half - i;

            // init: left of partition index as MIN
            // init: right of partition index as MAX
            int l1 = Integer.MIN_VALUE, l2 = Integer.MIN_VALUE;
            int r1 = Integer.MAX_VALUE, r2 = Integer.MAX_VALUE;

            if(i-1 >= 0)
                l1 = nums1[i-1]; // left of partition position in arr1
            if(i < n)
                r1 = nums1[i];  // at the partition position in arr1

            if(j-1 >=0)
                l2 = nums2[j-1]; // left of partition position in arr2

            if(j < m)
                r2 = nums2[j]; // at the partition position in arr2

            if(l1 <= r2 && l2 <= r1){ // check if this can form the first half correctly

                // if even length
                if(total%2 == 0){

                    return (Math.max(l1, l2) + Math.min(r1, r2))/2.0;

                // for odd length
                }else{

                    return Math.min(r1, r2)/1.0;

                }

            // if arr1 partition has greater element than arr2 partition, we need to reduce arr1 partition
            }else if(l1 > r2){
                r = i - 1;
            // otherwise, we need to add more elements to arr1 partition
            }else
                l = i + 1;

        }

        return -1.0;

    }

}
This post is licensed under CC BY 4.0 by the author.