forked from neetcode-gh/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
4-Median-Of-Two-Sorted-Arrays.js
48 lines (38 loc) · 1.47 KB
/
4-Median-Of-Two-Sorted-Arrays.js
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
/**
* @param {number[]} nums1
* @param {number[]} nums2
* Time O(log(N * M)) | Space O(N)
* @return {number}
*/
var findMedianSortedArrays = function(nums1, nums2) {
const canSwap = nums2.length < nums1.length;
if (canSwap) [nums1, nums2] = [nums2, nums1];
let [ left, right ] = [ 0, nums1.length - 1 ];
const totalLength = nums1.length + nums2.length
const mid = totalLength >> 1;
const isEven = (totalLength % 2) === 0;
while (true) {
const mid1 = left + right;
const mid2 = (mid - mid1) - 2;
const { aLeft, aRight, bLeft, bRight } = getPointers(nums1, mid1, nums2, mid2);
const isTarget = (aLeft <= bRight) && (bLeft <= aRight);
if (isTarget) return isEven
? (Math.max(aLeft, bLeft) + Math.min(aRight, bRight)) / 2
: Math.min(aRight, bRight);
const isTargetGreater = aLeft <= bRight;
if (isTargetGreater) left = mid1 + 1;
const isTargetLess = bRight < aLeft;
if (isTargetLess) right = mid1 - 1;
}
}
const getPointers = (nums1, mid1, nums2, mid2) => {
const getLeft = (nums, index) => 0 <= index
? nums[index]
: -Infinity;
const [ aLeft, bLeft ] = [ getLeft(nums1, mid1), getLeft(nums2, mid2) ];
const getRight = (nums, index) => (index + 1) < nums.length
? nums[index + 1]
: Infinity;
const [ aRight, bRight ] = [ getRight(nums1, mid1), getRight(nums2, mid2) ];
return { aLeft, aRight, bLeft, bRight };
}