Updated Median of Two Sorted Arrays

varunu28 · varunu28 · commit e3ef07b08ef6 · 2023-03-21T09:29:47.000-07:00
diff --git a/Hard/Median of Two Sorted Arrays.java b/Hard/Median of Two Sorted Arrays.java
@@ -1,42 +1,25 @@
 class Solution {
     public double findMedianSortedArrays(int[] nums1, int[] nums2) {
-        int n = nums1.length + nums2.length;
-        ArrayList<Integer> arr = new ArrayList<>();
-        
-        int i = 0;
-        int j = 0;
-        int k = 0;
-        int limit = (n)/2 + 1;
-        
-        while (i < nums1.length && j < nums2.length && k < limit) {
-            if (nums1[i] < nums2[j]) {
-                arr.add(nums1[i]);
-                i++;
-            }
-            else {
-                arr.add(nums2[j]);
-                j++;
-            }
-            k++;
-        }
-        
-        if (i < nums1.length) {
-            while (i < nums1.length && k < limit) {
-                arr.add(nums1[i]);
-                i++;
-                k++;
-            }
+        if (nums1.length < nums2.length) {
+            return findMedianSortedArrays(nums2, nums1);
         }
-        else {
-            while (j < nums2.length && k < limit) {
-                arr.add (nums2[j]);
-                j++;
-                k++;
+        int low = 0;
+        int high = nums2.length * 2;
+        while (low <= high) {
+            int midTwo = (low + high) / 2;
+            int midOne = nums1.length + nums2.length - midTwo;
+            double leftOne = (midOne == 0) ? Integer.MIN_VALUE : nums1[(midOne - 1) / 2];	
+            double leftTwo = (midTwo == 0) ? Integer.MIN_VALUE : nums2[(midTwo - 1) / 2];
+            double rightOne = (midOne == nums1.length * 2) ? Integer.MAX_VALUE : nums1[(midOne) / 2];
+            double rightTwo = (midTwo == nums2.length * 2) ? Integer.MAX_VALUE : nums2[(midTwo) / 2];
+            if (leftOne > rightTwo) {
+                low = midTwo + 1;
+            } else if (leftTwo > rightOne) {
+                high = midTwo - 1;
+            } else {
+                return (Math.max(leftOne, leftTwo) + Math.min(rightOne, rightTwo)) / 2;	
             }
         }
-        
-        k--;
-        
-        return n%2 == 0 ? (double) (arr.get(k - 1) + arr.get(k)) / 2.0 : (double) arr.get(k);
+        return -1;
     }
 }
