Skip to content

Instantly share code, notes, and snippets.

@adamkorg
Created April 25, 2019 09:17
Show Gist options
  • Save adamkorg/ffba283f298e7c2c2b748acb49ccc9f1 to your computer and use it in GitHub Desktop.
Save adamkorg/ffba283f298e7c2c2b748acb49ccc9f1 to your computer and use it in GitHub Desktop.
Leetcode median of two sorted arrays problem
#include <iostream>
#include <vector>
using namespace std;
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int size1 = nums1.size();
int size2 = nums2.size();
if (size1 < size2) //if one array is smaller then we want smaller in nums2
return findMedianSortedArrays(nums2, nums1);
if (size2 == 0) //single list
return (double(nums1[(size1-1)/2])+nums1[size1/2])/2;
int start1 = 0, start2 = 0;
int len1 = size1, len2 = size2;
bool beyond_start1=false, beyond_start2=false, beyond_end1=false, beyond_end2=false;
while (true) {
int L1 = (beyond_start1) ? INT_MIN : nums1[start1 + ((len1-1)/2)];
int L2 = (beyond_start2) ? INT_MIN : nums2[start2 + ((len2-1)/2)];
int R1 = (beyond_end1) ? INT_MAX : nums1[start1 + (len1/2)];
int R2 = (beyond_end2) ? INT_MAX : nums2[start2 + (len2/2)];
if (L1 > R2) { //partition list 2 window to use 2nd half (right half)
if (len2==1) { //beyond end of list 2 edge case
if (start2<size2-1)
len2++;
else
beyond_end2 = true;
if (len1==1) { //and beyond start of list1 edge case
if (start1>0) {
len1++;
start1--;
}
else
beyond_start1 = true;
}
else
len1--;
}
else {
int new_len2 = (len2/2);
start2 += ((len2+1)/2);
int num_discarded = len2 - new_len2;
len2 = new_len2;
//also discard num_discarded from right side of list 1 window
len1 = len1 - num_discarded;
}
}
else if (R1 < L2) { //partition list 2 window to use 1st half (left half)
if (len2==1) { //before start of list 2 edge case
if (start2>0) {
start2--;
len2++;
}
else
beyond_start2 = true;
if (len1==1) { //beyond end of list 1 edge case
if (start1<size1-1)
len1++;
else
beyond_end1 = true;
}
else {
start1++;
len1--;
}
}
else {
int new_len2 = (len2/2);
int num_discarded = len2 - new_len2;
len2 = new_len2;
//also discard num_discarded from left side of list1 window
start1 += num_discarded;
len1 -= num_discarded;
}
}
else {
return ((double(max(L1,L2))+min(R1,R2))/2);
}
}
return -1;
}
int main() {
cout << "findMedianSortedArrays({3,6,8,11,15,18},{1,2,4,7}) = ";
vector<int> nums1 = {3,6,8,11,15,18};
vector<int> nums2 = {1,2,4,7};
cout << findMedianSortedArrays(nums1, nums2) << endl;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment